The Recursion Tree: Seeing the Cost

"To find what a recursion costs, draw it as a tree of calls. The tree's shape — how wide it branches, how deep it goes — IS the complexity. And a tree that recomputes the same branches over and over is the loudest signal in algorithms that you're leaving easy speed on the table."

Recursion Makes a Tree

Every recursive computation traces out a recursion tree: the root is the original call, its children are the calls it makes, their children are the calls those make, down to the base cases at the leaves. To analyze the cost, you read the tree: how many children does each node spawn (the branching), how fast does the problem shrink (the depth), and how much work happens at each node? Multiply it out and you have the complexity. The tree turns 'how expensive is this recursion?' from a mystery into a drawing.

The Fibonacci Catastrophe

Naive recursive Fibonacci makes Θ(φⁿ) calls, with O(2ⁿ) as a looser upper bound. Counting base calls as the code below does, fib(40) makes about 331 million calls, not more than a billion. The important fact is repeated evaluation of the same states.

Pruning the Tree: the DP Signal

Here's the payoff that sets up the entire next track. If you remember each fib(k) the first time you compute it (in a dict), every later request is an instant lookup instead of a whole recomputed subtree. The fat exponential tree collapses into a thin line of n unique computations — O(2ⁿ) becomes O(n) from caching alone. This is memoization, and the recognition that 'my recursion tree recomputes the same subproblems' is the single loudest signal that dynamic programming (the next track) applies. When you draw a recursion tree and see repeated subtrees, you've found free speed.

Draw the recursion tree: branching factor × work per level reveals the complexity. Two-way branching that barely shrinks (naive Fibonacci) is exponential, O(2ⁿ). Repeated subtrees mean redundant work — caching them (memoization) collapses the tree and is the signal that dynamic programming applies.

Not All Trees Are Fat

Branching isn't automatically bad — it's branching without enough shrinking that explodes. Merge sort also branches two ways, but each call works on half the data, so the tree is only log n deep and each level totals O(n) work → O(n log n), perfectly fine. The difference is the shrink rate: halving (merge sort) gives a short tree; shrinking by a constant while branching (Fibonacci) gives an exponential one. The master theorem formalizes this branching-vs-shrinking analysis for divide-and-conquer — but drawing the tree gives you the intuition first.

Pippa's Confession

My naive fib(45) hung my terminal, and I genuinely thought I'd written an infinite loop. Dad had me draw the call tree for fib(5) on paper — and there was fib(2), computed five separate times. The redundancy was visible the instant I drew it. One dict to cache results, and fib(45) returned instantly. I learned to draw the tree whenever a recursion feels slow; the repeated subtrees jump off the page and tell you exactly where the wasted work is.

Code

The Fibonacci tree explosion, tamed by caching·python

# NAIVE Fibonacci: Θ(phi^n) calls, with O(2^n) as an upper bound.
calls = 0
def fib(n):
    global calls; calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # TWO children, barely shrinking -> fat tree

fib(20); print("fib(20) made", calls, "calls")   # 21,891 calls including base calls
# The same subproblems (fib(3), fib(4), ...) are recomputed thousands of times.

# MEMOIZED: remember each result -> the tree collapses to O(n).
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_fast(n):
    if n < 2:
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)

print(fib_fast(100))   # instant — each fib(k) computed ONCE, then cached
# Same recursion, one cache: O(2^n) -> O(n). 'Repeated subtrees' was the DP signal.

Exercise

Draw (or list) the recursion tree for naive fib(5). How many times does fib(2) get computed? Roughly how many total calls? Then contrast: why does merge sort, which also branches two ways, NOT explode exponentially the way Fibonacci does — what's different about how fast each shrinks the problem?

Hint

fib(5) → fib(4)+fib(3) → … fib(2) appears 3 times, ~15 total calls; the count roughly doubles each step → exponential. Merge sort branches two ways too, but each call halves the data, so it's only log n deep with O(n) per level (O(n log n)). Halving vs shrinking-by-1 is the whole difference.

Recursion Makes a Tree

The Fibonacci Catastrophe

Pruning the Tree: the DP Signal

Not All Trees Are Fat

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0