Fibonacci with Memoization
Naive recursive Fibonacci is the standard demonstration of why some recursions are catastrophically slow, and it earns the reputation: fib(40) makes over 300 million calls to compute 41 distinct values. Memoization fixes it with three extra lines, and seeing the recursion tree before and after is the fastest route to understanding what dynamic programming actually buys you.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
vector<long long> memo;
int calls = 0;
long long fib(int n) {
calls++;
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
long long a = fib(n - 1);
long long b = fib(n - 2);
memo[n] = a + b;
return memo[n];
}
int main() {
int n = 30;
memo.assign(n + 1, -1);
cout << fib(n) << endl;
cout << calls << endl;
return 0;
}The calls counter makes the saving concrete: memoized fib(30) reports 59 calls, while deleting the two memo lines pushes the same counter to 2,692,537.
How it works, step by step
The naive tree is exponential
fib(n) calls fib(n-1) and fib(n-2), each of which branches again. The tree has roughly 1.6 to the power n nodes, and the same subproblems appear in it thousands of times — fib(5) alone is recomputed from scratch on nearly every branch.
There are only n distinct subproblems
Despite the enormous tree, the function only ever has n+1 possible arguments. The explosion is entirely redundant work, which is exactly the condition under which memoization applies.
Check the cache before recursing
The memo lookup sits above the recursive calls, so a cached value short-circuits an entire subtree. That is where the saving comes from — not from the storage itself, but from the branches that never execute.
Store before returning
Assigning to memo[n] and then returning it guarantees the value is available to every later caller. Computing the sum and returning it without storing gives you correct answers at full exponential cost, which is a bug that produces no wrong output at all.
The tree becomes a path
With memoization, each value is computed once on the way down and reused on the way back. The recursion tree collapses into a single spine of n calls with n cheap cache hits hanging off it — visible immediately if you compare the two call counts.
Complexity
Each of the n subproblems is computed exactly once and every other call is an O(1) lookup; the naive version's cost is the size of the recursion tree, which grows by the golden ratio at each level and is why fib(50) is unreachable without a cache.
Common bugs
Using 0 as the not-computed sentinel
fib(0) is legitimately 0, so a memo initialised to 0 treats a real answer as a cache miss and recomputes it forever. Worse, in problems where 0 is a common valid result, the cache silently stops working and you get exponential behaviour with correct output. Use -1, or a parallel boolean array.
Sizing the memo to n instead of n + 1
The table must be indexable at n itself. Off by one and the top-level call writes past the end of the vector — undefined behaviour that frequently appears to work because the vector has spare capacity.
Computing but not storing
return fib(n-1) + fib(n-2); with the lookup still present looks memoized and is not. The cache is read but never written, so every lookup misses. The output is still right, so nothing looks wrong until you compare step counts — running both versions in DryRun and seeing one finish in 59 calls and the other not finish at all settles it immediately.
Overflowing int at around fib(47)
Fibonacci numbers grow exponentially and pass 2 billion at index 47. With int return values you get silent wraparound to negative numbers. Use long long, and be aware that even that runs out around index 92.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What is memoization?
Caching the result of a function call so that repeating the same call returns the stored value instead of recomputing it. It applies when a function is pure — the same arguments always produce the same result — and when the same arguments recur. It turns a recursion's cost from the size of its call tree into the number of distinct subproblems.
Why is naive recursive Fibonacci so slow?
Because it recomputes the same values an exponential number of times. fib(n) branches into two calls that overlap almost entirely, producing a tree with about 1.6 to the power n nodes to compute only n distinct values. fib(40) makes over 300 million calls; memoized, it makes 79.
What is the difference between memoization and tabulation?
Memoization is top-down — you write the natural recursion and add a cache, so only the subproblems actually needed get computed. Tabulation is bottom-up — you fill a table in dependency order with loops, no recursion and no stack depth. They have the same asymptotic cost; tabulation avoids stack overflow, memoization avoids computing unreachable states.
Why initialise the memo array to -1 instead of 0?
Because 0 is a valid Fibonacci value, so it cannot double as a marker for not-yet-computed. Using it as a sentinel means fib(0) is never cached and the cache check misfires. Choose a sentinel outside the function's possible range, or keep a separate array of booleans.