DP vs Recursion vs Greedy Choosing the Right Tool in DSA Python - 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 next step that looks easiest, and DP remembers which steps lead to the fastest climb to avoid trying the same paths again.

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

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

DP Table:
Index: 0 1 2 3 4
Value: x x x x x
Memo:  [check] [check] [check] [check] [check]

Dry Run Walkthrough

Input: Find minimum cost to climb stairs with costs [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]

Goal: Compare how recursion, greedy, and DP solve the problem and see which is best

Step 1: Recursion tries all paths from step 0

Recursion tree starts at 0, branches to 1 and 2

Why: Recursion explores every possible way to find minimum cost

Step 2: Greedy picks step 0 cost=1, then step 2 cost=1, then step 3 cost=1

Greedy path: 0(1) -> 2(1) -> 3(1)

Why: Greedy chooses the cheapest next step without looking ahead

Step 3: DP stores minimum cost for each step to avoid repeated work

DP memo: cost[0]=1, cost[1]=100, cost[2]=1, cost[3]=2 (1+1), ...

Why: DP remembers past results to speed up calculation

Step 4: Compare final costs: recursion and DP find minimum cost 6, greedy finds cost 7

Final costs: Recursion=6, DP=6, Greedy=7

Why: Greedy can miss the best path because it only looks at immediate cost

Result:

DP and recursion find minimum cost 6 -> 1 -> 2 -> 3 -> 4 -> 6 -> 7 -> end
Greedy finds cost 7 -> 1 -> 2 -> 3 -> 4 -> 5 -> 7 -> end

Annotated Code

DSA Python

class Solution:
    def minCostClimbingStairsRecursion(self, cost):
        def helper(i):
            if i >= len(cost):
                return 0
            # choose step i or i+1
            return cost[i] + min(helper(i+1), helper(i+2))
        return min(helper(0), helper(1))

    def minCostClimbingStairsGreedy(self, cost):
        i = 0
        total = 0
        while i < len(cost):
            if i == len(cost) - 1:
                total += cost[i]
                break
            # pick cheaper next step
            if cost[i+1] < cost[i+2]:
                total += cost[i+1]
                i += 2
            else:
                total += cost[i+2]
                i += 3
        return total

    def minCostClimbingStairsDP(self, cost):
        n = len(cost)
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        return dp[n]


cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
sol = Solution()
print("Recursion result:", sol.minCostClimbingStairsRecursion(cost))
print("Greedy result:", sol.minCostClimbingStairsGreedy(cost))
print("DP result:", sol.minCostClimbingStairsDP(cost))

return cost[i] + min(helper(i+1), helper(i+2))

recursively explore both next steps and pick minimum cost

if cost[i+1] < cost[i+2]:

greedy chooses next step with smaller immediate cost

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

dp stores minimum cost to reach step i using previous results

Output

Recursion result: 6

Greedy result: 7

DP result: 6

Complexity Analysis

Time: O(n) for DP and greedy because they scan the list 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

vs Alternative: DP improves recursion by remembering results to avoid repeated work; greedy is faster but can miss optimal solutions

Edge Cases

Empty cost list

Returns 0 cost as no steps to climb

DSA Python

if i >= len(cost): return 0

Single step cost list

Returns cost of that single step

DSA Python

return min(helper(0), helper(1))

All equal costs

All methods return same minimum cost

DSA Python

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

When to Use This Pattern

When a problem asks for an optimal solution with overlapping subproblems, consider DP; if it can be solved by making locally best choices, try greedy; if exploring all possibilities is needed, recursion is the fallback.

Common Mistakes

Mistake: Using greedy when problem requires global optimal solution
Fix: Switch to DP or recursion to explore all options or remember past results

Mistake: Not memoizing recursion leading to exponential time
Fix: Add memoization or convert to DP to avoid repeated calculations

Summary

Recursion tries all ways, greedy picks best now, DP remembers past results to avoid repeats.

Use recursion for simple exploration, greedy for fast local choices, DP for optimal solutions with overlapping subproblems.

The key is to know if local choices lead to global best (greedy) or if remembering past helps (DP).

Practice

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

easy

A. Brute Force

B. Greedy Algorithm

C. Dynamic Programming

D. Simple Recursion without memoization

Solution

1. Step 1: Understand problem properties

   Overlapping subproblems mean 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 properties

   Dynamic Programming stores results of subproblems to avoid repeated work, ideal for these properties.

