Why Dynamic Programming and When Recursion Alone Fails in DSA C++ - Quick Recap

Recall & Review

beginner

What is the main problem with using plain recursion for problems with overlapping subproblems?

Plain recursion often recalculates the same subproblems multiple times, leading to exponential time complexity and inefficiency.

beginner

Define Dynamic Programming in simple terms.

Dynamic Programming is a method to solve problems by breaking them into smaller parts, solving each part once, and saving the answers to avoid repeated work.

intermediate

Why does Dynamic Programming improve performance compared to plain recursion?

Because it stores results of subproblems (memoization or tabulation), so each subproblem is solved only once, reducing time complexity from exponential to polynomial.

intermediate

What are the two main approaches to implement Dynamic Programming?

1. Top-down approach with memoization (recursion + caching results). 2. Bottom-up approach with tabulation (iterative computation from smallest subproblems).

beginner

Give a real-life analogy for why Dynamic Programming is useful.

Like cooking a big meal by preparing ingredients once and reusing them in many dishes, Dynamic Programming solves parts once and reuses results to save time.

What happens when recursion solves overlapping subproblems without optimization?

A It always runs in linear time.

B It recalculates the same subproblems multiple times.

C It uses less memory than Dynamic Programming.

D It solves each subproblem only once.

Plain recursion recalculates overlapping subproblems repeatedly, causing inefficiency.

Which technique helps avoid repeated calculations in recursion?

A Memoization

B Brute force

C Sorting

D Greedy algorithm

Memoization stores results of subproblems to avoid recalculating them.

Dynamic Programming is best used when a problem has:

A No repeated subproblems

B Random inputs

C Only one solution path

D Overlapping subproblems and optimal substructure

DP works well when subproblems overlap and the problem can be broken into optimal subproblems.

Which approach uses iteration to solve subproblems from smallest to largest?

A Bottom-up tabulation

B Top-down memoization

C Plain recursion

D Divide and conquer

Bottom-up tabulation solves subproblems iteratively starting from the smallest.

Why might plain recursion fail for large inputs?

A Because it always returns wrong answers

B Because it uses too little memory

C Because it can cause stack overflow and exponential time complexity

D Because it is iterative

Plain recursion can cause stack overflow and slow performance due to repeated calculations.

Explain why recursion alone can be inefficient for problems with overlapping subproblems and how Dynamic Programming solves this.

Think about how saving answers helps avoid repeating work.

Describe the difference between top-down and bottom-up approaches in Dynamic Programming.

One starts from the big problem, the other from the smallest parts.

Practice

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

easy

A. Because dynamic programming stores results to avoid repeated work

B. Because recursion is always slower than loops

C. Because recursion cannot solve problems with multiple choices

D. Because dynamic programming uses less memory than recursion

Solution

1. Step 1: Understand recursion's limitation

   Recursion often recalculates the same subproblems multiple times, causing inefficiency.

2. Step 2: Role of dynamic programming

   Dynamic programming saves results of subproblems to reuse them, avoiding repeated calculations.

3. Final Answer:

   Because dynamic programming stores results to avoid repeated work -> Option A

4. Quick Check:

   Memoization avoids repeated work = A [OK]

Hint: Dynamic programming saves sub-results to speed up recursion [OK]

Common Mistakes:

• Thinking recursion is always slower than loops
• Believing recursion can't handle multiple choices
• Assuming dynamic programming uses less memory always

2. Which of the following is the correct syntax to declare a memoization array for a Fibonacci function in C++?

easy

A. int memo[100] = {0};

B. int memo(100, -1);

C. vector<int> memo(100, -1);

D. int memo[] = new int[100];

Solution

1. Step 1: Identify correct C++ container for memoization

   Using vector<int> memo(100, -1); initializes a vector of size 100 with all values -1, suitable for memoization.

2. Step 2: Check other options

   int memo[100] = {0}; initializes array with zeros, not -1 (commonly used to mark unvisited). int memo(100, -1); uses wrong syntax for array. int memo[] = new int[100]; uses incorrect syntax for dynamic array in C++.

3. Final Answer:

   vector<int> memo(100, -1); -> Option C

4. Quick Check:

   Vector with size and initial value = D [OK]

Hint: Use vector<int> with size and -1 for memo arrays [OK]

Common Mistakes:

• Using C-style arrays without initialization
• Confusing array and vector syntax
• Initializing memo with zeros instead of -1

3. What is the output of the following C++ code snippet?

int fib(int n, vector<int>& memo) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}

int main() {
  vector<int> memo(6, -1);
  cout << fib(5, memo);
  return 0;
}

medium

A. 8

B. Runtime error

C. 13

D. 5

Solution

1. Step 1: Understand Fibonacci calculation with memoization

   fib(5) calculates Fibonacci number at position 5: 0,1,1,2,3,5...

2. Step 2: Trace fib(5) call

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

3. Final Answer:

   5 -> Option D

4. Quick Check:

   fib(5) = 5 with memoization [OK]

Hint: Fibonacci(5) = 5, memo avoids repeated calls [OK]

Common Mistakes:

• Confusing Fibonacci index starting at 0 or 1
• Expecting fib(5) to be 8 or 13
• Ignoring memo initialization

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

int fib(int n) {
  if (n == 0) return 0;
  if (n == 1) return 1;
  return fib(n-1) + fib(n-2);
}

int main() {
  cout << fib(50);
  return 0;
}

medium

A. Returns wrong Fibonacci number

B. Stack overflow due to deep recursion

C. Syntax error in function definition

D. No bug, works fine

Solution

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

   fib(50) calls fib(49) and fib(48), which further call many functions, causing very deep recursion.

2. Step 2: Consequence of deep recursion without memoization

   Repeated calls cause exponential time and likely stack overflow error due to too many recursive calls.

3. Final Answer:

   Stack overflow due to deep recursion -> Option B

4. Quick Check:

   Deep recursion without memo causes stack overflow [OK]

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

Common Mistakes:

• Thinking syntax error exists
• Assuming function returns wrong value
• Believing no bug exists

5. You want to find the minimum number of coins to make a sum using coins of denominations 1, 3, and 5. Why is recursion alone inefficient here, and how does dynamic programming help?

hard

A. Recursion alone repeats subproblems; dynamic programming stores results to reuse them

B. Recursion cannot handle multiple coin types; dynamic programming can

C. Recursion uses loops internally; dynamic programming uses recursion

D. Recursion always uses more memory than dynamic programming

Solution

1. Step 1: Understand recursion inefficiency in coin change

   Recursion tries all combinations repeatedly, recalculating same sums multiple times.

2. Step 2: How dynamic programming improves efficiency

   Dynamic programming saves results of sub-sums, so each is computed once and reused.

3. Final Answer:

   Recursion alone repeats subproblems; dynamic programming stores results to reuse them -> Option A

4. Quick Check:

   Memoization avoids repeated subproblems = A [OK]

Hint: Store sub-results to avoid repeated calculations [OK]

Common Mistakes:

• Thinking recursion can't handle multiple coin types
• Confusing recursion and loops
• Assuming recursion always uses more memory