Fibonacci & Memoization

Memoization is the technique of caching a function's results so repeated calls with the same argument return instantly; the Fibonacci sequence — fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1 — is its canonical demonstration. Plain recursion recomputes subproblems exponentially often; one cache collapses the cost from roughly O(2ⁿ) to O(n).

Picture a clerk computing a subtotal from scratch every single time someone asks, even when they asked five minutes ago. That clerk is naive recursion. Memoization hands the clerk a notebook: compute once, write it down, and from then on answering is just looking it up. Dynamic programming is the discipline of using that notebook on purpose — and this lesson shows the same computation three ways, so you can watch the wasted work appear and then vanish.

How Memoization Works

Naive recursion (the default view) writes the recurrence directly as a function and builds a recursion tree. fib(6) calls fib(5) and fib(4); each splits again, down to the base cases fib(1) and fib(0). Nothing is remembered, so an entire subtree like fib(4) gets rebuilt from scratch every time it is requested. The clerk has no notebook; every question restarts the whole calculation.

Top-down memoization keeps the identical recursion and adds the notebook: a memo dictionary. The first time fib(4) is computed, the result is stored. Every later request becomes an O(1) lookup — a cache hit — and that whole subtree is never expanded again. The tree gets pruned to a thin spine.

Bottom-up tabulation throws away the recursion and fills the notebook in order. A table dp[] grows left to right: dp[0] = 0, dp[1] = 1, then each dp[i] = dp[i-1] + dp[i-2]. Every cell is written exactly once, reading only the two cells before it. No call stack, no waiting children — by the time you need an answer, you have already written it.

All three agree on the answer; they differ only in whether the fact "once fib(k) is known, it never needs computing again" gets exploited. Naive ignores it, memoization exploits it lazily, tabulation exploits it eagerly.

Fibonacci Step by Step

The default run is naive recursion with n = 6, so the target is fib(6) = 8.

1. Call fib(6). It needs fib(5) + fib(4) and recurses into fib(5) first.
2. Drill down the left spine — fib(5) → fib(4) → fib(3) → fib(2) — until it bottoms out at fib(1) = 1 and fib(0) = 0.
3. Combine upward. With both children resolved, a combine beat does the arithmetic — fib(2) = 1 + 0 = 1 — and a separate return beat commits the value and hands it up. Then fib(3) = 1 + 1 = 2, fib(4) = 2 + 1 = 3, fib(5) = 3 + 2 = 5.
4. Recompute fib(4) from scratch. Back at the root, fib(6) still needs its second child — and the clerk has no notebook, so the entire fib(4) subtree (nine calls) is rebuilt node by node. The status line calls it out: this argument has been seen before, and naive recursion does not care.
5. Finish. fib(6) = 5 + 3 = 8, after 25 calls in total.

Switch the mode selector to Memoization and the same fib(6) resolves in 11 calls: the second requests for fib(2), fib(3), and fib(4) arrive as cache-hit stubs that read straight out of the memo panel instead of growing subtrees. Switch to Bottom-up and there is no tree at all — the table fills 0, 1, 1, 2, 3, 5, 8, three beats per cell: focus the empty slot, read the two cells before it, write the sum.

On screen, the tree reveals one node per call rather than appearing all at once; the two children light up as summands on each combine beat, and a value chip turns the node green when it returns. In memoized mode the left-hand memo panel is the notebook itself — a row fills on every store, and flashes on every hit. The running call counter in the header is the whole argument in one number: 25 versus 11.

Time and Space Complexity

The exponential base is the golden ratio φ ≈ 1.618 — the call count of naive fib(n) grows like the Fibonacci numbers themselves, which is a pleasingly self-referential way to be doomed. The leap to O(n) time is the entire point of dynamic programming: it is the difference between fib(50) finishing instantly and not finishing at all.

Edge Cases

• n = 0 and n = 1 are base cases — they return immediately with no recursion. The lesson's slider therefore starts at n = 2, the smallest input with a real recurrence, and caps at n = 7, where the naive tree already holds 41 nodes.
• Base cases are never cache hits. The displayed code checks n < 2 before consulting the memo, so fib(0) and fib(1) never enter the notebook — there is nothing worth remembering about returning your own argument.
• Python's memo={} default argument persists across calls. Convenient here; a classic footgun anywhere the cache should not be shared.
• Large n overflows fixed-width integers in many languages long before O(n) becomes slow.

Common Mistakes

• Shipping the naive version. It is correct, it passes small tests, and it times out the moment n grows — exponential cost hides well at n = 10.
• Checking the cache before the base case. Harmless-looking, but it pollutes the memo with entries the recurrence never needed and quietly changes which line your code exits through.
• Off-by-one in the table. dp needs length n + 1, and both dp[0] and dp[1] must be written before the loop, or the first iteration reads an empty cell.
• Believing memoization changes the answer. All three approaches return the same fib(n). The notebook changes how much work the clerk does — never what the subtotal is.