Memoization to Optimize Recursion in DSA Javascript - 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, and returns it.

Execution Sample

DSA Javascript

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fib(n-1, memo) + fib(n-2, memo);
  return memo[n];
}
console.log(fib(5));

Calculates Fibonacci number for 5 using recursion with memoization to store intermediate results.

Execution Table

Step	Operation	n	Memo Content	Action	Returned Value
1	Call fib(5)	5	{}	Check memo: no	Pending
2	Call fib(4)	4	{}	Check memo: no	Pending
3	Call fib(3)	3	{}	Check memo: no	Pending
4	Call fib(2)	2	{}	Check memo: no	Pending
5	Call fib(1)	1	{}	n <= 1, return 1	1
6	Call fib(0)	0	{}	n <= 1, return 0	0
7	Compute fib(2)	2	{}	memo[2] = 1 + 0	1
8	Return fib(2)	2	{2:1}	Return memo[2]	1
9	Call fib(1)	1	{2:1}	n <= 1, return 1	1
10	Compute fib(3)	3	{2:1}	memo[3] = 1 + 1	2
11	Return fib(3)	3	{2:1,3:2}	Return memo[3]	2
12	Call fib(2)	2	{2:1,3:2}	Found in memo, return 1	1
13	Compute fib(4)	4	{2:1,3:2}	memo[4] = 2 + 1	3
14	Return fib(4)	4	{2:1,3:2,4:3}	Return memo[4]	3
15	Call fib(3)	3	{2:1,3:2,4:3}	Found in memo, return 2	2
16	Compute fib(5)	5	{2:1,3:2,4:3}	memo[5] = 3 + 2	5
17	Return fib(5)	5	{2:1,3:2,4:3,5:5}	Return memo[5]	5

💡 fib(5) returns 5 after all recursive calls use memo to avoid repeated work

Variable Tracker

Variable	Start	After Step 7	After Step 10	After Step 13	After Step 16	Final
n	5	2	3	4	5	5
memo	{}	{2:1}	{2:1,3:2}	{2:1,3:2,4:3}	{2:1,3:2,4:3,5:5}	{2:1,3:2,4:3,5:5}

Key Moments - 3 Insights

Why does the function check if memo[n] exists before computing?

Because checking memo[n] (see steps 12 and 15) avoids repeating the same recursive calls, saving time by returning stored results immediately.

What happens when n is 1 or 0?

At steps 5 and 6, the function returns n directly without recursion, which are the base cases stopping further calls.

How does memoization change the number of recursive calls?

Memoization reduces calls by storing results (see memo growing in steps 7, 10, 13, 16), so repeated calls like fib(2) and fib(3) return instantly from memo.

Visual Quiz - 3 Questions

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

A {"2":1,"3":2}

B {"2":1}

C {}

D {"2":1,"3":2,"4":3}

💡 Hint

Check the 'Memo Content' column at step 10 in the execution_table.

At which step does the function first return a value without further recursion?

A Step 12

B Step 7

C Step 5

D Step 16

💡 Hint

Look for the first step where 'Returned Value' is a number and no 'Pending' status.

If memoization was removed, how would the number of calls change?

A Fewer calls, faster execution

B More calls, repeated calculations

C Same number of calls

D No calls at all

💡 Hint

Memoization stores results to avoid repeated calls, so without it calls increase.

Concept Snapshot

Memoization stores results of recursive calls in a cache (object) to avoid repeated work.
Check cache before computing; if found, return cached result.
If not found, compute recursively, store result, then return.
Greatly improves performance for overlapping subproblems like Fibonacci.
Syntax: function f(n, memo={}) { if(memo[n] !== undefined) return memo[n]; ... }

Full Transcript

