Memoization to Optimize Recursion in DSA Rust - 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 recursion first checks if the answer is already saved (memo). If yes, it returns it immediately. Otherwise, it computes the answer, saves it, then returns it.

Execution Sample

DSA Rust

fn fib(n: usize, memo: &mut Vec<Option<usize>>) -> usize {
    if let Some(val) = memo[n] {
        return val;
    }
    if n <= 1 {
        return n;
    }
    let result = fib(n-1, memo) + fib(n-2, memo);
    memo[n] = Some(result);
    result
}

This code 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	[None, None, None, None, None]	[None, None, None, None, None]	-	[None, None, None, None, None]
2	Call fib(3)	3	[None, None, None, None, None]	[None, None, None, None, None]	-	[None, None, None, None, None]
3	Call fib(2)	2	[None, None, None, None, None]	[None, None, None, None, None]	-	[None, None, None, None, None]
4	Call fib(1)	1	[None, None, None, None, None]	[None, None, None, None, None]	1	[None, None, None, None, None]
5	Call fib(0)	0	[None, None, None, None, None]	[None, None, None, None, None]	0	[None, None, None, None, None]
6	Compute fib(2) = 1 + 0	2	[None, None, None, None, None]	[None, None, Some(1), None, None]	1	[None, None, Some(1), None, None]
7	Return to fib(3), call fib(1)	1	[None, None, Some(1), None, None]	[None, None, Some(1), None, None]	1	[None, None, Some(1), None, None]
8	Compute fib(3) = fib(2) + fib(1) = 1 + 1	3	[None, None, Some(1), None, None]	[None, None, Some(1), Some(2), None]	2	[None, None, Some(1), Some(2), None]
9	Return to fib(4), call fib(2)	2	[None, None, Some(1), Some(2), None]	[None, None, Some(1), Some(2), None]	1	[None, None, Some(1), Some(2), None]
10	Compute fib(4) = fib(3) + fib(2) = 2 + 1	4	[None, None, Some(1), Some(2), None]	[None, None, Some(1), Some(2), Some(3)]	3	[None, None, Some(1), Some(2), Some(3)]
11	Return fib(4) = 3	4	[None, None, Some(1), Some(2), Some(3)]	[None, None, Some(1), Some(2), Some(3)]	3	[None, None, Some(1), Some(2), Some(3)]
12	Call fib(3) again (memo hit)	3	[None, None, Some(1), Some(2), Some(3)]	[None, None, Some(1), Some(2), Some(3)]	2	[None, None, Some(1), Some(2), Some(3)]
13	End recursion	-	[None, None, Some(1), Some(2), Some(3)]	[None, None, Some(1), Some(2), Some(3)]	-	[None, None, Some(1), Some(2), Some(3)]

💡 Recursion stops when all calls return values, and memo contains computed Fibonacci numbers for 0 to 4.

Variable Tracker

Variable	Start	After Step 6	After Step 8	After Step 10	Final
n	4	2	3	4	4
memo	[None, None, None, None, None]	[None, None, Some(1), None, None]	[None, None, Some(1), Some(2), None]	[None, None, Some(1), Some(2), Some(3)]	[None, None, Some(1), Some(2), Some(3)]
Returned Value	-	1	2	3	3

Key Moments - 3 Insights

Why does the function check the memo before computing?

Because if the result is already in memo (see Step 12), it returns immediately to avoid repeating work, saving time.

What happens when n is 0 or 1?

The function returns n directly (see Steps 4 and 5), which are the base cases stopping recursion.

How does memoization change the number of recursive calls?

Memoization stores results so repeated calls (like fib(3) in Step 12) return instantly, reducing calls from exponential to linear.

Visual Quiz - 3 Questions

Look at the execution table, what is the memo state after Step 8?

A [None, None, Some(1), Some(2), None]

B [None, None, None, Some(2), None]

C [None, Some(1), Some(2), None, None]

D [Some(1), None, None, Some(2), None]

💡 Hint

Check the 'Memo After' column in Step 8 of the execution table.

At which step does the function return the value 3 for fib(4)?

A Step 9

B Step 10

C Step 11

D Step 12

💡 Hint

Look at the 'Returned Value' column for fib(4) in the execution table.

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

A Same number of calls

B More calls, repeated calculations

C Fewer calls, faster results

D No calls at all

💡 Hint

Refer to the key moment about memoization reducing repeated calls.

Concept Snapshot

Memoization stores results of recursive calls in a cache.
Before computing, check if result exists in memo.
If yes, return cached result immediately.
If no, compute recursively, save result, then return.
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 certain input, it first checks if the answer is already saved in a memo (cache). If it is, the function returns that saved answer immediately, avoiding repeated calculations. If not, it computes the answer recursively, stores it in the memo, and then returns it. This process reduces the number of recursive calls drastically, especially in problems like Fibonacci numbers where many calls overlap. The example code shows a Fibonacci function using a vector of optional values as memo. The execution table traces calls from fib(4) down to fib(0), showing how memo fills up and how repeated calls return instantly from memo. Key moments include understanding why memo is checked first, the base cases for recursion, and how memoization reduces calls. The visual quiz tests understanding of memo state changes and the effect of memoization on recursion.

