Recursion, Recurrence Relations, and the Master Theorem

Two threads meet this week. In Notes 01 you proved a recursive procedure correct by induction; in Notes 02 you priced loops by counting. This week the code starts calling itself in earnest, and pricing it needs a new instrument: the recurrence relation — an equation a recursive algorithm writes about its own cost. We will learn to extract that equation from code, solve it three ways by hand, and then meet the Master Theorem, which solves the most common family on sight. All of it is preparation for next week, when divide and conquer stops being an exercise and becomes merge sort and quicksort.

Session planHow we will spend the two sessions

Section 1Thinking recursively

Recursion works whenever the problem is self-similar — when an instance contains smaller instances of itself. Much of computing has this shape once you look for it. A list is either empty or one element in front of a smaller list. A sorted array splits at its midpoint into two sorted arrays. A directory contains files and smaller directory trees. When the data is self-similar, a procedure that mirrors the self-similarity is often the shortest correct thing you can write.

You have already met the reasoning that makes recursion trustworthy. Notes 01 §6.2 stated the obligations for a recursive procedure, and they are worth restating now as a designer's checklist rather than a prover's:

1. Base case. Some instances are answered directly, with no recursive call — and they are answered correctly.
2. Progress. Every recursive call is on a strictly smaller instance, so the base case is always reached.
3. Combination. Assuming the recursive calls return correct answers, the way you combine them produces a correct answer for the whole.

Obligation 3 contains the skill that separates people who can write recursion from people who trace it miserably. When you design or read a recursive procedure, you do not follow the call downward — you take the recursive leap of faith: assume the call on the smaller instance simply works, exactly as its specification says, and check only that the combination is right. This is not wishful thinking; it is the inductive hypothesis from Notes 01, worn as a design habit. Tracing the whole call tree is what the machine does. Trusting the specification of the smaller call is how humans design.

def factorial(n):
    """Return n! = n · (n−1) · … · 1.

    Precondition:  n is an integer, n >= 0.
    Postcondition: result == n!  (with 0! == 1).
    """
    if n == 0:                      # base case, answered directly
        return 1
    return n * factorial(n - 1)     # smaller instance + combination

def binary_search_rec(A, target, lo, hi):
    """Return an index of target in A[lo..hi], or None if absent.

    Precondition:  A is sorted; 0 <= lo and hi <= len(A) - 1.
    Postcondition: result is a valid index of target in A[lo..hi],
                   or None if target does not occur there.
    """
    if lo > hi:                     # base case: empty range
        return None
    mid = (lo + hi) // 2
    if A[mid] == target:
        return mid
    elif A[mid] < target:
        return binary_search_rec(A, target, mid + 1, hi)
    else:
        return binary_search_rec(A, target, lo, mid - 1)

Read binary_search_rec with the leap of faith and it becomes three lines of thought. Base: an empty range cannot contain the target, so None is right. Progress: each call's range is at least one element smaller. Combination: the midpoint comparison, plus the sortedness precondition, guarantees the target can only live in the half we recursed into — so the child's answer, whatever it is, is the answer. No trace required. That is the entire correctness argument, and you wrote its iterative twin's invariant last week.

Section 2The call stack

Before we price recursion we should be honest about how the machine runs it, because the mechanism has costs of its own. Every function call pushes a frame onto the call stack: the parameters, the local variables, and where to resume when the call returns. A recursive procedure with many live calls holds many frames at once — the chain from the outermost call down to wherever work currently is. Two consequences follow immediately.

• Depth is memory. The space cost of a recursion is Θ(maximum stack depth), on top of whatever the algorithm allocates deliberately. A recursion n deep spends Θ(n) memory even if it computes almost nothing.
• Depth is bounded. Python caps the stack at roughly a thousand frames by default and raises RecursionError beyond it — the polite version of the crash you watched in Notes 01's runaway recursion. The cap is adjustable (sys.setrecursionlimit), but a recursion whose depth is Θ(n) on large inputs usually wants to be rewritten as a loop, or driven with an explicit stack of your own. Python, unlike some languages, does not optimize tail calls; the frames are always real.

Now the demonstration. Naive Fibonacci is the canonical example of recursion's other hidden cost — not depth, but count:

def fib(n):
    """Return the n-th Fibonacci number.

    Precondition:  n is an integer, n >= 0.
    Postcondition: result == F(n), where F(0)=0, F(1)=1,
                   and F(n) = F(n−1) + F(n−2).
    """
    if n < 2:                        # two base cases
        return n
    return fib(n - 1) + fib(n - 2)

All three obligations hold — this procedure is perfectly correct. Step it below and watch what correctness fails to promise. The stack grows down the leftmost chain, unwinds, regrows; and the counter on the right records something alarming: the same subproblems being solved again, and again, and again.