Memoization optimizes recursion by saving results of function calls in a memo object. 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 technique is especially useful for problems like Fibonacci numbers where many calls overlap. The execution table shows each call, the state of the memo, and when results are returned. Key moments include understanding base cases, why memo checks happen, and how memoization reduces calls. The visual quiz tests understanding of memo content and call returns. The snapshot summarizes the memoization pattern and its benefits.

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 store results of expensive function calls and reuse them later

C. To avoid using recursion altogether

D. To increase the number of recursive calls

Solution

1. Step 1: Understand what memoization does

   Memoization saves the results of function calls so that if the same inputs occur again, the saved result is used instead of recalculating.

2. Step 2: Identify the effect on recursion

   This reduces repeated work and speeds up recursive functions by avoiding duplicate calculations.

3. Final Answer:

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

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated work to speed recursion [OK]

Common Mistakes:

• Thinking memoization makes recursion slower
• Confusing memoization with iteration
• Believing memoization removes recursion

2. Which of the following is the correct way to declare a memo object inside a recursive function in JavaScript?

easy

A. const memo = {}; inside the function, then pass it as a parameter

B. var memo = []; inside the function without passing it

C. let memo = 0; inside the function

D. memo = new Map(); outside the function and never pass it

Solution

1. Step 1: Understand memo object usage

   The memo object should be an object or map to store key-value pairs of inputs and results.

2. Step 2: Correct placement and passing

   Declaring const memo = {} inside the function and passing it as a parameter ensures the same memo is used across recursive calls.

3. Final Answer:

   const memo = {}; inside the function, then pass it as a parameter -> Option A

4. Quick Check:

   Memo object declared and passed = const memo = {}; inside the function, then pass it as a parameter [OK]

Hint: Declare memo as object and pass it to recursive calls [OK]

Common Mistakes:

• Using array instead of object for memo
• Not passing memo to recursive calls
• Declaring memo as a number

3. What will be the output of the following code?

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
console.log(fib(5));

medium

A. 5

B. 8

C. 3

D. Undefined

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) step-by-step

   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 Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memo and recalculating
• Assuming output is 8

4. Identify the error in this memoized factorial function and choose the fix:

function factorial(n, memo = {}) {
  if (n === 0) return 1;
  if (memo[n]) return memo[n];
  memo[n] = n * factorial(n - 1);
  return memo[n];
}

medium

A. Remove memo object completely

B. Change base case to n === 1

C. Pass memo in recursive call: factorial(n - 1, memo)

D. Initialize memo as an array instead of object

Solution

1. Step 1: Check recursive call parameters

   The recursive call to factorial misses passing the memo object, so memo is reset each time.

2. Step 2: Fix by passing memo in recursion

   Change call to factorial(n - 1, memo) to keep memo consistent across calls.

3. Final Answer:

   Pass memo in recursive call: factorial(n - 1, memo) -> Option C

4. Quick Check:

   Pass memo to recursive calls to fix [OK]

Hint: Always pass memo object in recursive calls [OK]

Common Mistakes:

• Forgetting to pass memo in recursion
• Changing base case unnecessarily
• Removing memo defeats optimization

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 improves performance?

hard

A. Store results only for even stair numbers in memo

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

C. Rewrite the function to use a loop without memoization

D. Use a memo object passed through recursive calls to store results for each stair number

Solution

1. Step 1: Understand the problem and recursion

   The function counts ways to climb stairs by summing ways(n-1) and ways(n-2).

2. Step 2: Apply memoization correctly

   Passing a memo object through recursive calls stores results for each stair number, avoiding repeated calculations.

3. Step 3: Evaluate other options

   Global counters don't store results, loops change approach, and storing only even results misses odd cases.

4. Final Answer:

   Use a memo object passed through recursive calls to store results for each stair number -> Option D

5. Quick Check:

   Memo object for all inputs optimizes recursion [OK]

Hint: Memoize all inputs to avoid repeated stair count calculations [OK]

Common Mistakes:

• Not passing memo object through recursion
• Partial memoization missing some inputs
• Confusing memoization with iteration