Why Dynamic Programming and When Recursion Alone Fails in DSA Typescript - Why This Pattern

Mental Model

Recursion repeats work by solving the same problem many times. Dynamic programming saves answers to avoid repeating work.

Analogy: Imagine you are solving a big puzzle by breaking it into smaller pieces. If you forget which pieces you already solved, you waste time solving them again. Dynamic programming is like writing down solved pieces so you never redo them.

Recursion tree with repeated nodes:

       [5]
      /    \
   [4]      [3]
   /  \     /  \
 [3]  [2] [2]  [1]
  ↑      ↑  ↑
Repeated calls to [3] and [2]

Dry Run Walkthrough

Input: Calculate Fibonacci number for n=5 using recursion

Goal: Show how recursion repeats calculations and how dynamic programming avoids repeats

Step 1: Call fib(5), which calls fib(4) and fib(3)

fib(5) -> fib(4), fib(3)

Why: To find fib(5), we need fib(4) and fib(3)

Step 2: fib(4) calls fib(3) and fib(2)

fib(5) -> fib(4) -> fib(3), fib(2); fib(3) pending

Why: fib(4) depends on fib(3) and fib(2)

Step 3: fib(3) calls fib(2) and fib(1)

fib(5) -> fib(4) -> fib(3) -> fib(2), fib(1); fib(2) and fib(3) pending

Why: fib(3) depends on fib(2) and fib(1)

Step 4: fib(3) is called again from fib(5) directly, repeating work

fib(5) -> fib(3) -> fib(2), fib(1) repeated

Why: Recursion repeats fib(3) calculation multiple times

Step 5: Dynamic programming saves fib(3) and fib(2) results to reuse

Memo: fib(2)=1, fib(3)=2 saved; fib(5) uses saved values

Why: Avoid repeated calculations by storing results

Result:

Final fib(5) = 5 calculated efficiently using saved results
State: Memo {2:1, 3:2, 4:3, 5:5}

Annotated Code

DSA Typescript

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

  fib(n: number): number {
    if (n <= 1) return n; // base case
    if (this.memo.has(n)) return this.memo.get(n)!; // reuse saved result

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

const fibCalc = new Fibonacci();
const n = 5;
console.log(`fib(${n}) = ${fibCalc.fib(n)}`);

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

stop recursion when n is 0 or 1

if (this.memo.has(n)) return this.memo.get(n)!; // reuse saved result

return saved answer to avoid repeated work

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

recursive calls to smaller subproblems

this.memo.set(n, result); // save result

store computed result for future reuse

Output

fib(5) = 5

Complexity Analysis

Time: O(n) because each number from 0 to n is calculated once and saved

Space: O(n) for the memo storage and recursion call stack

vs Alternative: Naive recursion is O(2^n) due to repeated calls; dynamic programming reduces it to O(n)

Edge Cases

n = 0 or n = 1

Returns n immediately as base case without recursion

DSA Typescript

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

Repeated calls for same n

Memoized result is returned instantly, avoiding recursion

DSA Typescript

if (this.memo.has(n)) return this.memo.get(n)!; // reuse saved result

When to Use This Pattern

When you see a problem with overlapping subproblems and repeated recursive calls, reach for dynamic programming to save and reuse results efficiently.

Common Mistakes

Mistake: Not saving results causes exponential time due to repeated work
Fix: Use a memo structure to store and reuse computed answers

Mistake: Forgetting base cases leads to infinite recursion
Fix: Always define clear base cases to stop recursion

Summary

Dynamic programming saves repeated recursive work by storing answers.

Use it when recursion solves the same subproblems many times.

The key is to remember and reuse results instead of recalculating.