Memoization to Optimize Recursion in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Fibonacci with Memoization

What is the output of the following C++ code that uses memoization to compute Fibonacci numbers?

DSA C++

#include <iostream>
#include <vector>

int fib(int n, std::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() {
    int n = 6;
    std::vector<int> memo(n+1, -1);
    std::cout << fib(n, memo) << std::endl;
    return 0;
}

A 8

B 21

C 15

D 13

💡 Hint

Recall that Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8, 13...

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, ... so fib(6) = 8.

❓ Predict Output

intermediate

Memoization Cache State After Calls

After calling fib(5) with memo initialized to -1, what is the state of the memo vector?

DSA C++

#include <iostream>
#include <vector>

int fib(int n, std::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() {
    int n = 5;
    std::vector<int> memo(n+1, -1);
    fib(n, memo);
    for (int i = 0; i <= n; ++i) {
        std::cout << memo[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

A -1 1 1 2 3 5

B 0 1 1 2 3 5

C -1 -1 1 2 3 5

D 0 1 2 3 5 -1

💡 Hint

Base cases n <= 1 return without storing in memo; only n > 1 values are stored.

After fib(5), memo[0] = -1 and memo[1] = -1 (base cases not stored), memo[2]=1, memo[3]=2, memo[4]=3, memo[5]=5.

🔧 Debug

advanced

Identify the Runtime Error in Memoized Fibonacci

What runtime error will occur when running this code?

DSA C++

#include <iostream>
#include <vector>

int fib(int n, std::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() {
    int n = 10;
    std::vector<int> memo(5, -1); // Incorrect size
    std::cout << fib(n, memo) << std::endl;
    return 0;
}

A Logical error: outputs wrong Fibonacci number

B No error, outputs 55

C Compilation error due to vector size mismatch

D Segmentation fault due to out-of-range vector access

💡 Hint

Check if memo vector size matches the maximum n used in recursion.

The memo vector size is 5 but fib(10) accesses memo[10], causing out-of-range access and segmentation fault.

🧠 Conceptual

advanced

Why Memoization Improves Recursive Fibonacci

Why does memoization improve the performance of the recursive Fibonacci function?

A It uses a loop instead of recursion

B It stores previously computed results to avoid repeated calculations

C It sorts the input before computing Fibonacci

D It reduces the Fibonacci sequence length

💡 Hint

Think about how recursion repeats calls for the same inputs.

Memoization saves results of function calls so the same calculations are not done multiple times, reducing time complexity.

❓ Predict Output

expert

Output of Memoized Recursive Function with Custom Cache

What is the output of this C++ code that uses memoization with a custom cache for a modified Fibonacci sequence?

DSA C++

#include <iostream>
#include <unordered_map>

int fib(int n, std::unordered_map<int,int>& cache) {
    if (n <= 1) return n;
    if (cache.find(n) != cache.end()) return cache[n];
    cache[n] = fib(n-1, cache) + 2 * fib(n-2, cache);
    return cache[n];
}

int main() {
    int n = 4;
    std::unordered_map<int,int> cache;
    std::cout << fib(n, cache) << std::endl;
    return 0;
}

A 5

B 8

C 9

D 10

💡 Hint

Calculate fib(4) using fib(n) = fib(n-1) + 2*fib(n-2) with base fib(0)=0, fib(1)=1.

fib(2)=fib(1)+2*fib(0)=1+0=1; fib(3)=fib(2)+2*fib(1)=1+2=3; fib(4)=fib(3)+2*fib(2)=3+2=5.

Practice

1. What is the main purpose of using memoization in recursive functions?

easy

A. To make the function run slower by adding extra steps

B. To avoid using any variables inside the function

C. To convert recursion into iteration automatically

D. To store results of expensive function calls and reuse them

Solution

1. Step 1: Understand what memoization does

   Memoization saves the results of function calls so that if the same inputs occur again, the function can return the saved result instead of recalculating.

2. Step 2: Identify the effect on performance

   This reuse of results reduces repeated work and speeds up the function.

3. Final Answer:

   To store results of expensive function calls and reuse them -> Option D

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated results to speed recursion [OK]

Common Mistakes:

• Thinking memoization slows down the function
• Confusing memoization with converting recursion to loops
• Believing memoization removes all variables

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

easy

A. std::unordered_map<int> memo;

B. std::vector<int> memo(100, -1);

C. int memo[];

D. map<int> memo;

Solution

1. Step 1: Identify suitable container for memoization

   We need a container that can store integer results indexed by integer keys. std::vector<int> initialized with -1 is common for fixed size memoization.

2. Step 2: Check syntax correctness

   std::vector<int> memo(100, -1); correctly declares a vector of size 100 with all values -1, which can be used to check if a value is computed.

3. Final Answer:

   std::vector<int> memo(100, -1); -> Option B

4. Quick Check:

   Vector with size and default value = Correct memo cache [OK]

Hint: Use vector with size and default -1 for memo cache [OK]

Common Mistakes:

• Using incomplete or wrong container syntax
• Not initializing memo with default values
• Using map without specifying key and value types

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

int fib(int n, std::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() {
  std::vector<int> memo(6, -1);
  std::cout << fib(5, memo);
  return 0;
}

medium

A. Error: vector index out of range

B. 8

C. 5

D. 3

Solution

1. Step 1: Understand Fibonacci calculation with memoization

   fib(5) calculates Fibonacci number at position 5 using memo to avoid repeated calls.

2. Step 2: Calculate fib(5)

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

3. Final Answer:

   5 -> Option C

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence: fib(5) = 5 [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Assuming vector size too small causes error
• Ignoring memoization effect on output

4. Consider this recursive function with memoization in C++:

int factorial(int n, std::vector<int>& memo) {
  if (n == 0) return 1;
  if (memo[n] != -1) return memo[n];
  memo[n] = n * factorial(n - 1, memo);
  return memo[n];
}

int main() {
  std::vector<int> memo(5, -1);
  std::cout << factorial(5, memo);
  return 0;
}

What is the error in this code?

medium

A. Vector size is too small causing out-of-range access

B. Base case condition is incorrect

C. Memoization check is missing

D. Factorial calculation formula is wrong

Solution

1. Step 1: Check vector size for memoization

   The vector memo has size 5, so valid indices are 0 to 4. But factorial(5) tries to access memo[5], which is out of range.

2. Step 2: Identify consequence of out-of-range access

   Accessing memo[5] causes undefined behavior or runtime error.

3. Final Answer:

   Vector size is too small causing out-of-range access -> Option A

4. Quick Check:

   Memo vector size < n causes error [OK]

Hint: Memo vector size must be >= n+1 to avoid errors [OK]

Common Mistakes:

• Ignoring vector size and indexing
• Thinking base case is wrong
• Assuming memo check is missing

5. You want to optimize a recursive function that calculates the number of ways to climb n stairs, taking 1 or 2 steps at a time. Which memoization approach below correctly applies to this problem in C++?

hard

A. Use a vector<int> memo(n+1, -1) and store results for each stair count

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

B. Use a vector<int> memo(n, 0) and store results only for even stairs

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

C. Use a map memo and store results only for odd stairs

int ways(int n, std::map& memo) {
if (n == 0) return 1;
if (n < 0) return 0;
if (memo.count(n)) return memo[n];
memo[n] = ways(n-1, memo) + ways(n-2, memo);
return memo[n];
}

D. Use a vector<int> memo(n+1, 0) but do not check memo before recursive calls

int ways(int n, std::vector<int>& memo) {
if (n == 0) return 1;
if (n < 0) return 0;
memo[n] = ways(n-1, memo) + ways(n-2, memo);
return memo[n];
}

Solution

1. Step 1: Understand memoization requirements

   Memo must store results for all n from 0 to n, so vector size n+1 with default -1 is correct.

2. Step 2: Check memo usage in recursion

   Before recursive calls, check if memo[n] is computed (not -1). If yes, return memo[n]. Otherwise, compute and store.

3. Step 3: Analyze options

   Use a vector<int> memo(n+1, -1) and store results for each stair count int ways(int n, std::vector<int>& memo) { if (n == 0) return 1; if (n < 0) return 0; if (memo[n] != -1) return memo[n]; memo[n] = ways(n-1, memo) + ways(n-2, memo); return memo[n]; } correctly implements memoization with vector size n+1, default -1, and memo check before recursion.

4. Final Answer:

   Option A code correctly applies memoization for climbing stairs problem -> Option A

5. Quick Check:

   Memo vector size n+1 and check before recursion = Correct [OK]

Hint: Memo vector size n+1 with -1 and check before recursion [OK]

Common Mistakes:

• Using wrong vector size causing out-of-range errors
• Not checking memo before recursive calls
• Storing results only for some stairs (odd/even)