DP vs Recursion vs Greedy Choosing the Right Tool in DSA Rust - Trade-offs & Analysis

Mental Model

We have three ways to solve problems: recursion tries all options, greedy picks the best now, and dynamic programming remembers past results to avoid repeats.

Analogy: Imagine climbing stairs: recursion tries every path, greedy picks the easiest step each time, and dynamic programming remembers the best way to each step to save effort.

Recursion Tree:
    root
   /    \
  ...    ...

Greedy Path:
start -> best choice -> best choice -> end

DP Table:
Index: 0 1 2 3 4
Value: _ _ _ _ _
Memo:  x x x x x

Dry Run Walkthrough

Input: Find minimum cost to climb stairs with costs [10, 15, 20]

Goal: Show how recursion, greedy, and DP solve the same problem differently

Step 1: Recursion tries climbing from step 0: cost 10 + min cost from step 1

Recursion tree starts at step 0
Costs: 10 + ?

Why: Recursion explores all paths to find minimum

Step 2: Recursion tries climbing from step 1: cost 15 + min cost from step 2

Recursion tree explores step 1
Costs: 15 + ?

Why: Recursion continues exploring all options

Step 3: Recursion reaches step 2: cost 20, no further steps

Recursion leaf at step 2
Costs: 20

Why: Base case reached, recursion returns cost

Step 4: Greedy picks step 0 cost 10, then step 2 cost 20 skipping step 1

Greedy path: 10 -> skip 15 -> 20
Total cost: 30

Why: Greedy picks locally cheapest next step

Step 5: DP fills memo: cost at step 2 is 20

DP memo: [_, _, 20]

Why: DP stores known costs to avoid repeats

Step 6: DP computes cost at step 1: 15 + cost at step 2 (20) = 35

DP memo: [_, 35, 20]

Why: DP uses stored results to build up solution

Step 7: DP computes cost at step 0: 10 + min(cost at step 1, cost at step 2) = 10 + min(35, 20) = 30

DP memo: [30, 35, 20]

Why: DP finds minimum cost using memoized results

Result:

Final costs: Recursion and DP find minimum cost 30; Greedy also finds 30 but by skipping step 1
DP memo: [30, 35, 20]

Annotated Code

DSA Rust

struct Solution;

impl Solution {
    // Recursive solution without memoization
    fn min_cost_climbing_stairs_rec(cost: &[i32], i: usize) -> i32 {
        if i >= cost.len() {
            return 0; // base case: beyond last step
        }
        // cost of current step + min cost of next one or two steps
        let one_step = Self::min_cost_climbing_stairs_rec(cost, i + 1);
        let two_steps = Self::min_cost_climbing_stairs_rec(cost, i + 2);
        cost[i] + one_step.min(two_steps)
    }

    // Greedy solution (not always optimal for all problems)
    fn min_cost_climbing_stairs_greedy(cost: &[i32]) -> i32 {
        let mut total = 0;
        let mut i = 0;
        while i < cost.len() {
            total += cost[i];
            // choose next step with smaller cost if possible
            if i + 2 < cost.len() && cost[i + 2] < cost[i + 1] {
                i += 2;
            } else {
                i += 1;
            }
        }
        total
    }

    // Dynamic programming with memoization
    fn min_cost_climbing_stairs_dp(cost: &[i32]) -> i32 {
        let n = cost.len();
        let mut dp = vec![0; n + 2]; // extra space to avoid bounds
        for i in (0..n).rev() {
            dp[i] = cost[i] + dp[i + 1].min(dp[i + 2]); // store min cost from step i
        }
        dp[0].min(dp[1]) // can start from step 0 or 1
    }
}

fn main() {
    let cost = vec![10, 15, 20];
    let rec = Solution::min_cost_climbing_stairs_rec(&cost, 0).min(Solution::min_cost_climbing_stairs_rec(&cost, 1));
    let greedy = Solution::min_cost_climbing_stairs_greedy(&cost);
    let dp = Solution::min_cost_climbing_stairs_dp(&cost);
    println!("Recursion min cost: {}", rec);
    println!("Greedy min cost: {}", greedy);
    println!("DP min cost: {}", dp);
}

if i >= cost.len() { return 0; }

base case: no cost beyond last step

let one_step = Self::min_cost_climbing_stairs_rec(cost, i + 1);

recurse to next step

let two_steps = Self::min_cost_climbing_stairs_rec(cost, i + 2);

recurse to step after next

cost[i] + one_step.min(two_steps)

choose minimum cost path

if i + 2 < cost.len() && cost[i + 2] < cost[i + 1] { i += 2; } else { i += 1; }

greedy picks cheaper next step

for i in (0..n).rev() { dp[i] = cost[i] + dp[i + 1].min(dp[i + 2]); }

fill dp table from end using memoized results

dp[0].min(dp[1])

start from step 0 or 1 for minimum cost

Output

Recursion min cost: 30

Greedy min cost: 30

DP min cost: 30

Complexity Analysis

Time: O(n) for DP and greedy because they compute each step once; O(2^n) for recursion because it explores all paths

Space: O(n) for DP due to memo array; O(n) for recursion due to call stack; O(1) for greedy as it uses constant extra space

vs Alternative: DP improves recursion by storing results to avoid repeated work; greedy is faster but may fail if local choices are not globally optimal

Edge Cases

Empty cost array

Returns 0 cost as no steps to climb

DSA Rust

if i >= cost.len() { return 0; }

Single step cost array

Returns cost of that single step

DSA Rust

dp[i] = cost[i] + dp[i + 1].min(dp[i + 2]);

Costs with equal values

All methods return correct minimum cost

DSA Rust

cost[i] + one_step.min(two_steps)

When to Use This Pattern

When a problem asks for optimal choices over steps or stages, consider DP if overlapping subproblems exist, recursion if simple exploration is enough, or greedy if local choices guarantee global optimum.

Common Mistakes

Mistake: Using greedy when problem requires global optimization leading to wrong answer
Fix: Check if greedy choice property holds; if not, use DP or recursion

Mistake: Not memoizing recursion causing exponential time
Fix: Add memoization or switch to DP to store intermediate results

Summary

Shows how recursion explores all options, greedy picks local best, and DP remembers past results to optimize.

Use recursion for simple problems, DP for overlapping subproblems, and greedy when local choices lead to global optimum.

The key is to recognize problem structure to pick the right tool for efficiency and correctness.

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