Recursion with memoization

O(states)

A recursive function caches each result by its arguments so an overlapping subproblem is computed once instead of exponentially many times.

Signals

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

Template

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;
}

Looks similar, isn't

Plain recursion: Plain recursion recomputes the same state every time it is reached, which is fine when states never repeat. Reach for memoization only once you notice the same arguments showing up more than once in the call tree.
Dynamic programming (tabulation): Memoization is this exact same recurrence solved top-down with a cache. Switch to bottom-up DP when you want to avoid recursion depth or fill the table in a fixed order.

n/states up to roughly 1e4-1e5 and naive recursion revisits the same (i, j) many times -> cache each state once: O(states) time and space instead of exponential.

Learn this pattern