Practice

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

easy

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

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

C. To avoid using recursion altogether

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 saved result is used instead of recalculating.

2. Step 2: Identify the benefit in recursion

   This avoids repeated calculations in recursive calls, making the function faster and more efficient.

3. Final Answer:

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

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 avoiding recursion
• Believing memoization always increases memory without benefit

2. Which of the following Rust code snippets correctly declares a memoization cache using a HashMap for a recursive function?

easy

A. let mut memo = Vec::new();

B. let memo = HashMap;

C. let memo: HashMap = new HashMap();

D. let mut memo: HashMap = HashMap::new();

Solution

1. Step 1: Check correct HashMap initialization syntax

   In Rust, to create a mutable HashMap, you use let mut memo: HashMap<u32, u32> = HashMap::new();.

2. Step 2: Identify incorrect options

   Vec::new() uses the wrong type. let memo = HashMap<u32, u32>; misses mut and HashMap::new(). let memo: HashMap = new HashMap(); has invalid syntax.

3. Final Answer:

   let mut memo: HashMap<u32, u32> = HashMap::new(); -> Option D

4. Quick Check:

   Correct HashMap init = let mut memo: HashMap<u32, u32> = HashMap::new(); [OK]

Hint: Use HashMap::new() with mut for memo cache [OK]

Common Mistakes:

• Forgetting to make the HashMap mutable
• Using Vec instead of HashMap for memoization
• Missing the ::new() method call

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

use std::collections::HashMap;

fn fib(n: u32, memo: &mut HashMap) -> u32 {
    if n <= 1 {
        return n;
    }
    if let Some(&val) = memo.get(&n) {
        return val;
    }
    let result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.insert(n, result);
    result
}

fn main() {
    let mut memo = HashMap::new();
    println!("{}", fib(5, &mut memo));
}

medium

A. 8

B. 5

C. 3

D. 13

Solution

1. Step 1: Understand the Fibonacci function with memoization

   The function returns the nth Fibonacci number. fib(0)=0, fib(1)=1, fib(5) = fib(4)+fib(3).

2. Step 2: Calculate fib(5)

   fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5. The memo cache stores intermediate results to avoid repeated calls.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Recall Fibonacci sequence: 0,1,1,2,3,5... [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Ignoring memoization effect on performance
• Misreading base cases as 1 instead of 0

4. Identify the bug in this Rust recursive function using memoization:

use std::collections::HashMap;

fn factorial(n: u32, memo: &mut HashMap) -> u32 {
    if n == 0 {
        return 1;
    }
    if memo.contains_key(&n) {
        return *memo[&n];
    }
    let result = n * factorial(n - 1, memo);
    memo.insert(n, result);
    result
}

fn main() {
    let mut memo = HashMap::new();
    println!("{}", factorial(5, &mut memo));
}

medium

A. Using memo[&n] causes a panic if key is missing

B. Base case should be n == 1 instead of n == 0

C. Missing mutable borrow for memo in recursive call

D. Factorial function does not use memoization

Solution

1. Step 1: Check how memo is accessed

   Using memo[&n] directly can panic if the key is missing. Better to use memo.get(&n) or unwrap safely.

2. Step 2: Verify base case and memo usage

   Base case n==0 is correct for factorial. Memo is passed mutably correctly. Memoization is used properly except for unsafe access.

3. Final Answer:

   Using memo[&n] causes a panic if key is missing -> Option A

4. Quick Check:

   Unsafe HashMap access = Using memo[&n] causes a panic if key is missing [OK]

Hint: Use memo.get() to safely access HashMap keys [OK]

Common Mistakes:

• Assuming memo[&n] never panics
• Changing correct base case unnecessarily
• Forgetting to pass memo mutably

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 Rust?

medium

A. Use a global variable to count calls without storing intermediate results

B. Use a vector without initializing it with default values

C. Use a mutable HashMap to store results keyed by stair number and check before recursive calls

D. Recompute all values each time without caching

Solution

1. Step 1: Understand the problem and memoization need

   Calculating ways to climb stairs with 1 or 2 steps is a classic recursion problem that benefits from memoization to avoid repeated calculations.

2. Step 2: Identify correct memoization method

   Using a mutable HashMap keyed by stair number to store and reuse results before recursive calls is the correct approach. Other options either do not store results or do not initialize storage properly.

3. Final Answer:

   Use a mutable HashMap to store results keyed by stair number and check before recursive calls -> Option C

4. Quick Check:

   Memoize with HashMap keyed by input = Use a mutable HashMap to store results keyed by stair number and check before recursive calls [OK]

Hint: Cache results keyed by input to avoid recomputation [OK]

Common Mistakes:

• Not storing intermediate results
• Using global counters instead of memo
• Using uninitialized vectors for memo