Recursion trees
factorial makes one self-call, so its picture is a straight line of frames. The interesting (and dangerous) shape appears when a function calls itself twice, like the Fibonacci numbers:
- fib(0) = 0, fib(1) = 1 (base cases)
- fib(n) = fib(n-1) + fib(n-2)
Drawing every call gives a recursion tree: fib(5) calls fib(4) and fib(3), fib(4) calls fib(3) and fib(2)... Notice fib(3) appears twice already, and each copy recomputes its entire subtree from scratch.
The tree roughly doubles in size per level, so naive fib is about O(2ⁿ) calls. Drawing (or at least sketching) the recursion tree is how you see an exponential blow-up before you run anything.
Code exercise · python
Run this. The counter tallies every call. Going from fib(10) to fib(20) makes the answer 123× bigger but the CALL COUNT 123× bigger too. Exponential blow-up is not subtle.
Quiz
In the fib recursion tree, why does the SAME subproblem like fib(2) get computed many times?
Code exercise · python
Your turn. Write power(base, exp) recursively for exp ≥ 0: the base case is exp == 0 (anything to the zero is 1), and otherwise base * power(base, exp - 1).