Why Dynamic Programming and When Recursion Alone Fails in DSA Rust - See It Work

Why Dynamic Programming and When Recursion Alone Fails

📖 Scenario: Imagine you want to find the number of ways to climb a staircase with 5 steps. You can climb either 1 step or 2 steps at a time. This is a common problem where recursion alone can be slow because it repeats the same calculations many times.

🎯 Goal: You will build a simple program to count the ways to climb the stairs using recursion first, then add a helper to remember past results (dynamic programming) to make it faster.

📋 What You'll Learn

Create a recursive function to count ways to climb stairs

Add a cache (memory) to store results of subproblems

Use the cache to avoid repeated calculations

Print the final number of ways to climb 5 steps

💡 Why This Matters

🌍 Real World

Counting ways to do tasks with overlapping steps, like climbing stairs or making change, is common in real life.

💼 Career

Understanding dynamic programming helps solve optimization problems efficiently in software development and technical interviews.

1

Create a recursive function to count ways to climb stairs

Create a function called count_ways that takes an integer n and returns the number of ways to climb n steps. Use recursion with these rules: if n is 0 or 1, return 1; otherwise, return count_ways(n - 1) + count_ways(n - 2).

DSA Rust

# Define the recursive function count_ways
// Your code here

Hint

Think about the base cases first: when there are 0 or 1 steps, there is only 1 way to climb. For more steps, add the ways to climb the previous step and two steps before.

2

Add a cache to store results of subproblems

Create a mutable Vec<Option<usize>> called cache with size n + 1 filled with None. This will store results for each step count to avoid repeated calculations.

DSA Rust

fn count_ways(n: usize) -> usize {
    // Your code here
}

// Create a cache vector with size n + 1 filled with None
// Your code here

Hint

Use a vector of Option<usize> to store results. Check if the value is already computed before calculating.

3

Use the cache in the recursive function to avoid repeated calculations

Modify the count_ways function to take a mutable reference to cache and use it to return cached results if available. Calculate and store the result in cache[n] if not cached.

DSA Rust

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

fn main() {
    let n = 5;
    let mut cache = vec![None; n + 1];
    // Your code here
}

Hint

Pass the cache as a mutable reference to the function and store results after computing them.

4

Print the final number of ways to climb 5 steps

Add a println! statement to print the value of ways with the message: "Number of ways to climb 5 steps: {ways}".

DSA Rust

fn count_ways(n: usize, cache: &mut Vec>) -> usize {
    if let Some(value) = cache[n] {
        return value;
    }
    if n == 0 || n == 1 {
        cache[n] = Some(1);
        return 1;
    }
    let result = count_ways(n - 1, cache) + count_ways(n - 2, cache);
    cache[n] = Some(result);
    result
}

fn main() {
    let n = 5;
    let mut cache = vec![None; n + 1];
    let ways = count_ways(n, &mut cache);
    // Your code here
}

Hint

Use println!("Number of ways to climb 5 steps: {}", ways); to show the result.

Practice

1. Why do we use dynamic programming instead of plain recursion for some problems?

easy

A. Because recursion alone can repeat the same calculations many times, making it slow.

B. Because recursion cannot solve problems with multiple steps.

C. Because dynamic programming uses loops instead of functions.

D. Because recursion always causes errors in programs.

Solution

1. Step 1: Understand recursion's limitation

   Recursion solves problems by calling itself but can repeat the same work many times.

2. Step 2: How dynamic programming helps

   Dynamic programming saves results of subproblems to avoid repeating calculations, making it faster.

3. Final Answer:

   Because recursion alone can repeat the same calculations many times, making it slow. -> Option A

4. Quick Check:

   Recursion repeats work, DP saves results [OK]

Hint: Recursion repeats work; DP remembers results to save time [OK]

Common Mistakes:

• Thinking recursion cannot solve multi-step problems
• Believing DP replaces recursion with loops only
• Assuming recursion always causes errors

2. Which of the following Rust function signatures correctly shows a recursive function for Fibonacci numbers?

easy

A. fn fib(n: u32) -> u32 { loop { n = n + 1; } }

B. fn fib(n: u32) -> u32 { if n <= 1 { n } else { fib(n-1) + fib(n-2) } }

