Dynamic Programming: the Explosion and the Collapse
Naive fib(20) makes 21,891 calls because the same subproblems keep coming back. Hand the recursion a cache and watch the tree collapse to 39 calls.
The Explosion and the Collapse
Computing Fibonacci by the plain recurrence redoes the same work over and over: fib(20) takes 21,891 calls. Hand that recursion a place to remember answers and the same call tree collapses to 39 calls. Pick a mode, set n, and step through to feel where the cost goes.
Naive fib(8): one call per node, no memory
Every node is a fresh function call. fib(k) calls fib(k-1) and fib(k-2), and neither remembers the other's work. Step through and watch identical subtrees appear again and again. The repeated arg fib(2) is highlighted; count how many times it recomputes.
Why the count drops from exponential to linear
Naive recursion grows as Fibonacci itself, so doubling the work for a few extra n. Memoization and tabulation both touch each subproblem once, so the count rises in a straight line. Read the two curves on a log scale: a straight line that keeps climbing is exponential, the nearly flat line is linear.
The two ingredients
Dynamic programming pays off when a problem has overlapping subproblems (the same smaller question is asked many times) and optimal substructure (the answer is built from answers to those smaller questions). Fibonacci has both: fib(k) appears all over the naive tree, and it is always fib(k-1) + fib(k-2). Memoization is top-down caching, you keep the recursion and remember answers as you meet them; tabulation is bottom-up, you drop recursion and fill a table in dependency order. Either way each subproblem is solved once instead of once per appearance, which is exactly why the call count falls from exponential to linear.
fib(0) = 0, fib(1) = 1, fib(k) = fib(k-1) + fib(k-2). Call counts are measured by instrumenting the actual recursion; the naive tree is capped at n = 12 so it stays drawable.