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.