Let the run finish and read the chips. For fib(6): twenty-five calls to produce the number 8 — fib(2) computed five times, fib(1) computed eight times, each recomputation oblivious to the others. The call count obeys C(n) = C(n−1) + C(n−2) + 1, which grows like the Fibonacci numbers themselves: exponentially, Θ(φⁿ) with φ ≈ 1.618. Move the selector to fib(8) and watch the total climb; every +2 on the argument roughly e-fold-ish multiplies the work. Meanwhile the stack depth — the other statistic — never exceeds n. Exponential time, linear space.

Section 3From code to recurrence

Loops let us count directly; recursion does not, because the cost of a call depends on the cost of smaller calls — which is circular. The instrument that tames the circularity embraces it:

Extracting the recurrence from code is a four-step recipe, and it is nearly mechanical:

1. Declare the variable. T(n) = worst-case cost on instances of size n — and say what "size" means for this problem.
2. Price the local work: everything the body does besides the recursive calls — the splitting, the testing, the combining.
3. Add the recursive calls at their sizes: each call on an instance of size m contributes T(m).
4. Record the base case — almost always T(constant) = Θ(1).

Applied to binary_search_rec: local work is Θ(1) — one midpoint, one comparison — and there is one recursive call on about half the range. Applied to factorial: Θ(1) local work, one call on n−1. For the third example, here is the silhouette of an algorithm you will meet properly on Tuesday — for now, only its cost structure matters:

And one more with a different personality — the Tower of Hanoi, moving n disks legally between three pegs:

def hanoi(n, src, dst, spare):
    """Print the moves that shift n disks from src to dst, legally.

    Precondition:  n >= 0; disks on src are stacked small-on-large.
    Postcondition: the printed moves transfer the n disks to dst
                   without ever placing a larger disk on a smaller.
    """
    if n == 0:
        return
    hanoi(n - 1, src, spare, dst)      # T(n−1)
    print(src, "→", dst)               # Θ(1)
    hanoi(n - 1, spare, dst, src)      # T(n−1)

Collect all five. Each row is nothing but the recipe applied once — and notice how much of the algorithm survives into its equation:

Section 4Solving by unrolling

A recurrence is a compressed sum; the most elementary way to solve one is to decompress it. Substitute the recurrence into itself until the pattern shows, run the pattern down to the base case, and add up everything shed along the way. Three unrollings below cover the three most important personalities — read each until the "pattern" line feels inevitable, because on Thursday you will be asked to produce lines like it unprompted.

One call, shrinking by subtraction

Factorial, and every recursion that peels one element per call with constant glue, is a loop in disguise: linear. (With linear glue instead — T(n) = T(n−1) + cn — the shed terms form the triangular sum from Notes 02 §4 and the answer is Θ(n²); that is the check question below.)

One call, shrinking by division

Binary search, certified — the halving loop of Notes 02 and this recurrence are the same argument in two costumes. Note where the logarithm comes from: it is the number of times you can halve n before hitting the base case, nothing more mysterious than that.

Two calls, shrinking by division, linear glue

The line worth staring at is the middle one: doubling the number of subproblems exactly cancels the halving of their size, so every layer of the unrolling costs the same cn. A perfectly balanced payroll, log₂ n layers deep. This is the sort silhouette's equation, and Θ(n log n) is why next week's merge sort earns its keep.

Two calls, shrinking by subtraction

Hanoi — and the sharpest lesson of the section, best seen by comparing this unrolling with the previous one. Both double the number of subproblems per level. The difference is entirely in what shrinks: dividing the size gives the doubling only log₂ n levels to compound, subtracting gives it n. Doubling tamed by halving is n log n; doubling fed by mere subtraction is 2ⁿ. (For Hanoi the exponential is not a flaw of the algorithm but a fact of the problem — the puzzle provably requires 2ⁿ − 1 moves — which is a useful reminder that a lower bound on the problem excuses any algorithm that merely matches it.)

Section 5Recursion trees

Unrolling is algebra; the recursion tree is the same computation as a picture, and the picture generalizes better. For a recurrence of the form T(n) = a·T(n/b) + f(n) — a subproblems, each a b-th of the size, f(n) of local glue — draw the calls as a tree and bill each node for its local work only:

• The root is the outermost call: cost f(n), with a children.
• Level i holds aⁱ nodes, each working on an instance of size n/bⁱ, so the level's total bill is aⁱ · f(n/bⁱ).
• The depth is log_b n — how many times b divides n before instances become constant-sized.
• The leaves — the base cases — number a^{log_b n}, which a logarithm identity rewrites as n^{log_b a}. Remember that exponent; it is about to run the whole show.

T(n) is the sum of the level bills, and here is the insight that turns a page of algebra into one question. For polynomial glue f(n) = nᵏ, consecutive level bills differ by a constant factor: each level has a× the nodes, each doing (1/bᵏ)× the work, so the bills form a geometric series with ratio r = a / bᵏ. Geometric series have exactly three behaviors, and each one is a running-time verdict:

