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 flow shows how recursion first checks for stored results to avoid repeated work, computes if needed, stores the result, then returns it.

Execution Sample

DSA C

int fib(int n, 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];
}

This code computes Fibonacci numbers using recursion with memoization to save intermediate results.

Execution Table

Step	Operation	Current n	Memo Access	Memo Update	Visual Memo State
1	Call fib(4)	4	memo[4] = -1 (not found)	None	[-1, -1, -1, -1, -1]
2	Call fib(3)	3	memo[3] = -1 (not found)	None	[-1, -1, -1, -1, -1]
3	Call fib(2)	2	memo[2] = -1 (not found)	None	[-1, -1, -1, -1, -1]
4	Call fib(1)	1	Base case	None	[-1, -1, -1, -1, -1]
5	Return 1	1	N/A	None	[-1, -1, -1, -1, -1]
6	Call fib(0)	0	Base case	None	[-1, -1, -1, -1, -1]
7	Return 0	0	N/A	None	[-1, -1, -1, -1, -1]
8	Compute fib(2) = 1 + 0	2	N/A	memo[2] = 1	[-1, -1, 1, -1, -1]
9	Return 1	2	N/A	None	[-1, -1, 1, -1, -1]
10	Call fib(1)	1	Base case	None	[-1, -1, 1, -1, -1]
11	Return 1	1	N/A	None	[-1, -1, 1, -1, -1]
12	Compute fib(3) = 1 + 1	3	N/A	memo[3] = 2	[-1, -1, 1, 2, -1]
13	Return 2	3	N/A	None	[-1, -1, 1, 2, -1]
14	Call fib(2)	2	memo[2] = 1 (found)	None	[-1, -1, 1, 2, -1]
15	Return 1	2	N/A	None	[-1, -1, 1, 2, -1]
16	Compute fib(4) = 2 + 1	4	N/A	memo[4] = 3	[-1, -1, 1, 2, 3]
17	Return 3	4	N/A	None	[-1, -1, 1, 2, 3]

💡 fib(4) computed and memoized; recursion ends after all calls return.

Variable Tracker

Variable	Start	After Step 8	After Step 12	After Step 16	Final
memo[2]	-1	1	1	1	1
memo[3]	-1	-1	2	2	2
memo[4]	-1	-1	-1	3	3

Key Moments - 3 Insights

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

Checking memo[n] (see steps 1, 2, 14) avoids repeating work by returning stored results immediately.

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

Without storing (see step 16), future calls recompute fib(n), losing memoization benefits and increasing time.

Why do base cases return immediately without memo access?

Base cases (steps 4, 6) return known values directly; no need to store because they are simple and fixed.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of memo[3] after step 12?

A 2

B -1

C 1

D 3

💡 Hint

Check the 'Memo Update' and 'Visual Memo State' columns at step 12.

At which step does the recursion first use a memoized value instead of computing?

A Step 8

B Step 14

C Step 2

D Step 16

💡 Hint

Look for 'memo[n] = value (found)' in the 'Memo Access' column.

If memo was not used, how would the number of calls change?

A Same number of calls

B Fewer calls, faster execution

C More calls, repeated computations

D No calls at all

💡 Hint

Memoization avoids repeated calls by storing results, see how memo prevents recomputation.

Concept Snapshot

Memoization stores results of recursive calls to avoid repeated work.
Check memo before computing; if found, return stored value.
If not found, compute recursively, store result, then return.
Improves efficiency from exponential to linear in many problems.
Commonly used in Fibonacci, factorial with caching, and DP problems.

Full Transcript

Memoization optimizes recursion by saving results of function calls in a memo array. When the function is called with a value, it first checks if the result is already stored. If yes, it returns that result immediately, avoiding repeated calculations. If not, it computes the result recursively, stores it in the memo, and returns it. This process reduces the number of recursive calls drastically, making algorithms like Fibonacci efficient. The execution table shows each step of calls, memo checks, updates, and returns, illustrating how memoization prevents redundant work.