3. Final Answer:

   Dynamic Programming -> Option C

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 problem needs global optimization
• Using simple recursion causing repeated calculations
• Confusing brute force with efficient methods

2. Which of the following Python function definitions correctly implements a recursive Fibonacci function?

easy

A. def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2)

B. def fib(n): for i in range(n): return fib(i-1) + fib(i-2)

C. def fib(n): while n > 1: n -= 1 return n

D. def fib(n): return n + fib(n-1)

Solution

1. Step 1: Check base case and recursion

   def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) correctly returns n if n <= 1, else calls fib(n-1) + fib(n-2).

2. Step 2: Verify other options

   Options B, C, and D have syntax or logic errors: B uses for loop wrongly, C uses while without recursion, D causes infinite recursion.

3. Final Answer:

   def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) -> Option A

4. Quick Check:

   Correct recursive base and calls = def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2) [OK]

Hint: Base case + two recursive calls = correct Fibonacci recursion [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursion incorrectly
• Wrong return statements inside recursion

3. What is the output of the following code?

def max_sum(arr, n):
    if n == 0:
        return 0
    elif n == 1:
        return arr[0]
    else:
        return max(max_sum(arr, n-1), max_sum(arr, n-2) + arr[n-1])

print(max_sum([3, 2, 7, 10], 4))

medium

A. 13

B. 17

C. 20

D. 10

Solution

1. Step 1: Understand function logic

   max_sum returns max sum of non-adjacent elements from first n elements.

2. Step 2: Trace calls for n=4

   max_sum(arr,4) = max(max_sum(arr,3), max_sum(arr,2) + arr[3]) max_sum(arr,3) = max(max_sum(arr,2), max_sum(arr,1) + arr[2]) max_sum(arr,2) = max(max_sum(arr,1), max_sum(arr,0) + arr[1]) Calculate bottom-up: max_sum(arr,0)=0 max_sum(arr,1)=3 max_sum(arr,2)=max(3,0+2)=3 max_sum(arr,3)=max(3,3+7)=10 max_sum(arr,4)=max(10,3+10)=13

3. Final Answer:

   13 -> Option A

4. Quick Check:

   Max sum non-adjacent = 13 [OK]

Hint: Trace recursion bottom-up for max sum non-adjacent [OK]

Common Mistakes:

• Adding adjacent elements mistakenly
• Confusing indices in recursion
• Ignoring base cases

4. The following code tries to solve the coin change problem using recursion but has an error. What is the error?

def coin_change(coins, amount):
    if amount == 0:
        return 1
    if amount < 0:
        return 0
    count = 0
    for coin in coins:
        count += coin_change(coins, amount - coin)
    return count

print(coin_change([1, 2], 3))

medium

A. It does not handle negative amounts correctly

B. It counts duplicate combinations multiple times

C. It misses base case for amount == 1

D. It uses iteration instead of recursion

Solution

1. Step 1: Analyze recursion logic

   The function counts ways to make amount by subtracting coins recursively.

2. Step 2: Identify counting duplicates

   Because it tries all coins at each step without order control, it counts same combinations in different orders multiple times.

3. Final Answer:

   It counts duplicate combinations multiple times -> Option B

4. Quick Check:

   Duplicates counted due to unordered recursion [OK]

Hint: Unordered recursion counts duplicates; use order or DP to fix [OK]

Common Mistakes:

• Assuming base cases are missing
• Confusing negative amount handling
• Thinking iteration replaces recursion

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

hard

A. Brute force trying all combinations without optimization

B. Simple recursion without memoization for clarity

C. Greedy algorithm because always picking largest coin works

D. Dynamic Programming to store and reuse subproblem results

Solution

1. Step 1: Understand problem requirements

   We want minimum coins to make amount, which requires checking all combinations to find optimal.

2. Step 2: Evaluate approaches

   Greedy fails here because picking largest coin first may not yield minimum coins (e.g., amount=6, greedy picks 4+1+1=3 coins, but 3+3=2 coins is better). Simple recursion repeats subproblems causing inefficiency. DP stores results to avoid repeated work and finds optimal solution efficiently.

3. Final Answer:

   Dynamic Programming to store and reuse subproblem results -> Option D

4. Quick Check:

   Minimum coins with overlapping subproblems = DP [OK]

Hint: Use DP for minimum coins; greedy can fail with some denominations [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Ignoring efficiency of memoization
• Using brute force causing timeouts