Memoization (Fibonacci)

The problem it solves

Recursive Fibonacci is the world’s most famous wrong program. fib(n) = fib(n−1) + fib(n−2) is a correct definition and a catastrophic algorithm: the call tree doubles roughly every level, fib(50) makes forty billion calls, and every one of them is recomputing something already computed. The waste has a precise shape — the same arguments appear over and over — and that shape has a precise name: overlapping subproblems.

Memoization is the smallest possible fix: a Map from argument to answer, consulted before recursing, written after. One data structure, three lines, and the exponential tree collapses to a linear one — each distinct argument computed exactly once, every repeat answered from cache in O(1). This page uses Fibonacci because its tree is drawable, but the technique is the front door to all of dynamic programming: every DP table on this site (coin change, knapsack, LCS, edit distance) is a memoized recursion that someone flattened into iteration. Watching the cache prune the tree here is watching why those tables exist.

The intuition — and where it breaks down

The call tree tells the story better than any formula. Naked fib(6) spawns fib(5) and fib(4); the fib(5) subtree contains another entire fib(4) subtree, which contains fib(3) twice, which… every value’s subtree is duplicated wholesale inside its larger siblings. The drawing makes this painful to look at, which is the point.

Now add the memo and watch the same tree grow differently: the leftmost spine computes fib(2), fib(3), … fib(n) honestly, one each — and every second request for a value hits the cache and becomes a ghosted stub: a node with no children, standing where an exponential subtree would have been. The player’s prediction question stops on the first such hit and asks what happens to the subtree; the answer — it never exists — is the entire mechanism. Not “computed faster”. Never born.

Two conditions make this legal, and knowing them is knowing when memoization applies anywhere. The function must be pure with respect to its arguments — same input, same answer, no dependence on mutable outside state, or the cache returns stale lies. And the subproblems must overlap — if every call has distinct arguments (like quicksort’s partitions), a cache stores everything and hits nothing, pure overhead. Fibonacci is the extreme best case: n distinct arguments servicing an exponential number of requests.

Loading…

A walkthrough you can check

fib(5), memoized, tracing only what actually computes:

1. fib(5) needs fib(4), which needs fib(3), which needs fib(2), which needs fib(1) = 1 and fib(0) = 0 — base cases, free. fib(2) = 1, cached.
2. fib(3) also needs fib(1) — base case. fib(3) = 2, cached.
3. fib(4) also needs fib(2) — cache hit, first stub in the drawing. fib(4) = 3, cached.
4. fib(5) also needs fib(3) — hit, second stub. fib(5) = 5.

Count: four real computations (fib(2)…fib(5)), two cache hits, versus fifteen calls for the naked version. At n = 7 (the default) it is six computations against forty-one calls; the done-summary prints both numbers, and the two decision prompts ask you to predict each before the tree grows. The naked count follows its own Fibonacci-shaped recurrence — calls(n) = calls(n−1) + calls(n−2) + 1 — which is a genuinely satisfying thing to verify once by hand.

The invariant

Every entry in the memo is correct, and every argument is computed at most once. Induction on completed computations: a value is only written after its two sub-answers returned, and those were either base cases or — by induction — correct memo entries or correct fresh computations. The at-most-once half follows from check-before-compute: a second request for any argument finds the entry and returns without recursing.

Note what the invariant does not require: any particular order of computation. That is memoization’s practical charm over bottom-up tables — the recursion discovers its own dependency order, computes only reachable states, and needs no analysis of which cell to fill first. The price is the call stack, and both facts become trade-offs in the follow-ups.

Complexity, derived

Distinct arguments: n−1 non-base values, each computed once at O(1) internal work — O(n) time, O(n) space for the memo (plus O(n) stack for the recursion’s leftmost spine). The naked version’s count grows as the recurrence above, tightly θ(φⁿ) with φ ≈ 1.618 — the golden ratio governing its own function’s inefficiency, which is almost too poetic.

The general statement, worth having ready: memoized recursion costs (number of distinct states) × (work per state). Fibonacci: n states × O(1). Memoized grid paths: n·m states × O(1). Memoized edit distance: n·m × O(1). That formula is the bridge to DP complexity analysis — every “why is this table O(n·m)?” answer is this sentence with different nouns. (And for completeness: fib itself has an O(log n) matrix-power algorithm — memoization is the teaching answer here, not the record holder.)

What people get wrong

• Caching an impure function — one that reads a mutable board, a clock, or accumulator state. The memo returns answers from a world that no longer exists. Purity first, cache second.
• The aliasing bug in other languages: using a mutable default argument (memo={} in Python) is correct precisely because the dict persists across calls of one top-level invocation — but sharing it across unrelated invocations with different semantics is the trap; know why your language’s idiom works.
• Stack depth: memoized recursion still recurses n deep. At n ≈ 10⁵, bottom-up iteration (or two rolling variables, for Fibonacci) is the answer, not a bigger stack.
• Memoizing non-overlapping recursion — quicksort, mergesort, tree traversals: distinct subproblems everywhere, so the cache is dead weight.
• Stopping at memoization in an interview when the question wanted the O(1)-space iterative version: fib needs two variables, not a Map. Offer the upgrade.

Implementation notes

The pattern is mechanical, which is its virtue: check the cache, compute, store, return — wrap any pure recursive function this way without understanding its internals. Many languages ship it as a decorator (functools.lru_cache in Python); writing it by hand once, as here, is what makes the decorator legible.

Key design deserves one thought: the cache key must capture all arguments that affect the answer. fib(n) needs only n; a memoized DFS over a board needs the position and whatever state distinguishes revisits — get the key wrong in either direction and you have stale answers or zero hits. When arguments are ranges or pairs, the tuple-key idiom (or an n·m array standing in for the map) is the same idea with cheaper constants — and once the keys are dense integers, replacing the map with an array and the recursion with two loops is the bottom-up conversion: same states, same recurrence, no stack.

For the classic interview arc — “write fib”, “faster?”, “even faster?” — the expected ladder is: naked recursion (correct, exponential), memoized (linear), two variables (linear time, constant space), and matrix power or fast doubling (logarithmic) as the flourish. Each rung exists on this page or in its follow-ups.

The follow-up questions

Memoization or bottom-up — how do you choose? Memo: keeps the natural recursive shape, computes only reachable states, costs stack. Bottom-up: no stack, better constants and cache behaviour, but fills every state and needs the dependency order made explicit. Sparse or awkward state spaces favour memo; dense rectangular ones favour tables.

What makes a problem memoizable at all? Pure subproblems (answers depend only on arguments) that overlap (arguments recur). Miss the first and the cache lies; miss the second and it merely wastes memory.

Why is naked fib θ(φⁿ) exactly? Its call count satisfies fib’s own recurrence, so it grows as Fibonacci does — like powers of the golden ratio. The function’s cost curve is itself.

What is the O(1)-space and the O(log n) version? Two rolling variables replace the memo (only the last two values are ever needed); fast doubling / 2×2 matrix exponentiation computes fib(n) in O(log n) multiplications. Name both; derive on request.