Remembering the sub-answers
A Socratic walk-through of remembering the sub-answers — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why does writing down answers you have already worked out turn an impossible calculation into an instant one?
The textbook definition of the Fibonacci numbers translates into three lines of code, and those three lines will not compute the fiftieth term while you wait. Add a small cache — a dictionary keyed by the argument — and the same three lines return instantly.
Nothing about the recursion changed. The same additions in the same order produce the same answer. So where did the enormous cost go, and why was it there in the first place?
Reasoning it through
REASONING #Count, rather than reason about, the work. To get the fiftieth term the naive version calls itself for 49 and 48. The call for 49 calls for 48 and 47 — so 48 is now being computed twice, independently, by two branches that will never learn of each other. Each of those recomputes 47, and so on downward.
How bad does that get? The number of calls needed for term n is exactly twice the (n+1)th Fibonacci number minus one — because the recursion tree's leaves are all the ones and zeros that sum to the answer. For n = 50 that is 40,730,022,147 calls to produce a number that is the sum of fifty additions. Better than four billion per cent overhead.
Now ask the diagnostic question. How many distinct calls are there? The argument is a single integer between 0 and 50, so there are only fifty-one distinct questions being asked. Forty billion calls, fifty-one distinct answers. The work is not hard; it is repeated.
That gap is the whole phenomenon, and it has a name: overlapping subproblems. Memoization simply refuses to answer the same question twice. Keep a table; on entry, look up the argument; if it is present, return it; otherwise compute, store, and return. Each distinct subproblem is now solved exactly once, so the total work becomes the number of distinct subproblems times the cost of combining their answers — fifty entries, one addition each.
Which tells you exactly when the technique helps, and this is worth being precise about, because "add a cache" is offered far too freely. Memoization pays off when the recursion tree contains vastly more nodes than there are distinct arguments. Apply it to mergesort and nothing happens: mergesort's recursive calls all have different arguments, so every cache lookup misses and you have paid for a dictionary to store answers you will never ask for again. Recursion that fans out is not enough. The branches have to reconverge.
There is a second condition, quieter but just as necessary: the function must be a genuine function of its arguments. If it reads a clock, a global variable, or a file that might change, then a stored answer may no longer be the right answer, and the cache is not an optimisation but a bug. Purity is what licenses the substitution of a recorded value for a recomputation.
So what has actually been traded? Time for space. The table holds one entry per distinct subproblem, and that count is now the thing to watch — because it can itself be enormous. Solving the travelling salesman problem by this method stores an entry for every subset of cities paired with an endpoint, which is on the order of 2^n times n: dramatically better than the (n-1)! of brute force, and still hopeless at n = 100. Memoization removes redundancy; it does not make an exponential number of distinct questions go away.
And there is a boundary worth naming for honesty's sake. Knapsack solved this way runs in time proportional to the number of items times the capacity, which people call linear-ish and is in fact pseudo-polynomial: the capacity is a number written in binary, so its magnitude is exponential in the length of the input that encodes it. The method is fast when the numbers are small, not fast in the sense complexity theorists mean, and knapsack remains NP-hard.
The analogy
THE ANALOGY #Think of a large family tree research project split among cousins who never speak. Each of them, tracing back from a different living relative, independently works out the same great-great-grandmother's line, in full, from parish records. The archive is not hard to read — it is just being read forty times over. Pin one shared board on the wall where each verified ancestor is written down once, and every cousin who reaches that name stops there and reads it. The genealogy was never the expensive part; the isolation was.
the shared board suggests the saving is coordination between separate workers, whereas the recursion has only one worker — it is itself at different moments, and the memo table is a message it sends forward in time rather than sideways to a colleague.
Clarifying the model
THE MODEL #Two refinements.
First, memoization and dynamic programming are the same idea approached from opposite ends. Memoization is top-down: state the problem recursively, cache as you go, and only the subproblems your particular query actually needs get computed. Tabulation is bottom-up: identify the subproblems in dependency order and fill an array from the base cases upward. Tabulation avoids recursion overhead and makes the storage pattern obvious — which is what lets you notice, for Fibonacci, that only the last two entries are ever read again, so the table can shrink to two variables. Memoization is easier to write and can be far better when the reachable subproblem space is much smaller than the full one. Neither is uniformly right.
Second, the recursion tree is not really a tree once you memoize — it is a directed acyclic graph, and it always was. The naive version simply traverses every path through that graph separately rather than every node once. That reframing tells you where to look for the saving in any new problem: draw the dependency graph, count the nodes, and compare that to the number of paths.
A picture of it
THE PICTURE #How to readevery node is a distinct subproblem, and the solid arrows are dependencies. Notice that "fib 3" and "fib 2" each have two arrows arriving — that is the reconvergence memoization exploits. Without the table each incoming arrow re-expands the whole subtree beneath it; with it, the dotted edges to the store mean the second and third arrivals cost one lookup.
What became clearer
WHAT CLEARED #The exponential cost was never in the arithmetic. It came from a recursion that fans out into a graph and then traverses every path through it instead of every node — so the fix is not a faster computation but a refusal to repeat one. Memoization is worth reaching for exactly when the distinct subproblems are few relative to the calls, the function is pure, and the table will fit.
Where to go next
ONWARD #- Why some dynamic programs can throw most of the table away (Fibonacci needs two entries, edit distance needs one row) and how to spot that from the dependency graph.
- Hirschberg's algorithm, which recovers a full alignment in linear space by trading extra time for a discarded table.
- Cache invalidation as the general form of the purity condition — what memoization becomes when the underlying answers can change.
Key terms
TERMS #| Term | What it means |
|---|---|
| Overlapping subproblems | the property that a recursion asks the same question many times, which is what memoization exploits. |
| Optimal substructure | the property that a problem's solution is built from optimal solutions of its subproblems; the second requirement for dynamic programming. |
| Tabulation | the bottom-up form of dynamic programming: fill a table in dependency order rather than caching a recursion. |
| Pseudo-polynomial time | running time polynomial in the numeric value of an input rather than in the number of bits used to write it. |
Every term the collection defines is gathered in the glossary.