Solution: Caching the Results

Start with where the cache lives. It has to outlive a single call, because the point is that a later call finds what an earlier call stored. But the public fib takes only n, and we do not want to change that signature. This is the situation the sorted-array chapter handled with a public method and a private helper. The public method takes what the caller has, and the private helper takes one extra parameter that the caller never sees. Here the extra parameter is the cache. The public fib allocates it and passes it to the helper:

public static int fib(int n) {
  int[] memo = new int[n + 1];
  return fib(n, memo);
}

private static int fib(int n, int[] memo) {
  // To be implemented!
}

The cache has n + 1 slots so that index n exists.

Now let’s write the helper without using the cache. It is exactly the same as the chapter’s fib, except that it calls itself with the extra parameter:

private static int fib(int n, int[] memo) {
  if (n <= 1) {
    return n;
  }
  return fib(n - 1, memo) + fib(n - 2, memo);
}

This version does not use the cache. Let’s make two updates to it. First, let’s store the result in the cache before returning it:

private static int fib(int n, int[] memo) {
  if (n <= 1) {
    return n;
  }
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);  // store the result
  return memo[n];
}

By the time fib(n) returns, the cache holds $F (k)$ for every $k$ from $2$ to $n$ . This version still does all the work of the chapter’s fib. It just stores the results. Nothing reads them yet.

Next, let’s check the cache before doing the recursive work. If memo[n] is not zero, the value was computed earlier, so we return it without recursing:

private static int fib(int n, int[] memo) {
  if (n <= 1) {
    return n;
  }
  if (memo[n] != 0) {
    return memo[n];  // computed earlier, so just look it up
  }
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

Why memo[n] != 0? Java fills a new int[] with zeros, so every slot starts at 0. We can use that as the marker for “not computed yet”, because every value we store is $F (k)$ for some $k \geq 2$ , and those are all at least $1$ .

So the helper does three things, in order: the base case, the lookup, and the recursive work followed by the store.

Time is $O (n)$ . Which calls still do the recursive work? Let’s lay out the calls that fib(5) makes now, the way the chapter did for the version without the cache:

                              fib(5)
                      ┌──────────┴─────────┐
                   fib(4)               fib(3)   lookup
             ┌────────┴────────┐
          fib(3)            fib(2)   lookup
       ┌─────┴─────┐
    fib(2)      fib(1)   base case
  ┌────┴───┐
fib(1)   fib(0)   base cases

fib(5) calls fib(4) first. fib(4) calls fib(3) first, and so on down the left side to fib(2), which calls the two base cases. Every result gets stored on the way back up. Then the second calls start.

When fib(2) returns, fib(3) calls fib(1), which is a base case and immediately returns.
When fib(3) returns, fib(4) calls fib(2), but that was computed and stored while fib(3) was running, so this call is a lookup.
When fib(4) returns, fib(5) calls fib(3), and that is a lookup too.

The chapter’s tree had $15$ calls for fib(5). This one has $9$ , and the repeated subtrees are gone. fib(3) is computed once, not twice, and fib(2) is computed once, not three times.

The same thing happens for any $n$ . The first calls form one chain, fib(n) down to fib(2), and that chain is where all the recursive work happens: $n - 1$ calls, each computed once. The second call that each of those makes, fib(n - 2, memo), is either a base case or a lookup, and there is one of those per call in the chain. So there are about $2 n$ calls in total, and each one does a constant amount of work. The time is $O (n)$ , down from $O (2^{n})$ .

Space is $O (n)$ . There are two things to count for auxiliary space. The cache is an array of $n + 1$ integers, so that is $O (n)$ . The call stack is the chain we just followed, fib(n) down to fib(1), and that is $n$ frames deep, the same as the chapter’s recursive fib. Both are $O (n)$ , so the auxiliary space is $O (n)$ . The input is a single number, so the total is $O (n)$ as well.

Here is the chapter’s table with this version added:

`fib` version	Time	Auxiliary Space
recursive	$O (2^{n})$	$O (n)$
recursive with a cache	$O (n)$	$O (n)$
bottom up with an array	$O (n)$	$O (n)$
bottom up with three variables	$O (n)$	$O (1)$

Memoization puts the recursive version on the same row as the bottom-up array. It fixes the time and does not change the space. With this recursive implementation, shrinking the cache to a few variables would not get rid of the call stack, which is $n$ frames deep. The calls still go from fib(n - 1) down to the base case, so the auxiliary space stays $O (n)$ .