The same answer, computed again and again

2,692,537 calls to compute 31 distinct values.

Naive fib(n) = fib(n-1) + fib(n-2) does not recurse down a chain — it recurses into a tree. Click any node to light up every place that value is recomputed.

Calls made
15for fib(5)
Distinct values
60 through n
Wasted
960% of the work
Answer
5fib(5)
Recursion tree of the naive Fibonacci function

Every node is one call. Click one to highlight all calls with the same argument.

base case (0 or 1) selected, recomputed skipped once memoized
Measured by instrumenting the real C++ function.
nCallsDistinctWith memoSpeed-up

What the tree is telling you

Set n to 9 and look at the width. The tree has 109 nodes but only 10 distinct arguments. Every subtree hanging off a repeated node is an exact copy of one drawn elsewhere — same input, same output, computed from scratch.

Now switch on memoize. Nothing about the recurrence changes; the second time a value is asked for, the stored answer comes back and the whole subtree underneath disappears. What is left is a thin spine of 2n - 1 calls.

The gap between distinct subproblems and calls made is the whole of dynamic programming.

That property has a name: overlapping subproblems. It is one of the two things that make a problem a DP problem, and it is why Week 5 turns recursions into memoized recursions before touching a table.

Why the stack is only O(n)

The tree is exponentially wide, but only one root-to-leaf path is ever open at a time — fib(n-1) finishes completely before fib(n-2) starts. So time is O(1.618n) while space stays O(n). Wide tree, shallow stack.