Remembering answers

Ask a naive procedure for the thirtieth Fibonacci number and it makes 2,692,537 calls. The Fibonacci numbers start with F(0) = 0 and F(1) = 1, and each later one is the sum of the two before it, so F(2) = 1, F(3) = 2 and F(4) = 3. The thirtieth is $F(30)$, counted from zero, and its call count is twice $F(31)$ minus one. Ask a procedure that writes each answer in a table and the same job needs twenty-nine additions, one for each value from F(2) to $F(30)$. The two procedures compute the same number, and the difference is entirely in how many times they compute the same intermediate value [S:1:117].

A recursive procedure is one whose definition refers to itself, and the act of a procedure calling itself is recursion. A memoisation procedure keeps a table of answers it has already produced and consults the table before doing any work. The first call with a given input pays the full cost, and every later call with that input pays only for a lookup. The saving arrives when the same subproblem returns. !Computing F(5) the naive way. The same call returns again and again: 15 calls for 6 distinct values. A table stores each value once, so the work falls to 4 additions. At the thirtieth number the same difference is 2,692,537 calls against 29 additions. Status: schematic.

The Fibonacci rule gives the waste a shape: F(n) = F(n−1) + F(n−2) for every n at least two. Computing the nth number therefore calls the procedure for n − 1 and for n − 2, and the call for n − 2 repeats work the call for n − 1 has already done. The recursion tree is not a tree of distinct subproblems but a tree of repeated ones.

The number of calls satisfies the same recurrence as the numbers, with the two smallest cases counting one call each. Induction gives 2F(n+1) − 1 calls, where F(n+1) is the Fibonacci number one place above the one you asked for [S:1:117]. A call for n − 1 happens once, for n − 2 twice, for n − 3 three times and for n − 4 five times: the counts themselves run along the Fibonacci numbers, F(k+1) calls for n − k.

Worked example. Compute three Fibonacci numbers both ways: F(7) is the worked example, and F(5) and F(10) bracket it to show the ratio widening.

The third column counts only the additions that fill the table, and the fourth counts the entries from F(0) to F(n). At n = 7 the naive procedure makes 41 calls and the table procedure makes 6 additions, so the saving is a factor of about seven. At n = 10 the counts are 177 and 9, and the ratio keeps growing because the naive count is exponential while the table count is linear. For F(5) the table holds six entries, F(0) through F(5), but two of them are the given starting values, so only the remaining four cost an addition.

$$C(n)=2F_{n+1}-1$$

The number of calls in the naive recursion is twice the next Fibonacci number, minus one, so the call count grows like the numbers themselves. The subscript carries that next number: in the displayed formula the small n + 1 below the F names which Fibonacci number is meant, while 2F(n+1) − 1 in the running text is the same statement written with parentheses.

The repair is to write the answer down. The first time the procedure computes a value it stores the value under its input, and every later request for that input returns the stored value immediately. The procedure still makes a call for each distinct subproblem, but each distinct subproblem is solved once, and the total work becomes proportional to the number of distinct subproblems rather than to the number of calls.

The table is usually an [[term:array]]array, a block of slots reached by a whole-number index, or a [[term:dictionary]]dictionary, a structure that maps a key to a value. The key is the input the stored answer belongs to, here the index n. The lookup is assumed to cost one step, which is another modelling decision of the kind the first section described, and it holds when the key is small enough to index an array directly. When the key is a long string or a large structure, the lookup has its own cost, and the saving has to be measured against that cost rather than assumed.

The method applies when the subproblems overlap, which is the opposite of the situation in merge sort. Merge sort splits a list into two disjoint halves, so no subproblem is solved twice and a table would only add bookkeeping. The Fibonacci procedure splits a number into two smaller numbers that share almost all of their own subproblems, and that sharing is what the table collects.

A dynamic programming solution goes one step further and fills the table in a deliberate order, starting from the smallest inputs. For Fibonacci the table is an array with one entry per index, filled from left to right, and the procedure needs only the two previous entries at each step. The memoised version performs O(n) additions and the deliberate version does the same, which is an exponential improvement over the naive recursion [S:1:118].

This is the first place in the chapter where the same recurrence yields two different classes, because of how the procedure is organised rather than because of a better formula. The recurrence is unchanged, and the same values are computed; only the repeated work is removed. In the language of the growth ladder, the naive procedure sits on the exponential rung and the table procedure sits on the linear rung, and the gap between those rungs is 2,692,537 calls against 29 additions.

