Memoization to Optimize Recursion in DSA C++ - Build from Scratch

Memoization to Optimize Recursion

📖 Scenario: Imagine you want to find the number of ways to climb a staircase with n steps. You can climb either 1 or 2 steps at a time. Calculating this using simple recursion can be slow because it repeats the same calculations many times.

🎯 Goal: You will build a program that uses memoization to remember previous results and speed up the calculation of ways to climb the stairs.

📋 What You'll Learn

Create a recursive function to calculate ways to climb stairs

Use a dictionary (map) to store results of subproblems

Use memoization to avoid repeated calculations

Print the number of ways to climb a staircase of 5 steps

💡 Why This Matters

🌍 Real World

Memoization is used in many real-world problems like calculating Fibonacci numbers, optimizing game moves, and speeding up complex calculations by remembering past results.

💼 Career

Understanding memoization helps in writing efficient algorithms, which is a key skill for software developers, especially in roles involving optimization and performance.

1

Create a map to store memoized results

Create a std::map<int, int> called memo to store previously calculated results for the number of ways to climb stairs.

DSA C++

#include 
#include 

int main() {
    // Create a map called memo to store results
    // Your code here
    return 0;
}

Hint

Use std::map<int, int> memo; inside main().

2

Add a variable for the number of steps

Add an integer variable called n and set it to 5 to represent the number of steps in the staircase.

DSA C++

#include 
#include 

int main() {
    std::map memo;
    // Create an integer n and set it to 5
    // Your code here
    return 0;
}

Hint

Write int n = 5; inside main().

3

Write a recursive function with memoization

Write a function called ways that takes an integer steps and a reference to std::map<int, int> called memo. The function should return the number of ways to climb steps stairs using recursion and memoization. Use these rules:
- If steps is 0 or 1, return 1.
- If steps is in memo, return the stored value.
- Otherwise, calculate ways(steps - 1, memo) + ways(steps - 2, memo), store it in memo[steps], and return it.

DSA C++

#include 
#include 

// Write the ways function here
// Your code here

int main() {
    std::map memo;
    int n = 5;

    return 0;
}

Hint

Define ways before main() with the described logic.

4

Print the number of ways to climb the stairs

Call the ways function with n and memo, then print the result using std::cout.

DSA C++

#include 
#include 

int ways(int steps, std::map& memo) {
    if (steps == 0 || steps == 1) {
        return 1;
    }
    if (memo.find(steps) != memo.end()) {
        return memo[steps];
    }
    memo[steps] = ways(steps - 1, memo) + ways(steps - 2, memo);
    return memo[steps];
}

int main() {
    std::map memo;
    int n = 5;
    // Call ways and print the result
    // Your code here
    return 0;
}

Hint

Use std::cout << ways(n, memo) << std::endl; inside main().

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)