Chapter 38

Home

Refactoring: Memoization

The naive Fibonacci recalculates the same values hundreds of thousands of times. Memoization caches each result the first time it's computed — subsequent calls return the cached value in O(1). Result: O(2ᴺ) → O(N).

Before: Naive Fibonacci

Clean, elegant, and catastrophically slow. Each call spawns two more.

C++ — O(2ᴺ) naive

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

// fib(40)  →  102,334,155  (331 million calls)
// fib(100) →  never finishes in your lifetime

Rust — O(2ᴺ) naive

fn fib(n: u64) -> u64 {
    if n <= 1 { return n; }
    fib(n - 1) + fib(n - 2)
}

After: Memoized Fibonacci

Add a cache (an array or map). Before recursing, check the cache. After computing, store in the cache. The same value is never computed twice.

fib(5): check cache… miss → compute → store in memo[5] fib(3) later: check cache… hit! → return memo[3] instantly N values computed once → O(N) total, O(N) memory

C++ — O(N) memoized (top-down)

long long fib_memo(int n, vector<long long>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];     // cached → return
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

// Usage:
vector<long long> memo(n + 1, -1);
cout << fib_memo(n, memo) << "\n";

Rust — O(N) memoized (top-down)

fn fib_memo(n: usize, memo: &mut Vec<Option<u64>>) -> u64 {
    if n <= 1 { return n as u64; }
    if let Some(val) = memo[n] { return val; }
    let val = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    memo[n] = Some(val);
    val
}

// Usage:
let mut memo = vec![None; n + 1];
println!("{}", fib_memo(n, &mut memo));

💡 Top-down vs bottom-up

This is top-down DP: start with the full problem, recurse down, cache results. The alternative is bottom-up (iterative): fill memo[0], memo[1], up to memo[N]. Both are O(N). Top-down is often easier to write; bottom-up avoids recursion overhead. You'll see both in Phase 7 (Dynamic Programming). 

// Speed comparison:
//                fib(40)       fib(100)
// Naive:         331M calls    ∞
// Memoized:      79 calls      199 calls
// Bottom-up:     40 iterations 100 iterations

The Pattern Generalises

Memoization works for any recursive function with overlapping subproblems. The pattern is always the same:

1. Identify the state

What parameters define a unique subproblem? (e.g. n in Fibonacci)

2. Create a cache

An array or map keyed by state. Use a sentinel value (-1 or None) for "not computed."

3. Check before compute

If the cache has the answer, return it. Otherwise compute, store, return.

Key Takeaways

Practice