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.ts

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

const memo: Map<number, number> = new Map();
const result: number = 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

TypeScript: const memo: Map<number, number> = new Map(); passed explicitly to fib(n, memo). The Map<number, number> annotation documents the key/value contract.
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<number, number>` 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.