Recursion with memoization

How does Recursion with memoization work?

Write the plain recursion first. Get it correct before trying to make it fast.

Look at what the arguments really are. If two calls share them, they share the answer.

Add a cache keyed by those arguments. A map or a plain array both work.

At the top of the function, return the cached answer if one exists. Nothing else runs.

Before returning, store the answer under its key. The next call reads it instead of recomputing.

Each distinct argument is now computed once. The tree of calls collapses into a graph.

Sources: Wikipedia: Memoization, Python docs: functools.cache

1. fib(5) needs fib(4) and fib(3)The naive version splits into two calls.
2. fib(4) needs fib(3) and fib(2)Now fib(3) is wanted twice over.
3. cache = {2: 1, 3: 2}The first fib(3) is computed and stored.
4. fib(3) is a lookupThe second fib(3) reads the cache. Its whole subtree is skipped.
5. 15 calls become 9Without a cache, fib(50) would take billions of calls.

function fib(n, memo = new Map()) {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    const result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.set(n, result);
    return result;
}

function fib(n: number, memo: Map<number, number> = new Map()): number {
    if (n <= 1) return n;
    const cached = memo.get(n);
    if (cached !== undefined) return cached;
    const result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.set(n, result);
    return result;
}

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

function fib(int $n, array &$memo = []): int {
    if ($n <= 1) return $n;
    if (isset($memo[$n])) return $memo[$n];
    return $memo[$n] = fib($n - 1, $memo) + fib($n - 2, $memo);
}

    public static long fib(int n, Map<Integer, Long> memo) {
        if (n <= 1) return n;
        Long cached = memo.get(n);
        if (cached != null) return cached;
        long result = fib(n - 1, memo) + fib(n - 2, memo);
        memo.put(n, result);
        return result;
    }

    public static long Fib(int n, Dictionary<int, long> memo) {
        if (n <= 1) return n;
        if (memo.TryGetValue(n, out long cached)) return cached;
        long result = Fib(n - 1, memo) + Fib(n - 2, memo);
        memo[n] = result;
        return result;
    }

A worked example of Recursion with memoization

Fewest coins for an amount

You get a list of coin values and an amount. Return the fewest coins that add up to it.

If no combination works, return minus one.

Ask the same question about a smaller amount. Each coin gives one branch.

The remaining amount alone identifies a subproblem. So the cache is keyed by that amount.

function coinChange(coins, amount) {
    const cache = new Map();

    function best(left) {
        if (left === 0) return 0;
        if (left < 0) return Infinity;
        if (cache.has(left)) return cache.get(left); // computed before

        let answer = Infinity;
        for (const coin of coins) {
            answer = Math.min(answer, best(left - coin) + 1);
        }

        cache.set(left, answer); // store the failure too
        return answer;
    }

    const result = best(amount);
    return result === Infinity ? -1 : result;
}

When should you use Recursion with memoization?

Use Recursion with memoization when the problem statement says “recursive calls repeat the same arguments (overlapping subproblems)”, “plain recursion is correct but too slow / exponential blow-up” or “small number of distinct states even though the recursion tree is huge”. A solution built on it usually runs in O(states).

• •recursive calls repeat the same arguments (overlapping subproblems)
• •plain recursion is correct but too slow / exponential blow-up
• •small number of distinct states even though the recursion tree is huge
• •cache/memo the result of (i, ...) before returning
• •Fibonacci / climbing stairs / grid-path wording with a hint to cache

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Recursion with memoization confused with?

Recursion with memoization is most often confused with Recursion, Dynamic programming (1-D), Hash set / map and Backtracking.

• Recursion: Plain recursion recomputes a repeated argument every time. The cache is the entire difference.
• Dynamic programming (1-D): Bottom-up DP fills a table in a fixed order. This fills it on demand, from the top down.
• Hash set / map: The cache is usually a map. This page is about deciding when to keep one.
• Backtracking: Backtracking explores paths that all differ, so nothing repeats. A cache there stores keys never asked again.

Common mistakes with Recursion with memoization

• A key that leaves out an argument

  Every value the answer depends on belongs in the key. A partial key returns another call's answer.

• Caching a mutable object

  Storing a reference lets a later call change it. Store a copy or a plain value.

• Not caching a failure

  A branch that fails is still an answer worth keeping. Otherwise dead ends get explored again.

• Caching where nothing repeats

  If every argument is unique, the cache only costs memory. Check the overlap before adding it.

Which interview problems use Recursion with memoization?

Interview problems solved with Recursion with memoization include Fibonacci, Climbing stairs, Coin change, House robber, Word break, Unique paths and Longest increasing path in a matrix.

• Fibonacci: The shortest example of an overlapping subproblem.
• Climbing stairs: The same shape with a different base case.
• Coin change: Keyed by the amount still left.
• House robber: Keyed by the index you are standing on.
• Word break: Keyed by the start position in the string.
• Unique paths: Keyed by the pair of coordinates.
• Longest increasing path in a matrix: Keyed by the cell, and no visited set is needed.

What is the time and space complexity of Recursion with memoization?

The target complexity of Recursion with memoization is O(states).

Cost is the number of distinct arguments times the work per call. A cache of 1e6 keys is fine.