Memoization (Fibonacci) — every question, written out
The same recursion, plus a Map — and an exponential call tree collapses to a linear one. Memoization, watched happening. The gentlest doorway into DP.
Read the memoization (fibonacci) explanation and watch it run
Naive `fib(n)` is exponential. What is the exponent, and why that one?
Complexity derivation
About φⁿ — the call count obeys Fibonacci’s own recurrence, so it grows like the sequence
Counting calls gives calls(n) = calls(n−1) + calls(n−2) + 1 with both base cases at 1 — Fibonacci’s own recurrence, so the count grows like φⁿ with φ ≈ 1.618. It falls short of 2ⁿ precisely because one branch terminates a level early. Prism prints both totals before the tree grows: 41 nodes naked against 13 memoised for fib(7).
See it run — The opening note counts both trees: 41 nodes without the cache, 13 with it.
With the memo in place, what does `fib(n)` cost in time and in space?
Complexity derivation
O(n) time and O(n) space — one computation per distinct argument, one entry each
There are n − 1 non-base arguments, the cache guarantees each is computed exactly once, and the work inside one computation is a single addition — hence O(n) time. Space is the memo’s n entries plus the O(n) stack the leftmost spine builds before anything returns. That stack is the half people forget, and it is what makes bottom-up preferable once n gets large.
What is the general cost formula for a memoised recursion, and why is it the bridge to DP?
Complexity derivation
Distinct states × work per state — the same sentence prices every DP table
A memoised function computes each reachable state once, so the total is states × per-state work: Fibonacci is n × O(1), memoised edit distance is n·m × O(1), memoised grid paths the same. Every "why is this table O(n·m)?" answer is that sentence with different nouns. Once you can name the state space you can price the algorithm before writing a line of it.
With memoisation, how many nodes does the call tree for `fib(n)` actually hold?
Complexity derivation
About 2n — one computed node per argument, plus one cached stub for each
The leftmost spine computes `fib(2)` through `fib(n)` once each, and each of those also issues a second request that lands as a childless stub — 2n − 1 nodes in total. For fib(7) the drawing holds 13 nodes against the naked tree’s 41; for fib(9) it is 17 against 109. The gap between those two pairs is the difference between linear and exponential, drawn to scale.
See it run — The root resolves at last — inside a tree of thirteen nodes rather than forty-one.
The second request for `fib(2)` arrives. What becomes of the subtree it would have grown?
Trace prediction
It never exists: the cached value returns at once and the node stays a childless stub
The check sits before the recursive calls, so a hit returns in O(1) and the recursion never descends. The exponential subtree the naked version would have grown here simply never comes into being, and the ghosted stub is all that remains of it. Not "computed faster" but never born, which is why the saving is exponential rather than constant.
See it run — The second f(2) is marked as a stub — no children, no work, no subtree.
When in the run does the FIRST cache hit occur, and what does the answer say about the shape?
Trace prediction
Only after the leftmost spine has descended all the way to the base cases
Depth-first order drives the recursion all the way down the `n − 1` branch to the base cases before a single value is memoised, and the cache then fills as calls return. The first hit lands when `fib(4)` asks for `fib(2)` — step 37 of a seventy-three step run. Everything before it is unavoidable work; everything after it is savings.
See it run — The first hit, and how far down the spine the run had to travel before earning it.
State the memo’s invariant so that the correctness proof follows from it.
Invariant identification
Every entry in the memo is correct, and every argument is computed at most once
Correctness follows by induction on completed computations: a value is written only once its two sub-answers returned, and those were base cases or, inductively, correct entries. The at-most-once half follows from checking before computing, and together the two halves give the right answer in O(n) work. Note what the invariant never mentions — any particular order of evaluation.
What does memoisation NOT require that a bottom-up table does?
Invariant identification
A dependency order worked out in advance — the recursion discovers its own
A table must be filled in an order where every cell’s inputs are already final, which means analysing the recurrence before writing the loops. Memoisation inherits that ordering free from the call stack, and it visits only the states that are actually reachable — a real advantage when the state space is sparse or awkwardly shaped. The price is the stack, which is why dense rectangular problems still tend to go bottom-up.
Memoised recursion or a bottom-up table — what actually decides between them?
Comparison
Stack against locality: the memo fills only reachable states, the table needs no frames
Both compute each state once, so the asymptotics match and the decision is made elsewhere. Memoisation keeps the natural recursive shape, touches only the states the problem reaches, and spends O(depth) of stack; tabulation needs no stack and has better constants, but fills every cell and forces you to work out the fill order. Sparse or awkward state spaces favour the memo, dense rectangular ones the table.
For Fibonacci specifically, why is even the O(n) memo more than the problem needs?
Trade-off & selection
Only the previous two values are ever read, so two variables replace the whole map
The recurrence reaches back exactly two positions, so once `fib(k)` is known everything below `k − 1` is dead storage. Two rolling variables give O(n) time in O(1) space, which is the expected answer after "memoise it" — offer it before being asked. The general form of that observation is what shrinks DP tables to a single row.
Is linear time the end of the line for Fibonacci, or is there something faster still?
Comparison
Fast doubling, or 2×2 matrix power, gets there in O(log n) multiplications
The doubling identities express `fib(2k)` and `fib(2k+1)` in terms of `fib(k)` and `fib(k+1)`, so each step halves the index and log n steps suffice; matrix exponentiation is the same idea in different clothing. The honest footnote is that the numbers themselves grow linearly in digit count, so O(log n) multiplications is not O(log n) bit operations. Naming both the method and that caveat is what makes the answer sound finished.
When is wrapping a recursive function in a cache pure overhead?
Trade-off & selection
When subproblems do not overlap: every call has a fresh argument, so nothing ever hits
A cache pays exactly when the same arguments recur; quicksort, mergesort and tree traversals partition their input, so every call sees a distinct subproblem and the map stores everything while hitting nothing. Overlap and purity are the two conditions that make memoisation both legal and worthwhile. Miss purity and the cache lies; miss overlap and it merely wastes memory.
A memoised function also reads a mutable board that changes between calls. What goes wrong?
Edge case reasoning
The cache hands back answers computed for a world that no longer exists
A memo assumes the answer is a function of the key alone, so any dependence on state outside the arguments must be removed or folded into the key. Otherwise a later call with the same arguments but a different board silently receives the earlier board’s answer. Purity first and cache second — and where the state genuinely matters, it belongs in the key.
You memoise `fib` properly and then call it with n = 100,000. What happens?
Edge case reasoning
It overflows the stack — the memo removes repeated work, not the n-deep descent
The first call descends from `fib(n)` to the base cases before anything returns, so the stack reaches depth n whether or not a cache exists. At n = 10⁵ that exceeds the default stack in most runtimes and the program dies before the memo has done any good at all. Bottom-up iteration — or two rolling variables here — is the fix, not a larger stack.
See it run — A dozen steps in, the run is still descending: f(7) → f(6) → … → f(1), nothing returned yet.
A memoised board search caches on position alone and returns wrong answers. What is the likely fault?
Code diagnosis
The key omits state that changes the answer, so two different situations collide
A key must capture everything that can change the answer — the position plus the visited set, the remaining budget, or whatever else distinguishes two visits to the same square. Too little in the key and unrelated situations share an entry; too much and nothing ever hits, which is merely slow rather than wrong. "What exactly is my state?" is the question that fixes both the correctness and the complexity of a memoised search.
Someone writes `function fib(n) { const memo = new Map(); ... }` and reports that memoisation does nothing. Why not?
Code diagnosis
A fresh map per call is never shared, so every recursive call starts from an empty cache
Each invocation builds its own map, writes one entry into it and throws it away, so no call ever benefits from another’s work and the call count stays Fibonacci-shaped. The cache has to outlive the recursion: take it as a parameter created once at the top, close over it, or use a decorator that owns it. The symptom is distinctive — correct answers, and no speed-up whatsoever.
Explain memoisation to someone who does not code. Say it out loud before revealing.
Explain it plainly
Suppose I ask you how many rabbits there are in month fifty, and the rule is that each month equals the two months before it added together. Follow the rule literally and you phone two friends about months forty-nine and forty-eight; they each phone two friends; and within a dozen rounds half the country is being asked about month three, over and over, by people with no idea anyone else has asked. That is the naive version, and it takes longer than the universe has been running. Now hang a whiteboard in the hall: before you phone anybody, look at the board, and whenever you get an answer, write it up. The first person asked about month three does the work and writes 2; every later request for month three takes a second — and, crucially, none of the people they would have phoned ever get phoned at all. An entire tree of pointless calls stops existing rather than merely going faster. Fifty months, fifty numbers on the board, done. Two places the story cheats. It works only because the answer to ‘month three’ never changes; if rabbits could die overnight, yesterday’s number on the board is a lie, and a cache of lies is worse than no cache at all. And it hides that the very first chain of calls still runs fifty people deep before anyone can answer, which inside a real computer is fifty thousand frames stacked up waiting on each other — and past a point, a crash.
The listener should grasp that the saving is not "faster work" but "work that never happens". A strong answer lands the pruning, then names the two conditions — the answer must not change, and the same questions must actually recur — and admits that the first descent still happens in full.