Why Dynamic Programming and When Recursion Alone Fails in DSA Rust - Quick Recap

Recall & Review

beginner

What is the main problem with using plain recursion for some problems?

Plain recursion can lead to repeated calculations of the same subproblems, causing exponential time complexity and slow performance.

beginner

What does Dynamic Programming (DP) do to improve recursion?

DP stores the results of subproblems so they don't need to be recalculated, turning exponential time into polynomial time.

intermediate

What are the two main approaches to implement Dynamic Programming?

Top-down (memoization) which uses recursion with caching, and bottom-up (tabulation) which builds solutions from smaller subproblems up.

beginner

Why does recursion alone fail for problems like Fibonacci sequence calculation?

Because it recalculates the same Fibonacci numbers many times, leading to exponential growth in calls and slow execution.

beginner

How does memoization help recursion?

Memoization saves the results of recursive calls in a cache so that when the same inputs occur again, the stored result is used instead of recalculating.

What is the main benefit of using Dynamic Programming over plain recursion?

A Makes code shorter but slower

B Uses more memory without performance gain

C Removes the need for recursion

D Avoids repeated calculations by storing results

Dynamic Programming stores results of subproblems to avoid repeated calculations, improving performance.

Which problem is a classic example where recursion alone is inefficient?

A Printing numbers from 1 to n

B Sorting an array

C Calculating Fibonacci numbers

D Finding maximum in a list

Calculating Fibonacci numbers with plain recursion recalculates the same values many times, causing inefficiency.

What is memoization in Dynamic Programming?

A Storing results of subproblems to reuse

B Breaking problems into smaller parts

C Using loops instead of recursion

D Ignoring repeated subproblems

Memoization caches results of subproblems to avoid repeated work.

Which approach builds solutions from the smallest subproblems up?

A Top-down (memoization)

B Bottom-up (tabulation)

C Plain recursion

D Divide and conquer

Bottom-up DP solves smaller subproblems first and uses their results to solve bigger ones.

When does recursion alone typically fail?

A When subproblems overlap and are recalculated multiple times

B When problems have no subproblems

C When problems are very small

D When no results need to be stored

Recursion fails when it recalculates overlapping subproblems repeatedly, causing inefficiency.

Explain why recursion alone can be inefficient and how Dynamic Programming solves this problem.

Think about how many times the same calculation happens in recursion.

Describe the difference between top-down and bottom-up Dynamic Programming approaches.

One builds from the top problem down, the other from the bottom up.

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