Memoization to Optimize Recursion in DSA Python

Mental Model

Memoization saves answers to small problems so we don't solve them again. It makes recursion faster by remembering past results.

Analogy: Imagine you are solving a puzzle and write down each step you finish. Next time you see the same step, you just look at your notes instead of solving it again.

fib(4)
  ↓
fib(3) + fib(2)
 ↓       ↓
fib(2)+fib(1) fib(1)+fib(0)
 ↑ memo stores fib(2)=1

Dry Run Walkthrough

Input: Calculate fib(5) using recursion with memoization

Goal: Find fib(5) efficiently by storing results of smaller fib calls

Step 1: Call fib(5), no memo yet

memo = {}
fib(5) calls fib(4) and fib(3)

Why: Start breaking down problem into smaller parts

Step 2: Call fib(4), no memo for fib(4)

memo = {}
fib(4) calls fib(3) and fib(2)

Why: Need fib(4) to compute fib(5)

Step 3: Call fib(3), no memo for fib(3)

memo = {}
fib(3) calls fib(2) and fib(1)

Why: Need fib(3) to compute fib(4)

Step 4: Call fib(2), no memo for fib(2)

memo = {}
fib(2) calls fib(1) and fib(0)

Why: Need fib(2) to compute fib(3)

Step 5: fib(1) and fib(0) are base cases, return 1 and 0

memo = {}
fib(2) = 1 + 0 = 1

Why: Base cases stop recursion

Step 6: Store fib(2) = 1 in memo

memo = {2:1}
fib(3) calls fib(1) which is base case 1

Why: Remember fib(2) to avoid recomputing

Step 7: Calculate fib(3) = fib(2) + fib(1) = 1 + 1 = 2

memo = {2:1, 3:2}
fib(4) calls fib(2) again

Why: Store fib(3) result and reuse fib(2)

Step 8: fib(4) = fib(3) + fib(2) = 2 + 1 = 3, store in memo

memo = {2:1, 3:2, 4:3}
fib(5) calls fib(3) again

Why: Reuse stored results for efficiency

Step 9: fib(3) found in memo as 2, no recursion needed

memo = {2:1, 3:2, 4:3}
fib(5) = 3 + 2 = 5

Why: Memoization avoids repeated work

Result:

memo = {2:1, 3:2, 4:3}
Final fib(5) = 5

Annotated Code

DSA Python

from typing import Dict

class FibonacciMemo:
    def __init__(self):
        self.memo: Dict[int, int] = {}

    def fib(self, n: int) -> int:
        if n in self.memo:
            return self.memo[n]  # return saved result to avoid recomputation
        if n <= 1:
            return n  # base case: fib(0)=0, fib(1)=1
        # recursive calls with memoization
        result = self.fib(n - 1) + self.fib(n - 2)
        self.memo[n] = result  # save result for future calls
        return result

# Driver code
fib_calc = FibonacciMemo()
result = fib_calc.fib(5)
print(result)

if n in self.memo:

Check if result already computed to reuse it

if n <= 1:

Handle base cases to stop recursion

result = self.fib(n - 1) + self.fib(n - 2)

Compute fib recursively breaking problem into smaller parts

self.memo[n] = result

Store computed result to avoid repeated work

Output

5

Complexity Analysis

Time: O(n) because each fib number from 0 to n is computed once and stored

Space: O(n) due to memo dictionary storing results for each number up to n

vs Alternative: Without memoization, time is O(2^n) due to repeated calls; memoization reduces it to linear time

Edge Cases

n = 0 (smallest input)

Returns 0 immediately as base case

DSA Python

if n <= 1:

n = 1 (smallest non-zero input)

Returns 1 immediately as base case

DSA Python

if n <= 1:

Repeated calls with same n

Returns memoized result instantly without recursion

DSA Python

if n in self.memo:

When to Use This Pattern

When you see a recursive problem with overlapping subproblems, reach for memoization to save repeated work and speed up the solution.

Common Mistakes

Mistake: Not storing the computed result in memo after recursion
Fix: Add memo[n] = result line after computing to save the answer

Mistake: Checking memo after recursive calls instead of before
Fix: Check if n in memo at the start of the function to avoid unnecessary recursion

Summary

Memoization stores results of recursive calls to avoid repeated work.

Use it when recursion solves the same subproblems multiple times.

The key insight is to remember answers so you never solve the same problem twice.

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