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 some problems?

Plain recursion often recalculates the same subproblems multiple times, leading to a lot of repeated work and slow performance.

beginner

What does Dynamic Programming (DP) do differently compared to plain recursion?

DP saves the results of subproblems so they can be reused later, avoiding repeated calculations and making the solution faster.

intermediate

Why is overlapping subproblems important for using Dynamic Programming?

Overlapping subproblems mean the same smaller problems appear many times. DP works well here by storing answers to these problems once and reusing them.

beginner

What is 'memoization' in the context of Dynamic Programming?

Memoization is a technique where we store the results of recursive calls in a table (like an array) so we don't compute them again.

beginner

Give an example of a problem where recursion alone is inefficient but Dynamic Programming helps.

Calculating Fibonacci numbers using plain recursion is slow because it repeats work. Using DP with memoization or tabulation makes it fast.

Why does plain recursion often lead to slow solutions?

A It recalculates the same subproblems multiple times

B It uses too much memory

C It never reaches the base case

D It only works for small inputs

Plain recursion repeats calculations for the same subproblems, causing slow performance.

What is the main benefit of Dynamic Programming?

A It always uses less memory

B It uses more recursion

C It ignores base cases

D It stores results of subproblems to avoid repeated work

DP saves subproblem results to reuse them, speeding up the solution.

Which condition makes a problem suitable for Dynamic Programming?

A No base case

B No recursion needed

C Overlapping subproblems and optimal substructure

D Only one subproblem

DP works well when subproblems overlap and the problem has optimal substructure.

What is memoization?

A Ignoring repeated calculations

B Storing results of recursive calls to reuse later

C Calling functions repeatedly

D Using loops instead of recursion

Memoization saves results of recursive calls to avoid recalculating them.

Which problem is a classic example where DP improves over recursion?

A Fibonacci number calculation

B Sorting an array

C Finding maximum in an array

D Printing numbers from 1 to n

Fibonacci calculation with recursion repeats work; DP speeds it up by storing results.

Explain why recursion alone can be inefficient and how Dynamic Programming solves this problem.

Think about how many times the same small problem is solved in recursion.

Describe the role of memoization in Dynamic Programming and how it differs from plain recursion.

Focus on storing and reusing answers.

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 loops.

C. Because dynamic programming uses less memory than recursion always.

D. Because recursion is only for sorting 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: Role of dynamic programming

   Dynamic programming stores these repeated results to avoid recalculations, making the solution 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 can't handle loops
• Believing DP always uses less memory
• Assuming recursion is only for sorting

2. Which of the following is the correct way to declare a memoization array in C for dynamic programming?

easy

A. memo = new int[1000];

B. int memo[] = 0;

C. int memo[1000] = {0};

D. int memo(1000);

Solution

1. Step 1: Check C array declaration syntax

   In C, arrays are declared with size and optional initialization like int memo[1000] = {0};

2. Step 2: Analyze options

   int memo[1000] = {0}; uses correct syntax. int memo[] = 0; is invalid syntax. int memo(1000); uses parentheses which is wrong in C. memo = new int[1000]; uses 'new' which is C++ syntax.

3. Final Answer:

   int memo[1000] = {0}; -> Option C

4. Quick Check:

   C arrays use brackets [] [OK]

Hint: Use brackets [] to declare arrays in C [OK]

Common Mistakes:

• Using C++ 'new' in C code
• Using parentheses instead of brackets
• Not initializing memo array properly

3. What will be the output of the following C code snippet?

int fib(int n, 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() {
  int memo[6];
  for (int i = 0; i < 6; i++) memo[i] = -1;
  printf("%d", fib(5, memo));
  return 0;
}

medium

A. 5

B. 8

C. 13

D. Runtime error

Solution

1. Step 1: Understand the Fibonacci function with memoization

   fib(5) calculates Fibonacci of 5 using memo array initialized with -1 to store results.

2. Step 2: Calculate fib(5)

   Fibonacci sequence: 0,1,1,2,3,5. fib(5) = 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

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

Common Mistakes:

• Confusing fib(5) with fib(6)
• Not initializing memo causing wrong results
• Assuming runtime error due to memo usage

4. Identify the error 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-3);
}

medium

A. Base cases are missing.

B. It should call fib(n-2) instead of fib(n-3).

C. Function will cause infinite recursion.

D. No error, code is correct.

Solution

1. Step 1: Check recursive calls in Fibonacci

   Fibonacci is defined as fib(n) = fib(n-1) + fib(n-2).

2. Step 2: Identify incorrect call

   Code calls fib(n-3) instead of fib(n-2), which is wrong and breaks Fibonacci definition.

3. Final Answer:

   It should call fib(n-2) instead of fib(n-3). -> Option B

4. Quick Check:

   Fibonacci uses n-1 and n-2 calls [OK]

Hint: Fibonacci sums fib(n-1) and fib(n-2) only [OK]

Common Mistakes:

• Using wrong recursive calls
• Missing base cases
• Thinking code is correct as is

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

hard

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

B. Recursion always gives wrong answers; dynamic programming is always correct.

C. Recursion uses loops which slow it down; dynamic programming uses no loops.

D. Recursion repeats subproblems; dynamic programming stores results to avoid repeats.

Solution

1. Step 1: Understand recursion inefficiency

   Recursion tries all combinations repeatedly, recalculating same subproblems many times.

2. Step 2: How dynamic programming improves

   Dynamic programming saves results of subproblems (like minimum coins for smaller values) to reuse, reducing time drastically.

3. Final Answer:

   Recursion repeats subproblems; dynamic programming stores results to avoid repeats. -> Option D

4. Quick Check:

   DP saves repeated work, recursion repeats it [OK]

Hint: DP stores sub-results; recursion repeats work [OK]

Common Mistakes:

• Thinking recursion can't handle multiple coins
• Believing recursion uses loops
• Assuming recursion is always wrong