Memoization to Optimize Recursion in DSA Rust - Build from Scratch

Memoization to Optimize Recursion

📖 Scenario: Imagine you want to calculate the number of ways to climb a staircase with a certain number of steps. You can climb either 1 or 2 steps at a time. This is a classic problem where recursion can be slow because it repeats the same calculations many times.Memoization helps by remembering results of previous calculations so you don't repeat work.

🎯 Goal: You will build a Rust program that uses memoization to speed up the recursive calculation of the number of ways to climb stairs.

📋 What You'll Learn

Create a recursive function to calculate ways to climb stairs

Use a dictionary (HashMap) to store intermediate results

Add a memoization helper variable

Print the final number of ways for 10 steps

💡 Why This Matters

🌍 Real World

Memoization is used in many real-world problems like calculating Fibonacci numbers, optimizing dynamic programming solutions, and speeding up recursive algorithms in games and simulations.

💼 Career

Understanding memoization helps in writing efficient code for interviews and real projects where performance matters, especially in software engineering and data science roles.

1

Create the recursive function without memoization

Create a function called count_ways that takes a parameter n of type usize and returns a usize. The function should return 1 if n is 0 or 1. Otherwise, it should return the sum of count_ways(n - 1) and count_ways(n - 2).

DSA Rust

# Your code here

Hint

Use simple recursion with base cases for 0 and 1 steps.

2

Add a memoization HashMap to store results

Add a mutable HashMap called memo with keys and values of type usize to store previously calculated results. Initialize it as empty before calling the recursive function.

DSA Rust

fn count_ways(n: usize) -> usize {
    if n == 0 || n == 1 {
        1
    } else {
        count_ways(n - 1) + count_ways(n - 2)
    }
}

// Create a mutable HashMap called memo here
// Your code here

Hint

Use HashMap::new() to create an empty map.

3

Modify the function to use memoization

Change the count_ways function to take a mutable reference to memo: &mut HashMap. Before computing, check if n is in memo. If yes, return the stored value. Otherwise, compute the value recursively, store it in memo, and then return it.

DSA Rust

use std::collections::HashMap;

fn count_ways(n: usize, memo: &mut HashMap) -> usize {
    // Your code here
}

fn main() {
    let mut memo: HashMap = HashMap::new();
}

Hint

Use memo.get(&n) to check for cached results and memo.insert(n, result) to save new results.

4

Call the memoized function and print the result

In main, call count_ways(10, &mut memo) and print the result using println!.

DSA Rust

use std::collections::HashMap;

fn count_ways(n: usize, memo: &mut HashMap) -> usize {
    if n == 0 || n == 1 {
        1
    } else if let Some(&result) = memo.get(&n) {
        result
    } else {
        let result = count_ways(n - 1, memo) + count_ways(n - 2, memo);
        memo.insert(n, result);
        result
    }
}

fn main() {
    let mut memo: HashMap = HashMap::new();
    // Your code here
}

Hint

Call count_ways(10, &mut memo) and print the result.

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