The saving is not free, because the table occupies memory proportional to the number of distinct subproblems. On a large problem that memory can be the binding constraint, the resource that runs out first and therefore caps the size you can solve. The method also helps only when subproblems repeat; if every call has a new input, the table adds bookkeeping and saves nothing. A table is only correct when the answer depends on the inputs alone, since a procedure that reads hidden state, meaning state that is not among its arguments, can return a stale value for an input it has seen before.

The formal statement. Let $P$ be a procedure that calls itself, and let $S(x)$ be the set of arguments reachable from $x$. Memoisation adds a table $M$ and changes each call into this rule: if $x$ is already in $M$, return $M[x]$; otherwise compute $P(x)$, store the result, and return it. The procedure must be a function of its argument, so two calls with the same $x$ have the same answer and produce no observable side effect. Under that condition the number of computations is at most the number of distinct states $|S(x)|$, and the work is that count times the cost of one state, plus one lookup per call.

The derivation. For Fibonacci, let $T(n)$ be the number of calls. Each call for $n>1$ makes one call for $n-1$ and one for $n-2$, plus itself, so $T(n)=T(n-1)+T(n-2)+1$ with $T(0)=T(1)=1$. Induction gives $T(n)=2F_{n+1}-1$ [S:1:117]. The memoised version evaluates each $F_i$ once, so it performs $O(n)$ additions and stores $n+1$ values [S:1:118]. The call tree collapses into a chain of table writes, and the number of distinct states is what replaces the number of calls.

The edge case. The purity condition is not decoration. A procedure that reads a global counter, the clock, a random seed or a mutable object can return a different value for the same argument, and the table then returns a stale answer. The same failure appears when the argument is a large structure: the key must be hashed or compared in full, and the lookup is no longer one step. A lookup costs one step only when the key fits in a word and the table is an array; a long key makes the lookup itself a computation.

A second edge. The table costs memory proportional to $|S(x)|$. For a two-index state, as in edit distance, that is a product of the two lengths, and the array is $O(mn)$ [S:1:132]. Memory can be the binding constraint even when time is not. A rolling array reduces it when the recurrence looks back only a fixed number of rows, which is why the space and the time of a dynamic program are separate claims.

What the core hid. The core named the memory cost, the purity condition and the count of distinct subproblems, so it hid none of them. What it left implicit is that a subproblem is the tuple of arguments, so two procedures with the same recurrence can need tables of different sizes. Every example in the core has a one-number state, which is why the omission is invisible there.

Original sources. Memoisation is usually credited to Donald Michie in 1967, with the same technique proposed by Arthur Samuel in 1959, and a table-driven maze solver built by Shannon's robot in 1950 [S:1:118]. Dynamic programming as a named paradigm is due to Richard Bellman in the mid-1950s [S:1:119]. The two-index table for edit distance is attributed to Wagner and Fischer in 1974, with independent discoveries by Vintsyuk, Velichko and Zagoruyko, Sankoff, and Sellers [S:1:132].

An open question. Whether edit distance has an algorithm in $O((m+n{)}^{2-ϵ})$ time for some fixed $ϵ>0$ is open. The table in 5.5 needs a product of the two lengths, and no procedure is known that runs below that product by more than a logarithmic factor. Evidence that would settle it: such a procedure, or a proof that none exists. A negative answer would have to rule out a whole family of table-filling methods, not one program.

A frontier result. The same recurrence drives sequence alignment. The edit-distance table is filled in row-major order, each entry from three neighbours, and a path from corner to corner reads off an optimal edit sequence [S:1:133]. The table is a shortest path in a grid, and the algorithm most often called Needleman–Wunsch computes the longest common subsequence with the same machinery [S:1:133]. The difference between the memoised and the tabulated version is a choice about evaluation order, not about the recurrence [S:1:119]. That is the dynamic program of 5.5 doing work outside the chapter.

What to read next. Read chapter 3 of Erickson for the recipe from recurrence to table [S:1:119]. Read chapter 21 of Mathematics for Computer Science for the Fibonacci recurrence and its closed form [S:5:883]. Then read the edit-distance section for the attribution trail and for the table drawn out entry by entry [S:1:132][S:1:133].