C. fn fib(n: u32) -> u32 { return n * n; }

D. fn fib(n: u32) -> u32 { let mut sum = 0; for i in 0..n { sum += i; } sum }

Solution

1. Step 1: Identify recursive call pattern

   fn fib(n: u32) -> u32 { if n <= 1 { n } else { fib(n-1) + fib(n-2) } } calls fib(n-1) and fib(n-2) inside the function, which is classic recursion for Fibonacci.

2. Step 2: Check other options for recursion

   Options A, C, and D do not call fib recursively; they use loops or simple calculations.

3. Final Answer:

   fn fib(n: u32) -> u32 { if n <= 1 { n } else { fib(n-1) + fib(n-2) } } -> Option B

4. Quick Check:

   Recursive calls in function = fn fib(n: u32) -> u32 { if n <= 1 { n } else { fib(n-1) + fib(n-2) } } [OK]

Hint: Look for function calling itself inside its body [OK]

Common Mistakes:

• Choosing loop-based or arithmetic-only functions
• Missing the recursive calls in the function body
• Confusing loops with recursion

3. What is the output of this Rust code using recursion to calculate Fibonacci of 4?

fn fib(n: u32) -> u32 {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

fn main() {
    println!("{}", fib(4));
}

medium

A. 4

B. 5

C. 3

D. 7

Solution

1. Step 1: Calculate fib(4) using recursion

   fib(4) = fib(3) + fib(2) - fib(3) = fib(2) + fib(1) = (fib(1) + fib(0)) + 1 = (1 + 0) + 1 = 2 - fib(2) = fib(1) + fib(0) = 1 + 0 = 1 So fib(4) = 2 + 1 = 3

2. Step 2: Confirm output printed

   The println! macro prints the result of fib(4), which is 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Break fib(n) into fib(n-1)+fib(n-2) stepwise [OK]

Common Mistakes:

• Adding fib(3) and fib(2) incorrectly
• Confusing fib(4) with fib(5)
• Forgetting base cases fib(0)=0, fib(1)=1

4. This Rust recursive function to calculate Fibonacci is very slow for large inputs. What is the main problem?

fn fib(n: u32) -> u32 {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
}

medium

A. It does not have a base case to stop recursion.

B. It uses too much memory because it stores all results in a vector.

C. It uses a loop instead of recursion.

D. It repeats the same calculations many times without saving results.

Solution

1. Step 1: Analyze recursion behavior

   The function calls fib(n-1) and fib(n-2) repeatedly without saving results, causing repeated work.

2. Step 2: Identify why it is slow

   Repeated calculations cause exponential time complexity, making it slow for large n.

3. Final Answer:

   It repeats the same calculations many times without saving results. -> Option D

4. Quick Check:

   Repeated work slows recursion without memoization [OK]

Hint: Check if function saves sub-results to avoid repeats [OK]

Common Mistakes:

• Thinking it uses too much memory storing results
• Believing it uses loops instead of recursion
• Missing the base case presence

5. You want to optimize this recursive Fibonacci function using dynamic programming in Rust. Which approach correctly applies memoization?

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

fn main() {
    let n = 5;
    let mut memo = vec![None; n+1];
    println!("{}", fib(n, &mut memo));
}

hard

A. This code uses a vector to save results and avoids repeated calculations, applying memoization correctly.

B. This code uses a loop instead of recursion, so it is not memoization.

C. This code does not save any results, so it is plain recursion.

D. This code will cause a runtime error because memo is not mutable.

Solution

1. Step 1: Check memo vector usage

   The function uses a mutable vector memo to store results of fib(n) once calculated.

2. Step 2: Confirm memoization logic

   Before calculating fib(n), it checks if memo[n] has a value to reuse, avoiding repeated work.

3. Final Answer:

   This code uses a vector to save results and avoids repeated calculations, applying memoization correctly. -> Option A

4. Quick Check:

   Memo vector stores results to speed recursion [OK]

Hint: Memo vector with Option stores and reuses results [OK]

Common Mistakes:

• Confusing memoization with loops
• Forgetting to pass mutable reference to memo
• Assuming no results are saved