Memoization to Optimize Recursion in DSA C++ - Execution Trace

Concept Flow - Memoization to Optimize Recursion

Start Recursive Call

↓

Check if Result in Memo?

Yes→Return Memoized Result

No↓

Compute Result Recursively

↓

Store Result in Memo

↓

Return Result

↓

End Call

The recursion first checks if the answer is already saved. If yes, it returns it immediately. Otherwise, it computes the answer, saves it, and returns it.

Execution Sample

DSA C++

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];
}

Computes Fibonacci number n using recursion with memoization to avoid repeated calculations.

Execution Table

Step	Operation	n	Memo Before	Memo After	Returned Value	Visual State
1	fib(4) called	4	[-1, -1, -1, -1, -1]	[-1, -1, -1, -1, -1]	?	Call stack: fib(4)
2	fib(4) checks memo[4]	4	[-1, -1, -1, -1, -1]	[-1, -1, -1, -1, -1]	Not found	Proceed to compute fib(4)
3	fib(3) called from fib(4)	3	[-1, -1, -1, -1, -1]	[-1, -1, -1, -1, -1]	?	Call stack: fib(4) -> fib(3)
4	fib(3) checks memo[3]	3	[-1, -1, -1, -1, -1]	[-1, -1, -1, -1, -1]	Not found	Proceed to compute fib(3)
5	fib(2) called from fib(3)	2	[-1, -1, -1, -1, -1]	[-1, -1, -1, -1, -1]	?	Call stack: fib(4) -> fib(3) -> fib(2)
6	fib(2) checks memo[2]	2	[-1, -1, -1, -1, -1]	[-1, -1, -1, -1, -1]	Not found	Proceed to compute fib(2)
7	fib(1) called from fib(2)	1	[-1, -1, -1, -1, -1]	[-1, -1, -1, -1, -1]	1	Base case reached, returns 1
8	fib(0) called from fib(2)	0	[-1, -1, -1, -1, -1]	[-1, -1, -1, -1, -1]	0	Base case reached, returns 0
9	fib(2) computes memo[2] = 1 + 0	2	[-1, -1, -1, -1, -1]	[-1, -1, 1, -1, -1]	1	Memo updated at index 2
10	fib(1) called from fib(3)	1	[-1, -1, 1, -1, -1]	[-1, -1, 1, -1, -1]	1	Base case reached, returns 1
11	fib(3) computes memo[3] = memo[2] + 1 = 1 + 1	3	[-1, -1, 1, -1, -1]	[-1, -1, 1, 2, -1]	2	Memo updated at index 3
12	fib(2) called from fib(4)	2	[-1, -1, 1, 2, -1]	[-1, -1, 1, 2, -1]	1	Memo hit, returns 1 directly
13	fib(4) computes memo[4] = memo[3] + memo[2] = 2 + 1	4	[-1, -1, 1, 2, -1]	[-1, -1, 1, 2, 3]	3	Memo updated at index 4
14	fib(4) returns 3	4	[-1, -1, 1, 2, 3]	[-1, -1, 1, 2, 3]	3	Final result returned
15	End	-	[-1, -1, 1, 2, 3]	[-1, -1, 1, 2, 3]	3	All calls completed

💡 fib(4) returns final value 3 after memoizing intermediate results

Variable Tracker

Variable	Start	After Step 9	After Step 11	After Step 13	Final
memo	[-1, -1, -1, -1, -1]	[-1, -1, 1, -1, -1]	[-1, -1, 1, 2, -1]	[-1, -1, 1, 2, 3]	[-1, -1, 1, 2, 3]
n	4	2	3	4	4
Returned Value	?	1	2	3	3

Key Moments - 3 Insights

Why does fib(2) get computed twice but only once stored in memo?

fib(2) is first computed at step 9 and stored in memo. Later at step 12, fib(2) is called again but memo[2] is found, so the stored value is returned immediately without recomputation.

Why do we check memo[n] before computing fib(n)?

Checking memo[n] first (steps 2, 4, 6, 12) avoids repeated calculations by returning stored results, saving time and preventing redundant recursive calls.

What happens if we don't store the result in memo after computing?

If we skip storing (like step 9, 11, 13), future calls won't find the result in memo and will recompute, losing the optimization benefit of memoization.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of memo after step 11?

A [-1, -1, 1, -1, -1]

B [-1, -1, -1, -1, -1]

C [-1, -1, 1, 2, -1]

D [-1, -1, 1, 2, 3]

💡 Hint

Check the 'Memo After' column at step 11 in the execution_table

At which step does fib(4) first return a value?

A Step 13

B Step 14

C Step 12

D Step 9

💡 Hint

Look at the 'Returned Value' and 'Operation' columns for fib(4) returning

If memo was not checked before recursion, how would the number of calls change?

A Number of calls would increase due to repeated calculations

B Number of calls would decrease

C Number of calls would stay the same

D Number of calls would be zero

💡 Hint

Refer to key_moments explaining the purpose of memoization to avoid repeated calls

Concept Snapshot

Memoization stores results of recursive calls in a data structure (like an array) to avoid repeated work.
Before computing fib(n), check if memo[n] exists.
If yes, return memo[n] immediately.
If no, compute recursively, store in memo, then return.
This reduces exponential recursion to linear time.

Full Transcript

Memoization optimizes recursion by saving results of function calls. When fib(n) is called, it first checks if the answer is already stored in memo. If found, it returns that value immediately, skipping repeated calculations. If not found, it computes fib(n) recursively, stores the result in memo, and returns it. This process is repeated for smaller values until base cases are reached. The execution table shows each step, including calls, memo checks, updates, and returns. The variable tracker shows how memo array fills up with computed Fibonacci numbers. Key moments clarify why memo checks happen before recursion and why storing results is essential. The visual quiz tests understanding of memo state and recursion flow. Overall, memoization changes slow exponential recursion into fast linear computation by remembering past answers.

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)