Answers · Making it fast enough

What is memoization and why does caching recursive results make it so much faster?

In shortMemoisation stores each answer once and reuses it, so a recursion that repeats the same subproblems stops redoing work and becomes a table lookup instead.

Memoisation means storing the answer to each distinct subproblem the first time it is computed and returning that stored answer whenever the same subproblem appears again. It makes a recursive method fast when, and only when, the recursion calls itself with the same arguments many times: the repeated work becomes a lookup, and the method no longer re-expands a subtree it has already solved.

The repetition is the whole reason

For the staircase, the number of ways to climb $n$ steps is the number for $n-1$ plus the number for $n-2$ . A plain recursive method follows that rule literally. Calling it on five asks for four and three; the call on four asks for three and two. The call on three has already been made, and it will be made again lower down. At small $n$ that looks harmless, because the repeated call is cheap. At thirty the call tree has thousands of copies of the same small questions, and almost all of the work is duplication rather than new arithmetic.

\text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2), \qquad \text{ways}(0)=\text{ways}(1)=1

Count the calls rather than guess. Without a store, one call to $\text{ways}(30)$ expands into 2,692,537 calls that do work: every non-base call performs one addition and then starts two more. With a store, the same call performs 31 computations, one for each argument from 0 to 30, and answers the other 29 requests from the store. At fifty the gap is 40,730,022,147 calls doing work against 51 computations and 49 lookups. Dividing gives $40{,}730{,}022{,}147 / 51 = 798{,}627{,}885$ with 12 left over, so the plain version is doing roughly eight hundred million times as many units of work. The time follows the same ratio: 345,600,000 milliseconds is 345,600 seconds, which is 96 hours, or four days, while the stored version returns in under a millisecond.

FIG 1

case	calls that do work	calls answered from store	time (ms)
thirty steps, before	2,692,537	0	200
thirty steps, after	31	29	0
fifty steps, before	40,730,022,147	0	345,600,000
fifty steps, after	51	49	0
ten thousand steps, after	10,001	9,999	20

Why the count collapses

Every call either finds its answer in the store and returns immediately, or does not and computes once. The second case can happen only once per distinct question, because after that the answer is in the store. So the number of calls that do real work is exactly the number of distinct arguments, not the number of nodes in the call tree. For a one-argument staircase that is $n+1$ ; for two arguments ranging to $n$ and $m$ it is $n \times m$ ; for a position in a list and a budget it is the list length times the number of budget values. This is why the repair can turn an exponential tree into a linear scan: it counts questions, not branches.

\text{work} \;=\; (\text{number of distinct questions}) \times (\text{work in one call, not counting its recursive calls})

What the key must capture

The repair fails in two opposite ways. If the key leaves out something the answer depends on, the method becomes fast and wrong. Suppose the answer depends on a position and a remaining budget, but the store is keyed on the position alone; the answer computed for one budget is then returned for another, and the error appears only when the same position is reached with two budgets. If the key includes something irrelevant, such as a counter used only for reporting, two genuinely identical questions look different, no lookup ever matches, and the method stays correct and as slow as before. The key must contain everything the answer depends on and nothing else. This is the one place where the repair is easy to get silently wrong, because a too-narrow key produces answers rather than a crash, and a too-wide key produces no visible failure at all.

The store holds one entry per distinct question, so the memory bill is the same count that set the running time. Ten thousand entries for the staircase at ten thousand is small. Two arguments each ranging to ten thousand is $10{,}000 \times 10{,}000 = 100{,}000{,}000$ entries, which is several gigabytes and is not small. The depth also remains: the remembered recursion still goes all the way down before it comes back up, so ten thousand steps still need ten thousand nested calls and the recursion limit still has to be raised. The time has collapsed; the stack has not.

Memoisation is not a general speed-up for recursion. It helps when the same argument combinations recur. If every call has different arguments, there are no hits and the store is pure overhead. It also stops being practical when the number of distinct questions is too large: three positions each up to a thousand is $1{,}000^3 = 1{,}000{,}000{,}000$ entries, and a set of visited places among thirty has $2^{30} = 1{,}073{,}741{,}824$ possible subsets. The formula tells you before you write the method whether the table will fit in time and memory. A cache with no repeats is just a slower method with a bigger memory footprint.

Worth keeping

Memoisation helps only when the recursion asks the same question more than once; it replaces repeated expansion with a lookup.
The running time after memoisation is the number of distinct questions times the work in one call, not the size of the call tree.
The store must be keyed on everything the answer depends on and nothing else, or the method becomes either fast and wrong or correct and slow.

Where this goes next

This question is one step of Answers Built From Smaller Answers, a course that works through its subject from the beginning. The page that teaches this part of it is Writing Each Answer Down Once, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course