Top-down memoization

**Memoization** wraps a recursive function with a lookup: before computing a state, check whether its answer is already stored; after computing it, store it. The function's logic is unchanged, and each distinct state is computed once.

The memoised Fibonacci animation on n = 5 makes 9 calls instead of 15, and on n = 10 it makes 19 calls instead of 177. The extra calls are the cache hits: they return at once. The recursion tree shrinks from a bush to nearly a single path with hanging leaves.

1static long[] memo;
2
3static long fibMemo(int n) {
4    if (n <= 1) return n;
5    if (memo[n] != 0) return memo[n];            // already solved
6    return memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
7}
8
9static long fibonacci(int n) {
10    memo = new long[Math.max(n + 1, 2)];
11    return fibMemo(n);
12}

1static long[] memo = new long[100];
2static long fib(int n) {
3    if (n <= 1) return n;                       // base cases
4    if (memo[n] != 0) return memo[n];           // already solved: reuse it
5    return memo[n] = fib(n - 1) + fib(n - 2);   // solve once, remember
6}

A memo table needs a value meaning **not computed yet**, distinct from every real answer. Zero often fails because zero can be a real answer (the fewest coins for amount 0 is 0). Use a special value outside the answer range, such as -1 when answers are never negative, or a boxed Integer[] where null means not computed.

If the answer itself can be -1 (for example, 'impossible'), use a different sentinel such as -2 for 'not computed'. The animation counts both calls and cache hits: on the “Memoized” preset for coins 1, 3, 4 and amount 6 there are 14 calls and 5 cache hits.

1static final int UNSET = -2, IMPOSSIBLE = -1;
2
3static int coinChangeTopDown(int[] coins, int amount) {
4    int[] memo = new int[amount + 1];
5    Arrays.fill(memo, UNSET);                    // -2 can never be a real answer
6    return solve(coins, amount, memo);
7}
8
9static int solve(int[] coins, int amount, int[] memo) {
10    if (amount == 0) return 0;
11    if (memo[amount] != UNSET) return memo[amount];
12    int best = Integer.MAX_VALUE;
13    for (int c : coins) {
14        if (c > amount) continue;
15        int sub = solve(coins, amount - c, memo);
16        if (sub != IMPOSSIBLE) best = Math.min(best, sub + 1);
17    }
18    return memo[amount] = best == Integer.MAX_VALUE ? IMPOSSIBLE : best;
19}

1static int[] memo;                                   // memo[a]: -2 = not computed yet, -1 = impossible, otherwise the fewest coins
2static int f(int[] coins, int a, boolean useMemo) {
3    if (a == 0) return 0;                            // base case
4    if (useMemo && memo[a] != -2) return memo[a];    // cache hit: this state is already solved (even if it was impossible)
5    int best = -1;
6    for (int c : coins) {
7        if (c > a) continue;
8        int sub = f(coins, a - c, useMemo);
9        if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1;
10    }
11    if (useMemo) memo[a] = best;                     // store the answer, including -1
12    return best;
13}

A state whose answer is 'impossible' or 'no solution' is still an answer, and it must be cached like any other, or the same failing subtree is explored again every time it is reached. In the code above, memo[amount] = IMPOSSIBLE does that. Leaving it out is correct but can make a memoised solution as slow as plain recursion on inputs with many dead ends.

The “Impossible states are cached too” preset (coins 4 and 6, amount 9) shows the stored -1 results: no way to make 9 from 4 and 6 exists, and the animation finishes after 4 calls.

1static int[] memo;                                   // memo[a]: -2 = not computed yet, -1 = impossible, otherwise the fewest coins
2static int f(int[] coins, int a, boolean useMemo) {
3    if (a == 0) return 0;                            // base case
4    if (useMemo && memo[a] != -2) return memo[a];    // cache hit: this state is already solved (even if it was impossible)
5    int best = -1;
6    for (int c : coins) {
7        if (c > a) continue;
8        int sub = f(coins, a - c, useMemo);
9        if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1;
10    }
11    if (useMemo) memo[a] = best;                     // store the answer, including -1
12    return best;
13}

Top-down recursion needs one stack frame per level of the longest dependency chain: the chain has length n for Fibonacci and the amount divided by the smallest coin for coin change. When that depth is large, Java throws StackOverflowError long before running out of heap. The frames are held on the thread stack, whose default size is small (a few hundred kilobytes to a megabyte, depending on the platform).

Three remedies: convert the memoised recursion to bottom-up tabulation (no recursion, no depth limit), run the recursion in a thread started with a larger stack size, or reduce the depth by processing states in an order that the recursion reaches shallowly. Tabulation is the robust answer, which is why the next lesson group is bottom-up.

1// run a deep recursion on a thread with a 256 MB stack
2static long runDeep(int n) throws InterruptedException {
3    long[] result = new long[1];
4    Thread t = new Thread(null, () -> result[0] = depthSum(n), "deep", 256L << 20);
5    t.start();
6    t.join();
7    return result[0];
8}
9
10static long depthSum(int n) {
11    return n == 0 ? 0 : n + depthSum(n - 1);     // recursion depth n
12}

1static long[] memo = new long[100];
2static long fib(int n) {
3    if (n <= 1) return n;                       // base cases
4    if (memo[n] != 0) return memo[n];           // already solved: reuse it
5    return memo[n] = fib(n - 1) + fib(n - 2);   // solve once, remember
6}

Both versions compute the same function, but memoization turns an exponential number of calls into a polynomial one. The number of calls without memoization for Fibonacci is 2·F(n + 1) - 1, and with memoization it is 2n - 1.

The coin-change animation shows it on small input: for coins 1, 3, 4 and amount 6 the plain recursion makes 24 calls, and the memoised version makes 14 calls with 5 cache hits. There are only 6 distinct amounts to solve, so the memoised version can never solve more than 6 non-trivial states; the rest of its calls are cheap lookups.

1static int[] memo;                                   // memo[a]: -2 = not computed yet, -1 = impossible, otherwise the fewest coins
2static int f(int[] coins, int a, boolean useMemo) {
3    if (a == 0) return 0;                            // base case
4    if (useMemo && memo[a] != -2) return memo[a];    // cache hit: this state is already solved (even if it was impossible)
5    int best = -1;
6    for (int c : coins) {
7        if (c > a) continue;
8        int sub = f(coins, a - c, useMemo);
9        if (sub >= 0 && (best < 0 || sub + 1 < best)) best = sub + 1;
10    }
11    if (useMemo) memo[a] = best;                     // store the answer, including -1
12    return best;
13}