Memoization to Optimize Recursion in DSA C++

Mental Model

Memoization saves answers to small problems so we don't solve them again. It makes recursion faster by remembering past results.

Analogy: Imagine you are solving a puzzle and write down each solved piece on a sticky note. Next time you see the same piece, you just read the note instead of solving it again.

fib(5)
  ↓
fib(4) + fib(3)
  ↓       ↓
fib(3)+fib(2) fib(2)+fib(1)
  ↓
[cache stores fib(2)=1, fib(3)=2, ...]

Dry Run Walkthrough

Input: Calculate fib(5) using recursion with memoization

Goal: Compute fib(5) efficiently by storing intermediate results to avoid repeated work

Step 1: Call fib(5), cache empty

cache = {}
Call stack: fib(5) ↑

Why: Start computing fib(5), no cached answers yet

Step 2: Call fib(4) from fib(5), cache still empty

cache = {}
Call stack: fib(5) -> fib(4) ↑

Why: Need fib(4) to compute fib(5)

Step 3: Call fib(3) from fib(4), cache still empty

cache = {}
Call stack: fib(5) -> fib(4) -> fib(3) ↑

Why: Need fib(3) to compute fib(4)

Step 4: Call fib(2) from fib(3), cache still empty

cache = {}
Call stack: fib(5) -> fib(4) -> fib(3) -> fib(2) ↑

Why: Need fib(2) to compute fib(3)

Step 5: fib(2) computes fib(1) + fib(0) = 1 + 0 = 1, store in cache

cache = {2:1}
Call stack: fib(5) -> fib(4) -> fib(3) ↑

Why: fib(2) computed using base cases fib(1)=1 and fib(0)=0, save result

Step 6: Call fib(1) from fib(3), cache unchanged

cache = {2:1}
Call stack: fib(5) -> fib(4) -> fib(3) -> fib(1) ↑

Why: Need fib(1) to compute fib(3)

Step 7: fib(1) base case returns 1

cache = {2:1}
Call stack: fib(5) -> fib(4) -> fib(3) ↑

Why: fib(1) base case

Step 8: Compute fib(3) = fib(2)+fib(1) = 1+1=2, store in cache

cache = {2:1, 3:2}
Call stack: fib(5) -> fib(4) ↑

Why: fib(3) computed from cached fib(2) and fib(1)

Step 9: Call fib(2) from fib(4), found in cache

cache = {2:1, 3:2}
Call stack: fib(5) -> fib(4) ↑

Why: Reuse cached fib(2) to avoid recomputation

Step 10: Compute fib(4) = fib(3)+fib(2) = 2+1=3, store in cache

cache = {2:1, 3:2, 4:3}
Call stack: fib(5) ↑

Why: fib(4) computed from cached fib(3) and fib(2)

Step 11: Call fib(3) from fib(5), found in cache

cache = {2:1, 3:2, 4:3}
Call stack: fib(5) ↑

Why: Reuse cached fib(3) to avoid recomputation

Step 12: Compute fib(5) = fib(4)+fib(3) = 3+2=5, store in cache

cache = {2:1, 3:2, 4:3, 5:5}
Call stack: empty

Why: fib(5) computed from cached fib(4) and fib(3)

Result:

cache = {2:1, 3:2, 4:3, 5:5}
Answer: fib(5) = 5

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>

class Fibonacci {
public:
    std::unordered_map<int, int> cache;

    int fib(int n) {
        if (n <= 1) return n; // base case
        if (cache.find(n) != cache.end())
            return cache[n]; // return cached result
        // compute and cache
        cache[n] = fib(n - 1) + fib(n - 2);
        return cache[n];
    }
};

int main() {
    Fibonacci fibObj;
    int n = 5;
    int result = fibObj.fib(n);
    std::cout << "fib(" << n << ") = " << result << std::endl;
    return 0;
}

if (n <= 1) return n; // base case

return base case values 0 or 1 immediately

if (cache.find(n) != cache.end()) return cache[n]; // return cached result

check if result already computed to avoid repeated work

cache[n] = fib(n - 1) + fib(n - 2);

compute fib(n) recursively and store in cache

Output

fib(5) = 5

Complexity Analysis

Time: O(n) because each fib number from 0 to n is computed once and stored

Space: O(n) for the cache storing results and recursion call stack

vs Alternative: Without memoization, time is O(2^n) due to repeated calls; memoization reduces it to linear time

Edge Cases

n = 0 (smallest input)

Returns 0 immediately as base case

DSA C++

if (n <= 1) return n; // base case

n = 1 (smallest positive input)

Returns 1 immediately as base case

DSA C++

if (n <= 1) return n; // base case

Repeated calls with same n

Uses cached result, no recomputation

DSA C++

if (cache.find(n) != cache.end())
    return cache[n]; // return cached result

When to Use This Pattern

When you see a problem with overlapping recursive calls and repeated subproblems, reach for memoization to store and reuse results, making recursion efficient.

Common Mistakes

Mistake: Not checking cache before recursive calls, causing repeated work
Fix: Add cache lookup before recursion to return stored results immediately

Mistake: Not storing computed results in cache after recursion
Fix: Store the computed value in cache before returning it

Mistake: Using recursion without base cases leading to infinite calls
Fix: Always include base cases that return immediately

Summary

Memoization stores results of recursive calls to avoid repeated work and speed up computation.

Use memoization when recursion solves the same subproblems multiple times.

The key insight is to remember past answers so you never solve the same problem twice.

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)