DP vs Recursion vs Greedy Choosing the Right Tool in DSA Rust - Visual Comparison

Concept Flow - DP vs Recursion vs Greedy Choosing the Right Tool

Start Problem

↓

Is problem optimal substructure?

|Yes↓

Is problem overlapping subproblems?

↓

Use DP

↓

Build solution bottom-up or memoize

↓

If no optimal substructure

↓

Use Greedy if local choices lead to global optimum

↓

End

Decide which method to use by checking if the problem has optimal substructure and overlapping subproblems; use DP if both, recursion if only optimal substructure, and greedy if local choices lead to global optimum.

Execution Sample

DSA Rust

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

fn fib_dp(n: usize) -> usize {
    let mut dp = vec![0; n+1];
    dp[1] = 1;
    for i in 2..=n {
        dp[i] = dp[i-1] + dp[i-2];
    }
    dp[n]
}

Calculates Fibonacci numbers using recursion and dynamic programming to show difference in approach.

Execution Table

Step	Method	Operation	Call Stack / DP Array	Result / Partial Result	Notes
1	Recursion	Call fib_recursive(4)	Stack: fib_recursive(4)	Pending	Start recursive calls
2	Recursion	Call fib_recursive(3)	Stack: fib_recursive(4) -> fib_recursive(3)	Pending	Recursion continues
3	Recursion	Call fib_recursive(2)	Stack: fib_recursive(4) -> fib_recursive(3) -> fib_recursive(2)	Pending	Keep going deeper
4	Recursion	Call fib_recursive(1)	Stack: fib_recursive(4) -> fib_recursive(3) -> fib_recursive(2) -> fib_recursive(1)	1	Base case reached
5	Recursion	Return 1 from fib_recursive(1)	Stack unwinds	1	Return to fib_recursive(2)
6	Recursion	Call fib_recursive(0)	Stack: fib_recursive(4) -> fib_recursive(3) -> fib_recursive(2) -> fib_recursive(0)	0	Base case reached
7	Recursion	Return 0 from fib_recursive(0)	Stack unwinds	0	Return to fib_recursive(2)
8	Recursion	Calculate fib_recursive(2) = 1 + 0	Stack unwinds	1	Return to fib_recursive(3)
9	Recursion	Call fib_recursive(1)	Stack: fib_recursive(4) -> fib_recursive(3) -> fib_recursive(1)	1	Base case reached
10	Recursion	Return 1 from fib_recursive(1)	Stack unwinds	1	Return to fib_recursive(3)
11	Recursion	Calculate fib_recursive(3) = 1 + 1	Stack unwinds	2	Return to fib_recursive(4)
12	Recursion	Call fib_recursive(2)	Stack: fib_recursive(4) -> fib_recursive(2)	Pending	Repeat calls without memoization
13	Recursion	Call fib_recursive(1)	Stack: fib_recursive(4) -> fib_recursive(2) -> fib_recursive(1)	1	Base case
14	Recursion	Return 1 from fib_recursive(1)	Stack unwinds	1	Return to fib_recursive(2)
15	Recursion	Call fib_recursive(0)	Stack: fib_recursive(4) -> fib_recursive(2) -> fib_recursive(0)	0	Base case
16	Recursion	Return 0 from fib_recursive(0)	Stack unwinds	0	Return to fib_recursive(2)
17	Recursion	Calculate fib_recursive(2) = 1 + 0	Stack unwinds	1	Return to fib_recursive(4)
18	Recursion	Calculate fib_recursive(4) = 2 + 1	Stack unwinds	3	Final result
19	DP	Initialize dp array	dp = [0,1,0,0,0]	N/A	Start bottom-up
20	DP	Calculate dp[2] = dp[1] + dp[0] = 1 + 0	dp = [0,1,1,0,0]	1	Fill dp array
21	DP	Calculate dp[3] = dp[2] + dp[1] = 1 + 1	dp = [0,1,1,2,0]	2	Fill dp array
22	DP	Calculate dp[4] = dp[3] + dp[2] = 2 + 1	dp = [0,1,1,2,3]	3	Fill dp array
23	DP	Return dp[4]	dp = [0,1,1,2,3]	3	Final result
24	Greedy	Check if problem fits greedy	N/A	Depends on problem	Greedy applies if local choices lead to global optimum
25	End	Choose method based on problem properties	N/A	N/A	Decision complete

💡 Recursion ends when base cases reached; DP ends after filling array; Greedy chosen if problem fits criteria

Variable Tracker

Variable	Start	After Step 5	After Step 11	After Step 18	After Step 23
Call Stack Depth (Recursion)	0	4	2	1	0
fib_recursive(n)	4	1 (fib(1))	2 (fib(3))	3 (fib(4))	3 (final)
dp array (DP)	[]	[]	[]	[]	[0,1,1,2,3]

Key Moments - 3 Insights

Why does recursion call fib_recursive(2) multiple times?

Because recursion does not remember previous results, it recomputes fib_recursive(2) each time as shown in steps 12-17 in the execution_table.

How does DP avoid repeated calculations?

DP stores results in the dp array (see steps 19-23), so each fib number is computed once and reused, unlike recursion.

When should we choose greedy over DP or recursion?

If the problem has optimal substructure but no overlapping subproblems and local choices lead to global optimum, greedy is best (step 24).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of fib_recursive(3) when it returns at step 11?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Result / Partial Result' column at step 11 in execution_table

At which step does the dp array first get fully filled for n=4?

A Step 19

B Step 21

C Step 23

D Step 20

💡 Hint

Look at the dp array state in the 'Call Stack / DP Array' column in execution_table

If we add memoization to recursion, which step's repeated calls would be avoided?

A Steps 12-17

B Steps 4-7

C Steps 19-23

D Step 24

💡 Hint

Repeated calls to fib_recursive(2) happen at steps 12-17 as shown in execution_table

Concept Snapshot

DP vs Recursion vs Greedy:
- Recursion: simple, solves by calling itself, may repeat work
- DP: uses recursion + memoization or bottom-up to avoid repeats
- Greedy: picks best local choice, works if leads to global best
- Choose DP if overlapping subproblems + optimal substructure
- Choose recursion if only optimal substructure
- Choose greedy if local optimum leads to global optimum

Full Transcript

This visual execution compares dynamic programming, recursion, and greedy methods for solving problems. We start by checking if the problem has optimal substructure and overlapping subproblems. If both, dynamic programming is best because it stores intermediate results to avoid repeated work. If only optimal substructure, recursion works but may repeat calculations. Greedy is chosen if local choices lead to a global optimum. The Fibonacci example shows recursion calling the same function multiple times, while DP fills an array bottom-up to compute results once. Key moments highlight why recursion repeats work, how DP avoids it, and when greedy is suitable. The quizzes test understanding of recursion results, DP array filling, and memoization benefits.

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