Fibonacci with Memoization

Compute fib(n) recursively. Cache each fib(k) in a memo map so each subproblem is solved at most once.

Algorithm

Canonical input n = 6 produces fib(6) = 8. Replay highlights every memo write and every cache hit.

Basic Implementation

basic.js

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

const memo = new Map();
const result = fib(6, memo);
console.log(result);
console.log(JSON.stringify(Object.fromEntries(memo)));

Complexity

Time: O(n) with memoization (vs. O(2^n) without)
Space: O(n) memo + O(n) call stack

Implementation notes

JavaScript: const memo = new Map(); passed explicitly to fib(n, memo). A plain object literal works too, but Map avoids any string-key coercion surprises.
The replay shows the call stack on one side and the memo map on the other so memo writes and cache hits are visually distinct.

memoization A `Map` cache stores each completed subproblem. Before recursing, check the memo: a hit returns immediately, a miss descends.

explicit memo parameter Pass the memo as an explicit parameter so the lesson stays about caching, not language-level scoping.