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

Mental Model

We solve problems by breaking them down into smaller parts. Recursion tries all ways, greedy picks the best now, and DP remembers past results to avoid repeats.

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

Start
 ↓
[Recursion] -> tries all paths
 ↓
[Greedy] -> picks best immediate step
 ↓
[DP] -> remembers best results to avoid repeats

Dry Run Walkthrough

Input: Problem: Find minimum coins to make 6 cents with coins [1, 3, 4]

Goal: Find the fewest coins needed to make 6 cents

Step 1: Recursion tries all combinations starting with coin 1

Trying 1 -> remaining 5 -> tries 1 again -> remaining 4 ...

Why: Recursion explores every possible way to find minimum coins

Step 2: Greedy picks largest coin 4 first, then 1, then 1

4 + 1 + 1 = 3 coins total

Why: Greedy picks biggest coin now, hoping for minimum total

Step 3: DP stores results: min coins for 0=0, 1=1, 2=2, 3=1, 4=1, 5=2, 6=2

DP table: [0,1,2,1,1,2,2]

Why: DP avoids recalculating by remembering best results for smaller amounts

Result:

DP final answer: 2 coins (3 + 3) or (4 + 1 + 1) but DP finds 2 coins minimum
Coins used: 3 + 3

Annotated Code

DSA Go

package main
import "fmt"

// Recursive solution: tries all combinations
func minCoinsRec(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
    res := 1 << 30 // large number
    for _, c := range coins {
        if c <= amount {
            subRes := minCoinsRec(coins, amount-c)
            if subRes != 1<<30 && subRes+1 < res {
                res = subRes + 1
            }
        }
    }
    return res
}

// Greedy solution: picks largest coin first
func minCoinsGreedy(coins []int, amount int) int {
    count := 0
    for amount > 0 {
        maxCoin := 0
        for _, c := range coins {
            if c <= amount && c > maxCoin {
                maxCoin = c
            }
        }
        if maxCoin == 0 {
            return -1 // no solution
        }
        amount -= maxCoin
        count++
    }
    return count
}

// DP solution: stores minimum coins for each amount
func minCoinsDP(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = 1 << 30
        for _, c := range coins {
            if c <= i && dp[i-c] != 1<<30 && dp[i-c]+1 < dp[i] {
                dp[i] = dp[i-c] + 1
            }
        }
    }
    if dp[amount] == 1<<30 {
        return -1
    }
    return dp[amount]
}

func main() {
    coins := []int{1, 3, 4}
    amount := 6
    fmt.Println("Recursion result:", minCoinsRec(coins, amount))
    fmt.Println("Greedy result:", minCoinsGreedy(coins, amount))
    fmt.Println("DP result:", minCoinsDP(coins, amount))
}

for _, c := range coins { if c <= amount { subRes := minCoinsRec(coins, amount-c) ... } }

try all coin choices recursively to find minimum coins

for amount > 0 { find maxCoin <= amount; amount -= maxCoin; count++ }

pick largest coin possible greedily until amount is zero

for i := 1; i <= amount; i++ { for _, c := range coins { if c <= i { dp[i] = min(dp[i], dp[i-c]+1) } } }

build dp table bottom-up storing minimum coins for each amount

Output

Recursion result: 2

Greedy result: 3

DP result: 2

Complexity Analysis

Time: Recursion: O(k^n) because it tries all combinations; Greedy: O(n*k) where n is amount and k is coin types; DP: O(n*k) because it fills table for each amount and coin

Space: Recursion: O(n) for call stack; Greedy: O(1) constant space; DP: O(n) for dp array

vs Alternative: DP is more efficient than recursion by avoiding repeated work; greedy is fastest but can give wrong answer if problem is not greedy-friendly

Edge Cases

amount = 0

All methods return 0 coins needed

DSA Go

if amount == 0 { return 0 }

no coins smaller than amount

Greedy returns -1, DP returns -1, recursion returns large number (treated as no solution)

DSA Go

if maxCoin == 0 { return -1 }

coins with duplicates

Methods still work correctly as duplicates do not affect logic

DSA Go

for _, c := range coins { ... }

When to Use This Pattern

When a problem asks for optimal solutions with overlapping subproblems, consider DP; if it can be solved by making locally best choices, try greedy; if unsure, recursion helps explore all possibilities.

Common Mistakes

Mistake: Using greedy on problems where local best choice is not globally optimal
Fix: Analyze problem properties; if greedy fails, use DP or recursion

Mistake: Not caching results in recursion causing exponential time
Fix: Use memoization or switch to DP to store intermediate results

