Memoization to Optimize Recursion in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is memoization in the context of recursion?

Memoization is a technique to store the results of expensive function calls and reuse them when the same inputs occur again, avoiding repeated calculations.

beginner

How does memoization improve recursive function performance?

By saving the results of recursive calls, memoization prevents the function from recalculating the same values multiple times, reducing time complexity from exponential to linear in many cases.

intermediate

In Rust, which data structure is commonly used to implement memoization for recursion?

A HashMap is commonly used in Rust to store input-output pairs for memoization, allowing quick lookup of previously computed results.

intermediate

What is the main difference between memoization and tabulation?

Memoization is a top-down approach that caches results during recursion, while tabulation is a bottom-up approach that builds a table iteratively without recursion.

beginner

Why is memoization especially useful for problems like Fibonacci sequence calculation?

Because naive recursion recalculates the same Fibonacci numbers many times, memoization stores these results once computed, drastically reducing redundant work and speeding up the process.

What does memoization store to optimize recursion?

A Input parameters only

B Previously computed results

C Function call stack

D Random values

Memoization stores previously computed results to avoid recalculating them.

Which Rust data structure is best suited for memoization?

A HashMap

B Vec

C LinkedList

D BinaryHeap

HashMap allows fast lookup of stored results by keys, ideal for memoization.

Memoization changes the time complexity of naive Fibonacci recursion from:

A O(n) to O(1)

B O(n^2) to O(n log n)

C O(n!) to O(n^2)

D O(2^n) to O(n)

Memoization reduces exponential time O(2^n) to linear time O(n) for Fibonacci.

Memoization is an example of which programming technique?

A Greedy algorithm

B Divide and conquer

C Dynamic programming

D Backtracking

Memoization is a dynamic programming technique that caches results to optimize recursion.

Which approach is top-down and uses recursion with caching?

A Memoization

B Tabulation

C Iteration

D Brute force

Memoization is a top-down approach that uses recursion and caches results.

Explain how memoization optimizes a recursive function using a Rust HashMap.

Think about saving and reusing answers to avoid repeated work.

Describe the difference between memoization and tabulation in dynamic programming.

Consider how each method approaches problem solving.

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