Memoization to Optimize Recursion in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is memoization in the context of recursion?

Memoization is a technique to store the results of expensive function calls and reuse them when the same inputs occur again, avoiding repeated calculations.

beginner

How does memoization improve the performance of recursive functions?

By saving the results of recursive calls in a cache, memoization prevents the function from recalculating the same values multiple times, reducing time complexity.

intermediate

In C++, which data structure is commonly used to implement memoization for recursion?

A std::unordered_map or std::vector is commonly used to store computed results keyed by input parameters for quick lookup.

intermediate

What is the difference between memoization and dynamic programming?

Memoization is a top-down approach that caches results of recursive calls, while dynamic programming is often a bottom-up approach that builds solutions iteratively.

beginner

Why is memoization especially useful in problems like Fibonacci sequence calculation?

Because naive recursion recalculates the same Fibonacci numbers many times, memoization stores these results to avoid redundant work, making the solution efficient.

What does memoization primarily help to reduce in recursive functions?

A Input size

B Memory usage

C Code length

D Repeated calculations

Memoization stores results of previous calls to avoid repeated calculations.

Which C++ container is best suited for memoization when input parameters are integers?

A std::vector

B std::list

C std::stack

D std::queue

std::vector allows fast access by index, ideal for integer keys in memoization.

Memoization is an example of which programming technique?

A Top-down dynamic programming

B Bottom-up dynamic programming

C Greedy algorithm

D Divide and conquer

Memoization uses a top-down approach by caching recursive calls.

What is the main drawback of not using memoization in recursive Fibonacci calculation?

A Stack overflow

B Exponential time complexity

C Incorrect results

D Memory leaks

Without memoization, Fibonacci recursion has exponential time complexity due to repeated calls.

Which of the following is NOT a benefit of memoization?

A Faster execution

B Reduced redundant work

C Lower memory usage

D Simpler code debugging

Memoization uses extra memory to store results, so it does not reduce memory usage.

Explain how memoization optimizes a recursive function using the Fibonacci sequence as an example.

Think about how many times the same Fibonacci number is calculated without memoization.

Describe the difference between memoization and bottom-up dynamic programming.

Consider the approach direction and how results are computed.

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)