Three quick sightings before you drive it yourself. The sort silhouette, 2T(n/2) + n: r = 2/2¹ = 1, every level bills cn — the balanced payroll of §4, now visible as the middle row. T(n) = 2T(n/2) + n²: r = 2/4 = ½, the level bills fall n², n²/2, n²/4, … and the whole tree costs at most 2n² — the root essentially is the cost, Θ(n²). T(n) = 4T(n/2) + n: r = 4/2 = 2, the bills grow n, 2n, 4n, … until the leaves — all n^{log₂ 4} = n² of them — dominate: Θ(n²). Same answer as the previous example, reached from the opposite end of the tree; the tree tells you not just the class but where the time goes, which is design information. A root-heavy algorithm wants its glue optimized; a leaf-heavy one wants its base case optimized, or fewer subproblems.

Section 6The substitution method

Trees and unrollings find answers; the substitution method certifies them. It is induction — the same induction as Notes 01 §6.2 — aimed at a bound instead of at correctness, and the workflow is: guess the answer (usually from a quick tree), then prove T(n) ≤ c·(the guess) by strong induction, keeping the constant honest. One full worked example, because there is a subtlety worth catching live.

Notice what the proof needed: room. We did not just barely squeeze under the bound — we landed under it with c·n − n to spare, and that slack is what absorbed the "+ n" of glue. When an attempted substitution proof keeps almost working, the standard fix is to strengthen the guess by subtracting a lower-order term (try proving T(n) ≤ c·n·log₂ n − d·n) — counterintuitively, a stronger claim can be easier to prove, because the induction hands you a stronger hypothesis too.

Section 7The Master Theorem

Section 5 ended with one question deciding everything: for T(n) = a·T(n/b) + f(n), compare the glue f(n) against the leaf count n^{log_b a} and see which one wins — or whether they tie. The Master Theorem is that observation, promoted to a theorem and hardened against the cases where f is not a clean power. Call W(n) = n^{log_b a} the watershed; the theorem is a three-way comparison against it.

Do not memorize this as three arbitrary formulas — you already own the picture. Case 1 is the tree with growing level sums (leaves dominate), case 2 is the balanced payroll (every level equal, log n levels), case 3 is the shrinking series (root dominates), and the ε's and the regularity condition are the lawyers' language making "genuinely smaller / genuinely bigger / well-behaved" precise. When f(n) = nᵏ, everything collapses back to the ratio test: k versus log_b a decides the case, the polynomial gap is automatic, and regularity always holds. Two applications in full sentences, then a battery in table form:

The sort silhouette, T(n) = 2T(n/2) + n. Watershed: n^{log₂ 2} = n. The glue is Θ(n) — exactly the watershed. Case 2: T(n) = Θ(n log n). (With f = Θ(W), no ε is needed; ties are decided without lawyers.)

T(n) = 2T(n/2) + n². Watershed: n. The glue n² is polynomially larger — ε = 1 works. Regularity: a·f(n/b) = 2·(n/2)² = n²/2 ≤ ½·f(n) ✓. Case 3: T(n) = Θ(n²). The recursion is a rounding error on the root's own bill.

Section 8When the theorem is silent

The Master Theorem is a lookup table for one specific family — constant a of equal-size subproblems of size n/b with well-behaved glue. Outside the family it says nothing at all, and recognizing "outside" on sight matters as much as applying the theorem inside. The usual escapes, with the tool that handles each:

• Shrink by subtraction. T(n) = T(n−1) + n has no n/b — the theorem does not parse it. Unroll instead: the triangular sum, Θ(n²), as in the §4 check. Every subtract-and-conquer recurrence belongs to §4, not §7.
• Unequal subproblems. T(n) = T(n/3) + T(2n/3) + n splits unevenly, so no single b exists. The recursion tree still works beautifully: every level bills at most n, and the tree's deepest branch — the one shrinking by only a third each step — has depth log_3/2 n = Θ(log n). Total: O(n log n), and a matching Ω from the levels near the top that do bill essentially the full n. This exact shape — "unequal but bounded-fraction splits still give n log n" — is the reason next week's quicksort survives imperfect pivots.
• A gap that is not polynomial. T(n) = 2T(n/2) + n log n: the glue exceeds the watershed n by only a log factor — no ε > 0 makes n log n = Ω(n^1+ε). Cases 1–3 all fail to match. The extended case 2 (fold above) answers Θ(n log² n); the basic theorem alone is simply silent, and writing "case 3, Θ(n log n)" is the classic wrong answer.
• a is not a constant. T(n) = n·T(n/2) + n has a growing number of subproblems; the theorem's premises fail before any comparison happens. Trees or substitution, from scratch.
• Regularity failures. Deliberately oscillating glue can satisfy case 3's size condition yet flunk a·f(n/b) ≤ c·f(n). Rare in practice, but it is why case 3 carries the extra clause, and why quoting case 3 without checking it loses a point in this course.

Section 9Before next session

Next week the machinery earns its keep. Insertion sort, merge sort, and quicksort — specified, proved, priced with this week's tools, and raced against each other with Notes 02's harness. Merge sort is T(n) = 2T(n/2) + cn; quicksort is the unequal-split story of §8 with a randomized twist; and the crossover between them at small n is the one you explored in Notes 02's last demonstration. It all connects. That is Notes 04.