Recurrence
Also known as: Recurrence relation
A recurrence defines $T(n)$ in terms of smaller values, usually the running time of a recursive algorithm: e.g. $T(n) = 2T(n/2) + O(n)$ for merge sort.
Solve with the master theorem, a recursion tree, or substitution (guess and induct). DP also uses recurrences, but for values of subproblems, not only for runtime.
Always include base cases. Floors, ceilings, and uneven splits rarely change $\Theta$ class, but they can break a sloppy closed form.