DP vs Recursion vs Greedy Choosing the Right Tool in DSA Rust - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci Function

What is the output of this Rust code that calculates the 5th Fibonacci number using recursion?

DSA Rust

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

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

A 8

B 13

C 5

D 3

💡 Hint

Remember the Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8...

The recursive fib(5) returns 5, following the sequence: fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of this Rust code that uses a greedy approach to find minimum coins for amount 27 with coins [10, 5, 2, 1]?

DSA Rust

fn min_coins_greedy(mut amount: u32, coins: &[u32]) -> u32 {
    let mut count = 0;
    for &coin in coins {
        count += amount / coin;
        amount %= coin;
    }
    count
}

fn main() {
    let coins = [10, 5, 2, 1];
    println!("{}", min_coins_greedy(27, &coins));
}

A 4

B 6

C 5

D 7

💡 Hint

Count how many coins of each type fit into 27 starting from the largest coin.

Greedy picks 2 coins of 10 (20), then 1 coin of 5 (5), then 1 coin of 2 (2), total 4 coins.

❓ Predict Output

advanced

Output of DP Fibonacci Memoization

What is the output of this Rust code that calculates the 7th Fibonacci number using dynamic programming with memoization?

DSA Rust

fn fib_dp(n: usize, memo: &mut Vec<u32>) -> u32 {
    if n <= 1 {
        return n as u32;
    }
    if memo[n] != 0 {
        return memo[n];
    }
    memo[n] = fib_dp(n - 1, memo) + fib_dp(n - 2, memo);
    memo[n]
}

fn main() {
    let n = 7;
    let mut memo = vec![0; n + 1];
    println!("{}", fib_dp(n, &mut memo));
}

A 13

B 21

C 8

D 34

💡 Hint

The 7th Fibonacci number (0-based) is 13.

Using memoization, fib_dp(7) returns 13 as the sequence is 0,1,1,2,3,5,8,13...

❓ Predict Output

advanced

Output of Recursive vs DP for Coin Change Count

What is the output of this Rust code that calculates the number of ways to make change for 5 using coins [1, 2] with recursion and DP?

DSA Rust

fn count_ways_recursive(coins: &[u32], m: usize, n: u32) -> u32 {
    if n == 0 {
        return 1;
    }
    if n < 0 || m == 0 {
        return 0;
    }
    count_ways_recursive(coins, m - 1, n) + count_ways_recursive(coins, m, n - coins[m - 1])
}

fn count_ways_dp(coins: &[u32], n: u32) -> u32 {
    let m = coins.len();
    let mut table = vec![vec![0; (n + 1) as usize]; m + 1];
    for i in 0..=m {
        table[i][0] = 1;
    }
    for i in 1..=m {
        for j in 1..=n as usize {
            if coins[i - 1] as usize > j {
                table[i][j] = table[i - 1][j];
            } else {
                table[i][j] = table[i - 1][j] + table[i][j - coins[i - 1] as usize];
            }
        }
    }
    table[m][n as usize]
}

fn main() {
    let coins = [1, 2];
    let n = 5;
    println!("{} {}", count_ways_recursive(&coins, coins.len(), n), count_ways_dp(&coins, n));
}

A 4 3

B 3 3

C 3 4

D 4 4

💡 Hint

Count the ways to make 5 using 1 and 2 coins.

Both recursive and DP methods find 3 ways: {1,1,1,1,1}, {1,1,1,2}, {1,2,2}.

🧠 Conceptual

expert

Choosing the Right Tool: DP vs Recursion vs Greedy

Which of the following statements best explains when to use dynamic programming (DP) instead of recursion or greedy algorithms?

A Use recursion for all optimization problems because it is always faster than DP and greedy.

B Use DP only when recursion is impossible and greedy always gives the correct answer.

C Use greedy algorithms when subproblems overlap and recursion when the problem is too simple for DP.

D Use DP when the problem has overlapping subproblems and optimal substructure, recursion is too slow, and greedy fails to find the global optimum.

💡 Hint

Think about problem properties and algorithm efficiency.

DP is best when subproblems overlap and greedy does not guarantee the best solution; recursion alone can be inefficient.

Practice

1. Which approach is best suited when a problem has overlapping subproblems and optimal substructure?

easy

A. Dynamic Programming

B. Greedy Algorithm

C. Simple Recursion without memoization

D. Brute Force

Solution

1. Step 1: Understand problem characteristics

   Overlapping subproblems means the same smaller problems repeat. Optimal substructure means the best solution can be built from best solutions of smaller problems.

2. Step 2: Match approach to characteristics

   Dynamic Programming stores results of subproblems to avoid recomputation and uses optimal substructure to build the solution efficiently.

3. Final Answer:

   Dynamic Programming -> Option A

4. Quick Check:

   Overlapping subproblems + optimal substructure = Dynamic Programming [OK]

