Memoization to Optimize Recursion in DSA Rust

Mental Model

Memoization remembers answers to small problems so we don't solve them again. It saves time by storing results and reusing them.

Analogy: Imagine you are solving a big puzzle by breaking it into smaller pieces. If you already solved a piece before, you keep it in a box and reuse it instead of solving it again.

fib(5)
  ↓
fib(4) + fib(3)
  ↓       ↓
fib(3)+fib(2) fib(2)+fib(1)
  ↓       ↓       ↓       ↓
...     ...     ...     ...
[cache] stores answers like fib(2)=1, fib(3)=2

Dry Run Walkthrough

Input: Calculate fib(5) using recursion with memoization

Goal: Compute fib(5) efficiently by storing intermediate results to avoid repeated work

Step 1: Call fib(5), check cache (empty), compute fib(4) and fib(3)

cache: {}
fib(5) -> fib(4) + fib(3)

Why: We start with fib(5) and need fib(4) and fib(3) to compute it

Step 2: Call fib(4), check cache (empty), compute fib(3) and fib(2)

cache: {}
fib(4) -> fib(3) + fib(2)

Why: fib(4) depends on fib(3) and fib(2), so we compute those next

Step 3: Call fib(3), check cache (empty), compute fib(2) and fib(1)

cache: {}
fib(3) -> fib(2) + fib(1)

Why: fib(3) depends on fib(2) and fib(1), so we compute those

Step 4: Call fib(2), base case returns 1, store fib(2)=1 in cache

cache: {2:1}
fib(2) = 1

Why: fib(2) is a base case, so we return 1 and save it

Step 5: Call fib(1), base case returns 1, store fib(1)=1 in cache

cache: {2:1, 1:1}
fib(1) = 1

Why: fib(1) is a base case, so we return 1 and save it

Step 6: Compute fib(3) = fib(2) + fib(1) = 1 + 1 = 2, store fib(3)=2

cache: {2:1, 1:1, 3:2}
fib(3) = 2

Why: We combine cached results to get fib(3) and save it

Step 7: Call fib(2), found in cache as 1, reuse it

cache: {2:1, 1:1, 3:2}
fib(2) = 1 (from cache)

Why: No need to compute fib(2) again, reuse cached value

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

cache: {2:1, 1:1, 3:2, 4:3}
fib(4) = 3

Why: Combine cached fib(3) and fib(2) to get fib(4) and save it

Step 9: Call fib(3), found in cache as 2, reuse it

cache: {2:1, 1:1, 3:2, 4:3}
fib(3) = 2 (from cache)

Why: Reuse cached fib(3) to avoid recomputation

Step 10: Compute fib(5) = fib(4) + fib(3) = 3 + 2 = 5, store fib(5)=5

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

Why: Combine cached fib(4) and fib(3) to get final answer fib(5)

Result:

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

Annotated Code

DSA Rust

use std::collections::HashMap;

fn fib_memo(n: u32, cache: &mut HashMap<u32, u32>) -> u32 {
    if n <= 2 {
        return 1; // base case: fib(1) and fib(2) = 1
    }
    if let Some(&val) = cache.get(&n) {
        return val; // reuse cached result
    }
    // compute fib(n-1) and fib(n-2) recursively
    let val = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);
    cache.insert(n, val); // store result in cache
    val
}

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

if n <= 2 { return 1; // base case: fib(1) and fib(2) = 1 }

return base case value for fib(1) and fib(2)

if let Some(&val) = cache.get(&n) { return val; // reuse cached result }

check if fib(n) is already computed and reuse it

let val = fib_memo(n - 1, cache) + fib_memo(n - 2, cache);

recursively compute fib(n-1) and fib(n-2)

cache.insert(n, val); // store result in cache

save computed fib(n) to cache for future reuse

Output

fib(5) = 5

Complexity Analysis

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

Space: O(n) for the cache storing results of fib(1) to fib(n) and recursion stack

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

Edge Cases

n = 1 or n = 2 (base cases)

Returns 1 immediately without recursion

DSA Rust

if n <= 2 {
        return 1; // base case: fib(1) and fib(2) = 1
    }

Repeated calls for same n

Uses cached value to avoid recomputation

DSA Rust

if let Some(&val) = cache.get(&n) {
        return val; // reuse cached result
    }

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 computed results in cache, causing repeated expensive calls
Fix: Insert the computed value into cache before returning it

Mistake: Not checking cache before recursive calls, missing reuse opportunity
Fix: Always check cache first and return cached value if present

Summary

Memoization stores results of recursive calls to avoid repeated work.

Use it when recursion solves the same subproblems multiple times.

Remember: save answers and check before computing again.

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