"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
The most famous cautionary tale: naive recursive Fibonacci, fib(n) = fib(n−1) + fib(n−2). Draw its tree — each call spawns two children that barely shrink (by 1 and 2), so the tree is enormous and bushy: about 2ⁿ nodes. fib(40) makes over a billion calls. Worse, look closely and you'll see the same values computed again and again — fib(3) appears in dozens of places, each time recomputed from scratch. The tree is fat with redundant work. That redundancy is the catastrophe: an exponential algorithm for something that should be trivial.
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.
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
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.