Practice

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

easy

A. To avoid using any variables inside the function

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

C. To convert recursion into iteration automatically

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

Solution

1. Step 1: Understand what memoization does

   Memoization saves the results of function calls so they don't need to be recalculated.

2. Step 2: Identify the benefit in recursion

   This reduces repeated work and speeds up recursive functions.

3. Final Answer:

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

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 variables

2. Which of the following is the correct way to declare a memoization array for Fibonacci numbers in C?

easy

A. int memo[] = {1, 1};

B. int memo = 100;

C. int memo[100] = {0};

D. int memo(100);

Solution

1. Step 1: Check valid C array declaration

   In C, arrays are declared with type, name, and size in square brackets.

2. Step 2: Identify correct syntax

   int memo[100] = {0}; uses int memo[100] = {0}; which initializes all elements to zero correctly.

3. Final Answer:

   int memo[100] = {0}; -> Option C

4. Quick Check:

   Array declaration with size and initialization = int memo[100] = {0}; [OK]

Hint: Use int array[size] = {0} to initialize memo array [OK]

Common Mistakes:

• Using parentheses instead of brackets for arrays
• Assigning a single int instead of an array
• Not initializing the array to zero

3. What will be the output of the following C code snippet using memoization for Fibonacci?

int memo[100] = {0};

int fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != 0) return memo[n];
  memo[n] = fib(n-1) + fib(n-2);
  return memo[n];
}

int main() {
  printf("%d", fib(5));
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 0

Solution

1. Step 1: Trace fib(5) with memoization

   fib(5) = fib(4) + fib(3), and so on, with memo storing results to avoid repeats.

2. Step 2: Calculate Fibonacci values

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

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

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect on output
• Mistaking base cases

4. Identify the error in this memoized factorial function in C:

int memo[100] = {0};

int fact(int n) {
  if (n == 0) return 1;
  if (memo[n] != 0) return memo[n];
  memo[n] = n * fact(n - 1);
  return memo[n];
}

int main() {
  printf("%d", fact(5));
  return 0;
}

medium

A. Memo array is not initialized to -1 to detect uncalculated values

B. Base case should return 0 instead of 1

C. Function should use iteration, not recursion

D. Memo array size is too small

Solution

1. Step 1: Understand memo check condition

   The code checks if memo[n] != 0 to decide if value is cached.

2. Step 2: Identify problem with zero initialization

   Since factorial(0) = 1, memo[1] will be 0 initially, but 0 is a valid value for uninitialized. This causes confusion.

3. Step 3: Correct approach

   Initialize memo array with -1 to mark uncalculated values, so 0 is a valid cached result.

4. Final Answer:

   Memo array is not initialized to -1 to detect uncalculated values -> Option A

5. Quick Check:

   Use -1 to mark uncalculated memo entries [OK]

Hint: Initialize memo with -1 to detect uncalculated values [OK]

Common Mistakes:

• Assuming zero means uncalculated without initialization
• Changing base case incorrectly
• Thinking recursion must be replaced by iteration

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 stores intermediate results to avoid repeated calculations?

hard

A. Use a global variable to count calls without storing results

B. Recalculate all values each time without storing

C. Use a linked list to store all previous results dynamically

D. Use an array int memo[n+1] initialized with -1, store results at memo[i] for steps i

Solution

1. Step 1: Understand problem and memoization need

   Number of ways to climb stairs is a classic recursion problem with overlapping subproblems.

2. Step 2: Choose correct memoization method

   Using an array sized n+1 initialized with -1 allows storing results for each step count to reuse.

3. Final Answer:

   Use an array int memo[n+1] initialized with -1, store results at memo[i] for steps i -> Option D

4. Quick Check:

   Array memo with -1 initialization stores intermediate results [OK]

Hint: Use array memo[n+1] with -1 to store step results [OK]

Common Mistakes:

• Not initializing memo array properly
• Using global counters without memoization
• Using complex data structures unnecessarily