Summary

Recursion tries all possibilities, greedy picks best immediate choice, DP remembers past results to avoid repeats.

Use recursion to explore all options, greedy when local choices lead to global optimum, and DP when subproblems overlap and optimal substructure exists.

The key is to recognize problem structure: overlapping subproblems and optimal substructure mean DP; greedy works only if local optimum leads to global optimum.

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 parts.

2. Step 2: Match approach to characteristics

   Dynamic Programming stores results of subproblems to avoid repeated work, ideal for overlapping subproblems and optimal substructure.

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
• Confusing brute force with DP

2. Which of the following Go function signatures correctly represents a recursive function to compute factorial?

easy

A. func factorial(n int) { if n == 0 { return 1 } return n * factorial(n-1) }

B. func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) }

C. func factorial(n int) int { if n == 0 { return 0 } return n * factorial(n-1) }

D. func factorial(n int) int { if n == 1 { return 0 } return n * factorial(n-1) }

Solution

1. Step 1: Check function return type and base case

   Factorial returns int, so function must return int. Base case for factorial is n == 0 returning 1.

2. Step 2: Verify recursive call and return statement

   Recursive call multiplies n by factorial(n-1). func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } matches correct signature and logic.

3. Final Answer:

   func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } -> Option B

4. Quick Check:

   Correct return type and base case = func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } [OK]

Hint: Check base case and return type carefully in recursion [OK]

Common Mistakes:

• Missing return type in function signature
• Incorrect base case value
• Returning wrong type or no return

3. What is the output of this Go code using recursion to compute Fibonacci numbers?

func fib(n int) int {
  if n <= 1 {
    return n
  }
  return fib(n-1) + fib(n-2)
}

func main() {
  fmt.Println(fib(5))
}

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Trace fib(5) calls

   fib(5) = fib(4) + fib(3); fib(4) = fib(3) + fib(2); fib(3) = fib(2) + fib(1); fib(2) = fib(1) + fib(0)

2. Step 2: Calculate values bottom-up

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

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Fibonacci(5) = 5 [OK]

Hint: Remember Fibonacci sequence: 0,1,1,2,3,5,8... [OK]

Common Mistakes:

• Confusing index starting point
• Miscomputing recursive calls
• Assuming fib(1) = 0

4. Identify the error in this greedy algorithm code snippet for coin change in Go:

func coinChange(coins []int, amount int) int {
  count := 0
  for i := len(coins) - 1; i >= 0; i-- {
    for amount >= coins[i] {
      amount -= coins[i]
      count++
    }
  }
  if amount != 0 {
    return -1
  }
  return count
}

medium

A. Greedy may fail if coins are not canonical denominations

B. The inner loop should increment amount instead of decrement

C. Coins array must be sorted in ascending order

D. Return value should be amount instead of count

Solution

1. Step 1: Understand greedy coin change logic

   The code tries largest coins first, subtracting from amount until no longer possible.

2. Step 2: Identify limitation of greedy approach

   Greedy works only if coin denominations are canonical (like US coins). Otherwise, it may not find minimum coins or any solution.

3. Final Answer:

   Greedy may fail if coins are not canonical denominations -> Option A

4. Quick Check:

   Greedy correctness depends on coin set [OK]

Hint: Greedy coin change fails on non-standard coin sets [OK]

Common Mistakes:

• Assuming greedy always finds minimum coins
• Ignoring coin order importance
• Misunderstanding return values

5. You want to find the longest increasing subsequence (LIS) in an array. Which approach is best and why? A) Simple recursion tries all subsequences but is slow. B) Greedy picks local best but may miss global LIS. C) Dynamic Programming stores LIS lengths to avoid recomputation. D) Brute force enumerates all subsequences without optimization.

hard

A. Simple recursion is best for LIS

B. Greedy approach always finds LIS

C. Brute force is efficient for LIS

D. Dynamic Programming is best for LIS

Solution

1. Step 1: Analyze LIS problem nature

   LIS requires checking subsequences and their lengths. Simple recursion tries all but is exponential time.

2. Step 2: Compare approaches

   Greedy fails because local choices don't guarantee global LIS. DP stores LIS lengths for subproblems, improving efficiency.

3. Final Answer:

   Dynamic Programming is best for LIS -> Option D

4. Quick Check:

   LIS problem = DP best approach [OK]

Hint: Use DP for LIS to avoid exponential recursion [OK]

Common Mistakes:

• Choosing greedy for LIS
• Ignoring exponential time of recursion
• Thinking brute force is efficient