Recursion, Recurrences & the Master Theorem — Algorithms Course

What you'll learn

Recursion — a function that calls itself on a smaller input — is the engine behind divide & conquer, backtracking, and dynamic programming. Here you'll see exactly how it runs on the call stack, and learn to turn a recursive algorithm into a recurrence you can solve for its Big-O.

By the end you'll be able to:

Break a problem into a base case and a recursive case
Trace how the call stack grows and unwinds
Write a recurrence relation for a recursive algorithm
Solve common recurrences with the Master Theorem

Anatomy of a recursion

Every correct recursion has two parts: a base case that stops the recursion, and a recursive case that makes progress toward it. Miss the base case (or fail to shrink the input) and you get infinite recursion — a stack overflow. Here is the classic factorial:

Language

factorial.py

def factorial(n):
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)   # recursive case

The call stack

Each call gets its own stack frame holding its arguments and where to resume. Calls pile up until the base case, then unwind — each returning a value to the call that's waiting for it. Step through factorial(4) and watch the stack grow to four frames, then collapse as values flow back up:

factorial(4) on the call stack

factorial(4)

Call stack

fact(4)

1/8Call fact(4). It needs fact(3) before it can multiply.

Calls push down to the base case, then pop back up carrying results.

Watch out

The stack has a limited depth. Deep recursion (say, n = 10⁶) can overflow it — a reason we sometimes rewrite recursion as iteration, or lean on tail-call optimization where the language provides it.

Writing a recurrence

To find a recursive algorithm's complexity, write T(n) — its cost on input n — in terms of the cost on smaller inputs. Factorial does O(1) work and one call on n - 1:

T(n) = T(n − 1) + O(1) ⇒ O(n)

Divide & conquer algorithms split into several subproblems. Merge sort makes two calls on half the input plus O(n) to merge:

T(n) = 2·T(n/2) + O(n) ⇒ O(n log n)

You could unroll each into a recursion tree and sum the levels — or use a shortcut for the common shape.

The Master Theorem

For recurrences of the form T(n) = a·T(n/b) + O(nᵈ) — a subproblems, each of size n/b, plus O(nᵈ) to split and combine — the answer depends only on how d compares to log_b(a):

Case	Condition	Result	Example
`1`	`d < log_b a`	`Θ(n^{log_b a})`	Karatsuba (a=3, b=2, d=1)
`2`	`d = log_b a`	`Θ(nᵈ log n)`	Merge sort (a=2, b=2, d=1)
`3`	`d > log_b a`	`Θ(nᵈ)`	Split-heavy combine step

Merge sort: a=2, b=2, d=1, and log₂2 = 1 = d → case 2 → Θ(n log n). Binary search: a=1, b=2, d=0, and log₂1 = 0 = d → case 2 → Θ(log n).

Key idea

The Master Theorem is a lookup table for divide & conquer. Identify a, b, and d, compare d with log_b a, and read off the answer — no tree-summing required.

Recap & quick check

Key takeaways

Recursion needs a base case (to stop) and a recursive case (to make progress).
Each call gets a stack frame; calls push down to the base case, then pop back up.
Model a recursion's cost with a recurrence T(n) in terms of smaller T's.
The Master Theorem solves T(n) = a·T(n/b) + O(n^d) by comparing d with log_b a.
Merge sort → Θ(n log n); binary search → Θ(log n).

Quick check

1. What are the two required parts of a correct recursion?

2. What does the recurrence T(n) = 2·T(n/2) + O(n) solve to?

3. In the Master Theorem, which quantity do you compare with d?

4. Why can deep recursion be dangerous?

Recursion that works isn't the same as recursion you've proven works. Next we make correctness rigorous. Next up: Module 4 — Correctness: Loop Invariants & Induction.