Memoization to Optimize Recursion in DSA Python - 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

The flow shows how recursion checks for stored results before computing, saving time by reusing answers.

Execution Sample

DSA Python

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

Calculates Fibonacci numbers using recursion with memoization to avoid repeated work.

Execution Table

Step	Operation	n	Memo Before	Memo After	Returned Value	Visual Memo State
1	Call fib(4)	4	{}	{}	?	{}
2	Check memo for 4	4	{}	{}	Not found	{}
3	Call fib(3)	3	{}	{}	?	{}
4	Check memo for 3	3	{}	{}	Not found	{}
5	Call fib(2)	2	{}	{}	?	{}
6	Check memo for 2	2	{}	{}	Not found	{}
7	Call fib(1)	1	{}	{}	1	{}
8	Return fib(1)	1	{}	{}	1	{}
9	Call fib(0)	0	{}	{}	0	{}
10	Return fib(0)	0	{}	{}	0	{}
11	Compute fib(2) = 1 + 0	2	{}	{2:1}	1	{2:1}
12	Return fib(2)	2	{2:1}	{2:1}	1	{2:1}
13	Call fib(1)	1	{2:1}	{2:1}	1	{2:1}
14	Return fib(1)	1	{2:1}	{2:1}	1	{2:1}
15	Compute fib(3) = 1 + 1	3	{2:1}	{2:1, 3:2}	2	{2:1, 3:2}
16	Return fib(3)	3	{2:1, 3:2}	{2:1, 3:2}	2	{2:1, 3:2}
17	Call fib(2)	2	{2:1, 3:2}	{2:1, 3:2}	1	{2:1, 3:2}
18	Return fib(2)	2	{2:1, 3:2}	{2:1, 3:2}	1	{2:1, 3:2}
19	Compute fib(4) = 2 + 1	4	{2:1, 3:2}	{2:1, 3:2, 4:3}	3	{2:1, 3:2, 4:3}
20	Return fib(4)	4	{2:1, 3:2, 4:3}	{2:1, 3:2, 4:3}	3	{2:1, 3:2, 4:3}

💡 fib(4) returns 3 after storing all intermediate results in memo

Variable Tracker

Variable	Start	After Step 11	After Step 15	After Step 19	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	?	1	2	3	3

Key Moments - 3 Insights

Why do we check if n is in memo before computing?

Because if the result is already stored (see Step 2 and Step 4), we avoid repeating the same calculation, saving time.

What happens when n is 1 or 0?

At these base cases (Step 7 and Step 9), the function returns n directly without recursion, stopping further calls.

How does memoization reduce the number of recursive calls?

By storing results after first computation (Step 11, 15, 19), later calls reuse these values (Step 17), skipping repeated work.

Visual Quiz - 3 Questions

Look at the execution table, what is the memo content after Step 15?

A {}

B {2:1}

C {2:1, 3:2}

D {4:3}

💡 Hint

Check the 'Memo After' column at Step 15 in the execution table.

At which step does fib(2) get computed and stored in memo for the first time?

A Step 17

B Step 11

C Step 6

D Step 19

💡 Hint

Look for the first time memo changes to include key 2 in the 'Memo After' column.

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

A More calls, repeated calculations

B Fewer calls, faster execution

C Same number of calls

D No calls at all

💡 Hint

Memoization avoids repeated calls by storing results, see how calls reduce in the table.

Concept Snapshot

Memoization stores results of recursive calls in a dictionary.
Before computing, check if result exists in memo.
If yes, return stored result to save time.
If no, compute recursively and store result.
This avoids repeated work and speeds up recursion.

Full Transcript

Memoization is a technique to optimize recursion by saving results of function calls. When the function is called with a value, it first checks if the answer is already saved in a dictionary called memo. If yes, it returns that saved answer immediately. If not, it computes the answer recursively, saves it in memo, and then returns it. This way, repeated calculations are avoided, making the recursion much faster. For example, in Fibonacci calculation, fib(2) is computed once and stored. Later calls reuse this stored value instead of recalculating fib(2) again. This reduces the total number of recursive calls and speeds up the program.

