Memoization to Optimize Recursion in DSA Typescript - Execution Trace

Concept Flow - Memoization to Optimize Recursion

Start Recursive Call

↓

Check if result in cache?

Yes→Return cached result

No↓

Compute result recursively

↓

Store result in cache

↓

Return result

↓

End Recursive Call

The flow shows how recursion checks a cache before computing, stores results to avoid repeated work, and returns cached results when available.

Execution Sample

DSA Typescript

function fib(n: number, memo: Record<number, number> = {}): number {
  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];
}

Calculates Fibonacci numbers using recursion with memoization to save and reuse results.

Execution Table

Step	Operation	Current n	Cache Before	Cache After	Returned Value	Visual State
1	Call fib(4)	4	{}	{}	pending	fib(4) called, cache empty
2	Call fib(3)	3	{}	{}	pending	fib(3) called inside fib(4)
3	Call fib(2)	2	{}	{}	pending	fib(2) called inside fib(3)
4	Call fib(1)	1	{}	{}	1	fib(1) base case returns 1
5	Call fib(0)	0	{}	{}	0	fib(0) base case returns 0
6	Compute fib(2)	2	{}	{"2": 1}	1	fib(2) = 1 + 0 = 1 stored in cache
7	Call fib(1)	1	{"2":1}	{"2":1}	1	fib(1) base case returns 1
8	Compute fib(3)	3	{"2":1}	{"2":1,"3":2}	2	fib(3) = 1 + 1 = 2 stored in cache
9	Call fib(2)	2	{"2":1,"3":2}	{"2":1,"3":2}	1	fib(2) result found in cache
10	Compute fib(4)	4	{"2":1,"3":2}	{"2":1,"3":2,"4":3}	3	fib(4) = 2 + 1 = 3 stored in cache
11	Return fib(4)	4	{"2":1,"3":2,"4":3}	{"2":1,"3":2,"4":3}	3	Final result returned

💡 All recursive calls resolved, final fib(4) value computed and cached.

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 10	Final
n	4	2	3	4	4
memo	{}	{"2":1}	{"2":1,"3":2}	{"2":1,"3":2,"4":3}	{"2":1,"3":2,"4":3}
Returned Value	pending	1	2	3	3

Key Moments - 3 Insights

Why does the function check the cache before computing?

Because as shown in steps 9 and 10, the function returns cached results immediately to avoid repeating calculations, speeding up execution.

What happens when the base case is reached?

At steps 4 and 5, the function returns the base values (0 or 1) without recursion, stopping further calls and starting to build results back up.

How does memoization reduce the number of recursive calls?

By storing results in the cache (memo), repeated calls like fib(2) at step 9 return instantly from cache instead of recalculating, reducing total calls.

Visual Quiz - 3 Questions

Look at the execution table, what is the cache content after step 8?

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

B {"2":1}

C {"3":2}

D {}

💡 Hint

Check the 'Cache After' column at step 8 in the execution table.

At which step does fib(2) return a cached value instead of computing?

A Step 4

B Step 6

C Step 9

D Step 10

💡 Hint

Look for when fib(2) is called and cache already has its value.

If memoization was removed, what would happen to the number of calls?

A Calls would stay the same

B Calls would increase due to repeated calculations

C Calls would decrease

D Calls would stop immediately

💡 Hint

Refer to how memoization avoids repeated calls in the execution table.

Concept Snapshot

Memoization stores results of recursive calls in a cache.
Before computing, it checks if result exists to avoid repeated work.
This optimizes recursion by reducing calls and speeding up execution.
Use a dictionary or object to save and retrieve results.
Base cases return directly without caching.
Memoization is key for efficient recursive algorithms.

Full Transcript

This visualization shows how memoization optimizes recursion by storing results in a cache object. When the recursive function fib is called with a number n, it first checks if the result is already in the cache. If yes, it returns that cached value immediately, avoiding repeated calculations. If not, it computes the value recursively, stores it in the cache, and then returns it. Base cases for fib(0) and fib(1) return immediately without recursion. The execution table tracks each step, showing calls, cache state before and after, and returned values. The variable tracker shows how the cache (memo) grows and how returned values build up. Key moments clarify why caching is checked first, how base cases stop recursion, and how memoization reduces calls. The quiz tests understanding of cache contents, when cached values are used, and the effect of removing memoization. The snapshot summarizes memoization as a technique to speed up recursion by saving and reusing results.

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 make the function run slower by adding extra steps

C. To convert recursion into iteration automatically

D. To store results of expensive function calls and reuse them later

Solution

1. Step 1: Understand recursion inefficiency

   Recursive functions often repeat the same calculations multiple times, which wastes time.

2. Step 2: Role of memoization

   Memoization saves the results of these repeated calculations in a storage (like an object) so they can be reused without recalculating.

3. Final Answer:

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

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated results to speed up recursion [OK]

