Typorithm · medium

Memoized Recursion (Fibonacci)

memoize-recursionpatternsrecursionfibonaccidp

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Memoized Recursion (Fibonacci)

Memoization

Naive recursive Fibonacci is O(2^n) because it recomputes the same subproblems. Memoizing fib collapses it to O(n): each n is computed once and reused. This is top-down dynamic programming, and the recursive call must reference the memoized binding.

Plain recursive Fibonacci computes fib(n-1) and fib(n-2), which overlap heavily — fib(n-2) is recomputed by both branches, and so on down the tree. That repetition makes it O(2^n).

Wrapping fib with memoize() caches each fib(n) the first time it is computed. Every later request for the same n is a cache hit, so the work collapses to O(n) — each value is produced exactly once.

This is top-down dynamic programming: solve the big problem by recursing into subproblems and memoizing their answers. The key detail is that the recursive calls use fib — the memoized binding — not the inner lambda, or the cache would never be consulted.

Naive recursive fib is O(2^n) from repeated subproblems.

Memoizing collapses it to O(n) — each n computed once.

This is top-down dynamic programming.

const fib = memoize((n) => {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
});

console.log(fib(50));

Read the implementation

Connect each part of the code to the concept before you type.

1. Memoized binding

fib names the memoized wrapper, so recursive calls go through the cache.

const fib = memoize((n) => {

2. Base case

fib(0) is 0 and fib(1) is 1; these stop the recursion.

if (n < 2) return n;

3. Recursive step

Each fib(n) sums the two prior terms — and each recursive call is itself memoized.

return fib(n - 1) + fib(n - 2);

4. Self-reference

The call references fib, the memoized binding, not the inner lambda — that is what makes recursion hit the cache.

fib(n - 1)

5. Large input

fib(50) is instant when memoized; naive recursion would take billions of calls.

console.log(fib(50));

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.