Hint: Use DP when subproblems repeat and build optimal solutions [OK]

Common Mistakes:

• Choosing greedy when subproblems overlap
• Using simple recursion without memoization causing slow code
• Confusing optimal substructure with greedy choice property

2. Which of the following Rust function signatures correctly represents a recursive function that returns an integer?

easy

A. fn factorial(n: u32) -> u32 { let mut result = 1; for i in 1..=n { result *= i; } result }

B. fn factorial(n: u32) { if n == 0 { 1 } else { n * factorial(n - 1) } }

C. fn factorial(n: u32) -> String { if n == 0 { "1".to_string() } else { (n * factorial(n - 1)).to_string() } }

D. fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } }

Solution

1. Step 1: Check function return type and recursion

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } returns u32 and calls itself recursively correctly. fn factorial(n: u32) { if n == 0 { 1 } else { n * factorial(n - 1) } } lacks return type, so it returns unit ().

2. Step 2: Validate correctness of recursion and return

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } correctly returns the factorial value recursively. fn factorial(n: u32) -> u32 { let mut result = 1; for i in 1..=n { result *= i; } result } is iterative, not recursive. fn factorial(n: u32) -> String { if n == 0 { "1".to_string() } else { (n * factorial(n - 1)).to_string() } } returns String, not integer.

3. Final Answer:

   fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } -> Option D

4. Quick Check:

   Recursive function with correct return type = fn factorial(n: u32) -> u32 { if n == 0 { 1 } else { n * factorial(n - 1) } } [OK]

Hint: Recursive functions must specify return type matching recursive calls [OK]

Common Mistakes:

• Omitting return type causes compilation errors
• Confusing iterative and recursive implementations
• Returning wrong data types in recursion

3. What is the output of the following Rust code using recursion to compute Fibonacci numbers?

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

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

medium

A. 13

B. 5

C. 3

D. 8

Solution

1. Step 1: Understand Fibonacci recursion

   fib(5) = fib(4) + fib(3). Calculate fib(4) and fib(3) similarly until base cases fib(1)=1 and fib(0)=0.

2. Step 2: Calculate fib(5) step-by-step

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Fibonacci of 5 = 5 [OK]

Hint: Trace base cases and add results up to n [OK]

Common Mistakes:

• Confusing fib(5) with fib(6)
• Miscounting base cases
• Assuming fib(0) = 1 instead of 0

4. The following Rust code attempts to implement a greedy algorithm for coin change but has a bug. What is the bug?

fn coin_change(coins: &[u32], amount: u32) -> u32 {
    let mut remaining = amount;
    let mut count = 0;
    for &coin in coins {
        count += remaining / coin;
        remaining %= coin;
    }
    if remaining == 0 { count } else { 0 }
}

fn main() {
    let coins = [1, 2, 5];
    println!("{}", coin_change(&coins, 11));
}

medium

A. The loop should break when remaining is zero

B. The function returns 0 instead of -1 when change is impossible

C. Coins are not sorted in descending order, so greedy fails

D. The function uses integer division which causes errors

Solution

1. Step 1: Check coin order

   Greedy coin change requires coins sorted in descending order to pick largest first. Here coins=[1, 2, 5] are ascending, so it picks smallest first.

2. Step 2: Trace execution

   For amount=11: coin=1, count=11, remaining=0; subsequent coins add 0. Returns 11, but optimal is 3 (5+5+1). Greedy suboptimal.

3. Final Answer:

   Coins are not sorted in descending order, so greedy fails -> Option C

4. Quick Check:

   Greedy needs descending coin order [OK]

Hint: Always sort coins descending for greedy coin change [OK]

Common Mistakes:

• Assuming greedy always works for any coin set
• Ignoring coin order importance
• Confusing return values for impossible change

5. You want to find the minimum number of coins needed to make a certain amount using coins of denominations [1, 3, 4]. Which approach is best and why?

hard

A. Use dynamic programming to store minimum coins needed for smaller amounts and build up

B. Use recursion without memoization to explore all combinations

C. Use a greedy algorithm because picking the largest coin first always gives minimum coins

D. Use simple iteration over coins without storing intermediate results

Solution

1. Step 1: Analyze greedy suitability

   Greedy fails here because picking largest coin first (4) may not lead to minimum coins for all amounts (e.g., amount=6).

2. Step 2: Consider recursion and DP

   Recursion without memoization repeats calculations and is inefficient. Dynamic programming stores results for smaller amounts, avoiding recomputation and ensuring minimum coins.

3. Final Answer:

   Use dynamic programming to store minimum coins needed for smaller amounts and build up -> Option A

4. Quick Check:

   Minimum coins with overlapping subproblems = Dynamic Programming [OK]

Hint: DP stores sub-results to find minimum coins efficiently [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Using recursion without memoization causing slow code
• Ignoring overlapping subproblems in coin change