Common Mistakes:

• Thinking memoization slows down the function
• Confusing memoization with iteration
• Believing memoization removes recursion

2. Which of the following is the correct way to declare a memo object in TypeScript for memoization?

easy

A. let memo = []

B. const memo: Record = {}

C. var memo = 0

D. const memo: string = ''

Solution

1. Step 1: Identify memo storage type

   Memoization requires a storage that maps input (number) to output (number), so an object with number keys and number values is suitable.

2. Step 2: Check TypeScript syntax

   Record correctly types an object with number keys and number values.

3. Final Answer:

   const memo: Record = {} -> Option B

4. Quick Check:

   Memo object type = Record [OK]

Hint: Use Record for memo object in TypeScript [OK]

Common Mistakes:

• Using array instead of object for memo
• Declaring memo as a number or string
• Not initializing memo as an empty object

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

function fib(n: number, memo: Record = {}): number {
  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. 13

Solution

1. Step 1: Understand Fibonacci sequence

   Fibonacci numbers start as 0,1,1,2,3,5,8,... The 5th Fibonacci number (0-based) is 5.

2. Step 2: Trace fib(5) call

   fib(5) = fib(4) + fib(3) = 3 + 2 = 5, memoization avoids repeated calls.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember Fibonacci sequence values for small n [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Ignoring memoization effect on output
• Calculating fib(5) as fib(6)

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

function factorial(n: number, memo: Record = {}): number {
  if (n === 0) return 1;
  if (memo[n]) return memo[n];
  memo[n] = n * factorial(n - 1, memo);
  return memo[n];
}
console.log(factorial(5));

medium

A. Remove memo parameter from function

B. Add base case for n === 1

C. Change if (memo[n]) to if (memo[n] !== undefined)

D. Initialize memo as an array instead of object

Solution

1. Step 1: Understand memo check issue

   Checking if (memo[n]) fails when memo[n] is 0 or falsy, but factorial values are always positive, so 0 is not possible here, but better to check for undefined explicitly.

2. Step 2: Fix condition to check existence properly

   Use if (memo[n] !== undefined) to correctly detect cached values.

3. Final Answer:

   Change if (memo[n]) to if (memo[n] !== undefined) -> Option C

4. Quick Check:

   Check memo existence with !== undefined [OK]

Hint: Check memo keys with !== undefined to avoid false negatives [OK]

Common Mistakes:

• Using if(memo[n]) which fails for falsy cached values
• Adding unnecessary base case for n=1
• Removing memo parameter breaks memoization

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 implements this in TypeScript?

hard

A. function climb(n: number, memo: Record = {}): number {
if (n <= 1) return 1;
if (memo[n] !== undefined) return memo[n];
memo[n] = climb(n - 1, memo) + climb(n - 2, memo);
return memo[n];
}

B. function climb(n: number): number {
if (n <= 1) return 1;
return climb(n - 1) + climb(n - 2);
}

C. function climb(n: number, memo: number[] = []): number {
if (n <= 1) return 1;
if (memo[n]) return memo[n];
memo[n] = climb(n - 1, memo) * climb(n - 2, memo);
return memo[n];
}

D. function climb(n: number, memo: Record = {}): number {
if (n === 0) return 0;
if (memo[n]) return memo[n];
memo[n] = climb(n - 1, memo) + climb(n - 2, memo);
return memo[n];
}

Solution

1. Step 1: Understand problem base cases

   Number of ways to climb 0 or 1 stairs is 1 (one way: stand still or one step).

2. Step 2: Check memoization and recursion logic

   function climb(n: number, memo: Record = {}): number { if (n <= 1) return 1; if (memo[n] !== undefined) return memo[n]; memo[n] = climb(n - 1, memo) + climb(n - 2, memo); return memo[n]; } correctly uses memo object, checks with !== undefined, and sums ways from n-1 and n-2 stairs.

3. Step 3: Identify errors in other options

   function climb(n: number): number { if (n <= 1) return 1; return climb(n - 1) + climb(n - 2); } lacks memoization, function climb(n: number, memo: number[] = []): number { if (n <= 1) return 1; if (memo[n]) return memo[n]; memo[n] = climb(n - 1, memo) * climb(n - 2, memo); return memo[n]; } multiplies instead of sums, function climb(n: number, memo: Record = {}): number { if (n === 0) return 0; if (memo[n]) return memo[n]; memo[n] = climb(n - 1, memo) + climb(n - 2, memo); return memo[n]; } returns 0 for n=0 which is incorrect.

4. Final Answer:

   Option A code correctly implements memoized climb function -> Option A

5. Quick Check:

   Memo + sum of previous two = correct climb ways [OK]

Hint: Sum ways for n-1 and n-2 with memo check !== undefined [OK]

Common Mistakes:

• Forgetting memoization causing slow recursion
• Multiplying instead of adding ways
• Wrong base case for n=0