Practice

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

easy

A. To replace recursion with iteration

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

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

D. To increase the memory usage without any benefit

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 benefit of memoization

   This saves time by avoiding repeated calculations, making recursive functions faster.

3. Final Answer:

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

4. Quick Check:

   Memoization = Store and reuse results [OK]

Hint: Memoization saves repeated work by caching results [OK]

Common Mistakes:

• Thinking memoization slows down the function
• Confusing memoization with converting recursion to loops
• Believing memoization always increases memory without benefit

2. Which of the following is the correct way to define a memo dictionary inside a recursive function in Python?

easy

A. def fib(n, memo={}):

B. def fib(n, memo=None): memo = {}

C. def fib(n, memo=[]):

D. def fib(n, memo=0):

Solution

1. Step 1: Understand default mutable arguments problem

   Using a mutable default argument like a dictionary directly can cause unexpected behavior because the same dictionary is shared across calls.

2. Step 2: Use None as default and initialize inside

   Setting memo=None and then initializing memo = {} inside the function avoids this problem and is the correct pattern.

3. Final Answer:

   def fib(n, memo=None): memo = {} -> Option B

4. Quick Check:

   Use None default and initialize dict inside [OK]

Hint: Use None default and create dict inside function [OK]

Common Mistakes:

• Using mutable default arguments directly
• Using list instead of dictionary for memo
• Setting memo default to 0 which is invalid

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

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

print(fib(5))

medium

A. 8

B. None

C. 3

D. 5

Solution

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

   fib(5) = fib(4) + fib(3), fib(4) = fib(3) + fib(2), and so on. Using memoization avoids repeated calls.

2. Step 2: Calculate fib(5)

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

3. Final Answer:

   5 -> Option D

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 memo and recalculating values
• Returning None due to missing return

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

def factorial(n, memo=None):
    if memo is None:
        memo = {}
    if n == 0:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = n * factorial(n-1)
    return memo[n]

medium

A. Add memo argument in recursive call: factorial(n-1, memo)

B. Change base case to n == 1

C. Initialize memo as a list instead of dict

D. Remove memo dictionary completely

Solution

1. Step 1: Check recursive call parameters

   The recursive call factorial(n-1) misses passing memo, so memo is reset each time, losing stored results.

2. Step 2: Fix by passing memo in recursive call

   Change to factorial(n-1, memo) to keep using the same memo dictionary.

3. Final Answer:

   Add memo argument in recursive call: factorial(n-1, memo) -> Option A

4. Quick Check:

   Pass memo in recursion to keep cache [OK]

Hint: Always pass memo in recursive calls [OK]

Common Mistakes:

• Forgetting to pass memo in recursive call
• Changing base case unnecessarily
• Using list instead of dictionary for memo

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 avoids redundant calculations and handles edge cases?

hard

A. Use memo=None default, initialize inside, pass memo in recursive calls, and handle base cases for n=0 and n=1

B. Use a default mutable argument dictionary and update it inside the function

C. Do not use memoization; rely on simple recursion for clarity

D. Use a global dictionary outside the function to store results and pass n only

Solution

1. Step 1: Understand memoization best practice

   Using memo=None default and initializing inside avoids shared mutable defaults and ensures fresh memo per call.

2. Step 2: Pass memo in recursive calls and handle base cases

   Passing memo keeps cache consistent. Base cases n=0 (1 way) and n=1 (1 way) prevent infinite recursion and define correct results.

3. Final Answer:

   Use memo=None default, initialize inside, pass memo in recursion, handle base cases -> Option A

4. Quick Check:

   Proper memo init and passing + base cases = correct [OK]

Hint: Initialize memo inside and pass it in recursion [OK]

Common Mistakes:

• Using global variables causing side effects
• Using mutable default arguments directly
• Ignoring base cases causing infinite recursion