Why Dynamic Programming and When Recursion Alone Fails in DSA C++ - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate Fibonacci numbers using simple recursion.

DSA C++

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) [1] fib(n-2);
}

Drag options to blanks, or click blank then click option'

A/

B-

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Forgetting the base case for n <= 1.

The Fibonacci sequence is defined as fib(n) = fib(n-1) + fib(n-2). So, the operator between the two recursive calls is '+'.

2fill in blank

medium

Complete the code to add memoization to the recursive Fibonacci function.

DSA C++

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

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong operators causing incorrect sums.

Not checking if memo[n] is already computed.

Memoization stores results to avoid repeated calculations. The Fibonacci sum remains the same, so '+' is used.

3fill in blank

hard

Fix the error in the recursive factorial function to correctly compute factorial.

DSA C++

int factorial(int n) {
    if (n == 0) return 1;
    return n [1] factorial(n-1);
}

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' or '-' instead of '*'.

Missing base case for n == 0.

Factorial is the product of all positive integers up to n, so the operator must be '*'.

4fill in blank

hard

Fill both blanks to create a bottom-up dynamic programming solution for Fibonacci.

DSA C++

int fibDP(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-[1]] [2] dp[i-2];
    }
    return dp[n];
}

Drag options to blanks, or click blank then click option'

A1

B2

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices like 2 and 3.

Using '-' instead of '+'.

In bottom-up DP for Fibonacci, dp[i] = dp[i-1] + dp[i-2]. So blanks are '1' and '+'.

5fill in blank

hard

Fill all three blanks to implement memoized recursion for the Fibonacci sequence.

DSA C++

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

Drag options to blanks, or click blank then click option'

An

Bn-1

C+

Dn-2

Attempts:

3 left

💡 Hint

Common Mistakes

Using different indices for memo check and return.

Using wrong operator instead of '+'.

We check and return memo[n], so blanks 1 and 2 are 'n'. The operator is '+' for Fibonacci sum.

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