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.

Practice

1. Why do we use dynamic programming instead of just recursion for some problems?

easy

A. Because recursion alone can repeat the same calculations many times, making it slow.

B. Because recursion cannot solve problems with multiple steps.

C. Because dynamic programming uses loops instead of functions.

D. Because recursion always causes errors in large problems.

Solution

1. Step 1: Understand recursion's limitation

   Recursion solves problems by calling itself but often recalculates the same results multiple times.

2. Step 2: Recognize dynamic programming's advantage

   Dynamic programming stores results of subproblems to avoid repeated work, making it faster.

3. Final Answer:

   Because recursion alone can repeat the same calculations many times, making it slow. -> Option A

4. Quick Check:

   Recursion repeats work, DP saves results [OK]

Hint: DP saves repeated results to speed up recursion [OK]

Common Mistakes:

• Thinking recursion cannot handle multiple steps
• Believing DP only uses loops
• Assuming recursion always causes errors

2. Which of the following TypeScript function signatures correctly shows a recursive function with memoization parameter for dynamic programming?

easy

A. function fib(n: number): number[]

B. function fib(n: string, memo: number): number

C. function fib(memo: number[], n: number): void

D. function fib(n: number, memo: number[] = []): number

Solution

1. Step 1: Check parameter types and order

   function fib(n: number, memo: number[] = []): number has number n and optional memo array with default empty array, suitable for memoization.

2. Step 2: Verify return type and parameters

   function fib(n: number, memo: number[] = []): number returns number (the Fibonacci number), others have wrong types or order.

3. Final Answer:

   function fib(n: number, memo: number[] = []): number -> Option D

4. Quick Check:

   Correct memo param with default empty array [OK]

Hint: Memo param usually an array with default empty value [OK]

Common Mistakes:

• Swapping parameter order
• Using wrong return type
• Not providing default value for memo

3. What is the output of this TypeScript code snippet?

function fib(n: number, memo: number[] = []): number {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. 3

B. 8

C. 5

D. Undefined

Solution

1. Step 1: Trace fib(5) calls with memo

   fib(5) = fib(4) + fib(3), memo stores results to avoid repeats.

2. Step 2: Calculate fib values

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci of 5 = 5 [OK]

Hint: Memo avoids repeats; fib(5) = 5 [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect
• Assuming output is sum of all calls

4. Identify the bug in this recursive Fibonacci function without memoization:

function fib(n: number): number {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fib(n - 1) + fib(n - 2);
}
console.log(fib(40));

medium

A. It will cause a stack overflow error for large n.

B. It returns wrong Fibonacci numbers for n > 2.

C. It uses memoization incorrectly.

D. It has a syntax error in the return statement.

Solution

1. Step 1: Analyze recursion depth for fib(40)

   Without memoization, fib(40) causes many repeated calls, leading to deep recursion.

2. Step 2: Understand consequences

   Deep recursion can cause stack overflow or very slow execution, but no syntax or logic errors.

3. Final Answer:

   It will cause a stack overflow error for large n. -> Option A

4. Quick Check:

   Deep recursion without memo causes stack overflow [OK]

Hint: Large n without memo causes stack overflow [OK]

Common Mistakes:

• Thinking it returns wrong values
• Assuming syntax error exists
• Confusing memoization usage

5. You want to find the minimum number of coins to make a sum using recursion. Why is dynamic programming necessary here instead of plain recursion?

function minCoins(coins: number[], sum: number): number {
  if (sum === 0) return 0;
  let res = Infinity;
  for (let coin of coins) {
    if (coin <= sum) {
      let subRes = minCoins(coins, sum - coin);
      if (subRes !== Infinity && subRes + 1 < res) {
        res = subRes + 1;
      }
    }
  }
  return res;
}

hard

A. Because recursion cannot handle arrays as input parameters.

B. Because recursion alone recalculates the same sums multiple times, causing slow performance.

C. Because dynamic programming uses loops instead of recursion.

D. Because recursion always returns Infinity for large sums.

Solution

1. Step 1: Identify repeated subproblems in recursion

   The function calls itself with the same sums multiple times, recalculating results.

2. Step 2: Explain dynamic programming benefit

   DP stores results for sums already computed, avoiding repeated work and speeding up solution.

3. Final Answer:

   Because recursion alone recalculates the same sums multiple times, causing slow performance. -> Option B

4. Quick Check:

   DP saves repeated sum calculations [OK]

Hint: DP caches results to avoid repeated sum calculations [OK]

Common Mistakes:

• Thinking recursion can't handle arrays
• Believing DP replaces recursion with loops
• Assuming recursion returns Infinity always