Memoization to Optimize Recursion in DSA Typescript

Mental Model

Memoization remembers answers to small problems so we don't solve them again.

Analogy: Like writing down answers in a notebook while solving puzzles, so next time you see the same puzzle, you just look it up instead of solving it again.

fib(5)
  ↓
fib(4) + fib(3)
  ↓       ↓
fib(3)+fib(2) fib(2)+fib(1)
  ↓
[cache stores answers here]
fib(2) -> 1
fib(3) -> 2
fib(4) -> 3
fib(5) -> 5

Dry Run Walkthrough

Input: Calculate fib(5) using recursion with memoization

Goal: Find fib(5) efficiently by storing intermediate results to avoid repeated work

Step 1: Call fib(5), no cache yet

cache = {}
fib(5) -> fib(4) + fib(3)

Why: Start breaking down fib(5) into smaller problems

Step 2: Call fib(4), no cache yet

cache = {}
fib(4) -> fib(3) + fib(2)

Why: Need fib(4) to compute fib(5)

Step 3: Call fib(3), no cache yet

cache = {}
fib(3) -> fib(2) + fib(1)

Why: Need fib(3) to compute fib(4)

Step 4: Call fib(2), no cache yet

cache = {}
fib(2) -> fib(1) + fib(0)

Why: Need fib(2) to compute fib(3)

Step 5: fib(1) and fib(0) are base cases, return 1 and 0

cache = {}
fib(2) = 1 + 0 = 1

Why: Base cases stop recursion

Step 6: Store fib(2) = 1 in cache

cache = {2: 1}

Why: Remember fib(2) to avoid recomputing

Step 7: Call fib(1), base case returns 1

cache = {2: 1}

Why: fib(1) is base case

Step 8: Calculate fib(3) = fib(2) + fib(1) = 1 + 1 = 2 and store in cache

cache = {2: 1, 3: 2}

Why: Store fib(3) result for reuse

Step 9: Call fib(2) again, found in cache as 1

cache = {2: 1, 3: 2}

Why: Reuse cached fib(2) to save time

Step 10: Calculate fib(4) = fib(3) + fib(2) = 2 + 1 = 3 and store in cache

cache = {2: 1, 3: 2, 4: 3}

Why: Store fib(4) result for reuse

Step 11: Call fib(3) again, found in cache as 2

cache = {2: 1, 3: 2, 4: 3}

Why: Reuse cached fib(3) to save time

Step 12: Calculate fib(5) = fib(4) + fib(3) = 3 + 2 = 5 and store in cache

cache = {2: 1, 3: 2, 4: 3, 5: 5}

Why: Final answer stored for fib(5)

Result:

fib sequence cache: {2:1, 3:2, 4:3, 5:5}
Answer: 5

Annotated Code

DSA Typescript

class Fibonacci {
  private cache: Map<number, number> = new Map();

  fib(n: number): number {
    if (n <= 1) return n; // base case

    if (this.cache.has(n)) {
      return this.cache.get(n)!; // return cached result
    }

    const result = this.fib(n - 1) + this.fib(n - 2); // recursive calls
    this.cache.set(n, result); // store result in cache
    return result;
  }
}

const fibCalc = new Fibonacci();
console.log(fibCalc.fib(5));

if (n <= 1) return n; // base case

stop recursion when n is 0 or 1

if (this.cache.has(n)) { return this.cache.get(n)!; }

return cached answer if available to avoid recomputation

const result = this.fib(n - 1) + this.fib(n - 2);

compute fib(n) by recursive calls to smaller problems

this.cache.set(n, result);

store computed result in cache for future reuse

Output

5

Complexity Analysis

Time: O(n) because each fib number from 0 to n is computed once and then reused

Space: O(n) because the cache stores results for all numbers up to n and recursion stack can go up to n

vs Alternative: Without memoization, time is O(2^n) due to repeated calculations; memoization reduces it drastically to O(n)

Edge Cases

n = 0 (smallest input)

Returns 0 immediately as base case

DSA Typescript

if (n <= 1) return n; // base case

n = 1 (smallest positive input)

Returns 1 immediately as base case

DSA Typescript

if (n <= 1) return n; // base case

Repeated calls with same n

Returns cached result instantly without recursion

DSA Typescript

if (this.cache.has(n)) { return this.cache.get(n)!; }

When to Use This Pattern

When you see a problem with overlapping recursive calls and repeated subproblems, reach for memoization to save time by caching results.

Common Mistakes

Mistake: Not checking cache before recursive calls, causing repeated work
Fix: Always check if result is cached before computing recursively

Mistake: Not storing computed results in cache after recursion
Fix: Store the result in cache immediately after computing to reuse later

Mistake: Using global variables without encapsulation causing bugs
Fix: Use a class or closure to keep cache private and avoid side effects

Summary

Memoization stores answers to recursive calls to avoid repeating work.

Use it when recursion solves the same subproblems multiple times.

The key is to remember results so you never solve the same problem twice.