Memoisation

In Tree recursion (4.3), fib(6) took 25 calls to compute the number 8. Most of those calls were repeats: fib(2) was worked out five separate times, from scratch, and gave 1 every time. A person doing this by hand would write the answer down the first time and look it up after. A program can do the same.

⋯3#define MAXN 934 5static long calls = 0;6static long long memo[MAXN];7 8long long fib_memo(int n)9{10    calls++;11    if (n < 2)12        return n;13    if (memo[n] != -1)14        return memo[n];15    long long a = fib_memo(n - 1);16    long long b = fib_memo(n - 2);17    memo[n] = a + b;18    return memo[n];19}20 21long long fib_loop(int n)22{23    if (n == 0)24        return 0;25    long long prev = 0, cur = 1;26    for (int i = 2; i <= n; i++) {27        long long next = prev + cur;28        prev = cur;29        cur = next;30    }31    return cur;32}33 34int main(void)35{36    for (int i = 0; i < MAXN; i++)37        memo[i] = -1;38    long long f = fib_memo(6);39    printf("memoised fib(6) = %lld in %ld calls\n", f, calls);40    long long g = fib_loop(6);41    printf("loop fib(6) = %lld\n", g);42    return 0;43}

Repeated work

Count the calls of plain fib(6) by what they ask for: fib(5) once, fib(4) twice, fib(3) three times, fib(2) five times, fib(1) eight times and fib(0) five times. That is 1 + 1 + 2 + 3 + 5 + 8 + 5 = 25. The same small questions are asked again and again, and every repeat redoes the whole subtree under it. These are repeated subproblems, and they are why the calls grow exponentially.

The table

Memoisation means storing each answer the first time it is computed, and looking it up every time after. For fib the answers are indexed by n, so the table is an array, memo, with one cell per n.

long long fib_memo(int n)
{
    calls++;
    if (n < 2)
        return n;
    if (memo[n] != -1)
        return memo[n];
    long long a = fib_memo(n - 1);
    long long b = fib_memo(n - 2);
    memo[n] = a + b;
    return memo[n];
}

The only changes from plain fib are the two lines that read the table and the line that writes it. Before the first call, main sets every cell to −1, which means “not worked out yet”. Why not 0? Because 0 is a real answer: fib(0) = 0. A cell holding 0 would look empty, and that answer would be worked out again every time it was asked for.

The table is 93 cells long because fib(92) = 7,540,113,804,746,346,429 is the largest Fibonacci number that fits in a long long; fib(93) does not.

What the table does to the calls

Watch the tree in the clip. The first call of each fib(k) runs in full and stores its answer. Every later call of fib(k) finds the answer in the table at once, and the whole subtree that plain fib would have built under it is never made. What is left is a path down the left of the tree, from 6 to 1, with one short branch off each node: 11 calls instead of 25.

In general, only the first calls of fib(n), fib(n − 1), … down to fib(2) make further calls, two each; every other call stops at once, either because it is a base case or because it finds its answer. That is n − 1 calls making 2(n − 1) more, plus the first: memoised fib(n) makes 2n − 1 calls for n ≥ 1: 11 for fib(6), 59 for fib(30).

What the table does not change is the depth. The first call of fib(6) still has to go all the way down to fib(1) before anything is stored, so the stack still holds 6 frames of fib_memo at the deepest, just as plain fib did. The table saves calls, not stack.

Top down and bottom up

fib_memo starts at the top, fib(6), and fills the table as the answers come back: top down. But we know the order the cells get filled: 2, 3, 4, 5, 6. So we can fill them in that order directly, with a loop and no recursion at all: bottom up. This is the idea behind dynamic programming.

For fib, each cell needs only the two cells before it, so the loop does not even need the table. Two variables are enough:

long long fib_loop(int n)
{
    if (n == 0)
        return 0;
    long long prev = 0, cur = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + cur;
        prev = cur;
        cur = next;
    }
    return cur;
}

Before each round, cur is fib(i − 1) and prev is fib(i − 2). For n = 6 the loop runs 5 times and ends with cur = 8.

The costs

Memoisation trades memory for time: a table of n cells buys a run that grows in proportion to n instead of exponentially. The loop then removes the stack as well.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic memo.c -o memo
./memo

It prints memoised fib(6) = 8 in 11 calls and loop fib(6) = 8.

Worked example

fib(30), three ways. Plain recursion makes 2,692,537 calls (Tree recursion, 4.3). The memoised version, with 30 in place of 6, makes 59, and the loop runs 29 rounds. All three give 832,040.

Bottom up by hand to fib(8). Start with (prev, cur) = (0, 1), and at each round replace them with (cur, prev + cur):

(0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21).

That is seven rounds, for i = 2 to 8, and cur ends at 21, so fib(8) = 21.

Why −1, once more. Suppose the table started at 0 and a function stored an answer that is itself 0. Every later call would read 0, take it for “empty” and do the work again. fib escapes only because a call with n < 2 returns before it reads the table, so fib(0) is never stored. A marker that can never be a real answer, like −1 for a count, is the safe choice.

Before you read on, three to try:

1. How many calls does memoised fib(10) make? (19.)
2. After fib_memo(6), which cells of memo hold an answer? (2 to 6; cells 0 and 1 still hold −1.)
3. If main called fib_memo(6) a second time straight after, how many calls would that make? (1: the answer is already in memo[6].)

Where it’s used

Dynamic programming. Many problems split into smaller ones that repeat, and a table of their answers makes them fast. Edit distance, the fewest single-letter changes that turn one word into another, is filled in a table this way; spelling suggestions and the comparison of DNA sequences use it. So does finding shortest paths in a graph (19.5), and choosing the cheapest order in which to multiply a chain of matrices. Binomial coefficients (4.8), next, are another.

Caching. Any function that always gives the same answer for the same input, and takes a long time, can keep a table of past answers: a web server keeps pages it has already built, a compiler keeps results it has already worked out.

Reference card

Platform: C11, gcc on x86-64 Linux, long long 8 bytes.