DP vs Recursion vs Greedy Choosing the Right Tool in DSA C# - 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 easiest step each time, and DP remembers which steps cost less to avoid repeating work.

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

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

DP Table:
Index: 0 1 2 3
Value:25 15 20 0
Memo:  [check] [check] [check] [check]

Dry Run Walkthrough

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

Goal: Compare how recursion, greedy, and DP solve this problem

Step 1: Recursion tries climbing from step 0 and step 1 separately

Recursion calls:
min(climb(0), climb(1))
climb(0)=25, climb(1)=15

Why: We explore all possible starting points

Step 2: Recursion from step 0 calls climb(1) and climb(2)

climb(0) -> climb(1)=15, climb(2)=20
10 + min(15,20)=25

Why: We try all next steps from current position

Step 3: Greedy always picks locally cheapest next step to land on

start ->0(10) ->1(15) ->end(0)
Total cost: 25 (suboptimal)

Why: Greedy chooses immediate cheapest landing but misses global optimum

Step 4: DP fills table backward storing min cost from each step to end

DP table:
dp[2]=20, dp[1]=15, dp[0]=25

Why: DP remembers results to avoid repeated calculations

Step 5: DP returns min(dp[0], dp[1]) = min(25,15)=15

Optimal path: start ->1(15) ->end(0)

Why: Combines previous optimal sub-solutions for global minimum

Result:

Pure recursion finds 15 but with exponential repeated work
Greedy gets suboptimal 25 by local choices
DP efficiently finds optimal 15 in linear time

Annotated Code

DSA C#

using System;

class StairClimber
{
    static int[] costs = {10, 15, 20};

    // Recursion: tries all paths
    static int MinCostRecursion(int step)
    {
        if (step >= costs.Length) return 0;
        int costOneStep = MinCostRecursion(step + 1);
        int costTwoSteps = MinCostRecursion(step + 2);
        return costs[step] + Math.Min(costOneStep, costTwoSteps);
    }

    // Greedy: picks locally cheapest next landing
    static int MinCostGreedy()
    {
        int n = costs.Length;
        int total = 0;
        int pos = -1;
        while (pos + 1 < n || pos + 2 < n)
        {
            int next1 = pos + 1;
            int next2 = pos + 2;
            int c1 = next1 < n ? costs[next1] : 0;
            int c2 = next2 < n ? costs[next2] : 0;
            if (c1 <= c2)
            {
                total += c1;
                pos = next1;
            }
            else
            {
                total += c2;
                pos = next2;
            }
        }
        return total;
    }

    // DP: remembers results
    static int MinCostDP()
    {
        int n = costs.Length;
        int[] dp = new int[n + 2];
        for (int i = n - 1; i >= 0; i--)
        {
            dp[i] = costs[i] + Math.Min(dp[i + 1], dp[i + 2]);
        }
        return Math.Min(dp[0], dp[1]);
    }

    static void Main()
    {
        int rec = Math.Min(MinCostRecursion(0), MinCostRecursion(1));
        Console.WriteLine("Recursion result: " + rec);
        Console.WriteLine("Greedy result: " + MinCostGreedy());
        Console.WriteLine("DP result: " + MinCostDP());
    }
}

if (step >= costs.Length) return 0;

base case: past end costs 0

return costs[step] + Math.Min(costOneStep, costTwoSteps);

pay current + min of two possible futures

int c1 = next1 < n ? costs[next1] : 0; int c2 = next2 < n ? costs[next2] : 0; if (c1 <= c2) { total += c1; pos = next1; } else { ... }

greedy chooses cheaper next landing cost (0 if past end)

dp[i] = costs[i] + Math.Min(dp[i + 1], dp[i + 2]);

min cost from i: pay i + best of next 1 or 2 steps

return Math.Min(dp[0], dp[1]);

min over starting at step 0 or 1

Output

Recursion result: 15

Greedy result: 25

DP result: 15

Complexity Analysis

Time: O(phi^n) ~O(2^n) for pure recursion (fib-like); O(n) for DP and Greedy

Space: O(n) recursion stack; O(n) DP array; O(1) greedy

vs Alternative: DP optimizes recursion's repeated subproblems; greedy is fast but suboptimal here (25 vs 15)

Edge Cases

Empty cost array (n=0)

All return 0 (no stairs)

DSA C#

step >= 0 return 0; dp min(0,0)=0; greedy loop doesn't enter

n=2, costs=[10,15]

Recursion min(10+0,15+0)=10; Greedy min(10,15)=10 then end; DP min(10+0,15+0)=10

DSA C#

Math.Min(dp[0], dp[1])

All equal costs e.g. [5,5,5]

Optimal 10 (e.g. 0+2 or 1+end); greedy also 10

DSA C#

c1 <= c2 handles ties

When to Use This Pattern

Optimal paths with choices of 1/2 steps and overlapping subproblems: prefer DP. Test greedy if local optimum = global. Fallback to recursion + memo.

Common Mistakes

Mistake: Using pure recursion without memo: TLE on large n
Fix: Add memoization array or use bottom-up DP

Mistake: Wrong greedy logic, or assuming greedy works (here 25 != optimal 15)
Fix: Verify 'greedy choice property': does local best lead to global? Here no.

Mistake: Forgetting min(dp[0], dp[1]) , calling only from 0 gets 25 >15
Fix: Account for starting choices correctly

Summary

Recursion explores exhaustively (slow), greedy chases local optima (may fail), DP solves optimally efficiently by storing subproblem results.

Key: Recognize overlapping subproblems (DP), safe local choices (greedy), or brute-force ok (recursion).

Here greedy fails: teaches when to avoid it and use DP.

Practice

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

easy

A. Simple Recursion

B. Dynamic Programming

C. Greedy Algorithm

D. Brute Force

Solution

1. Step 1: Understand problem characteristics

   Overlapping subproblems mean 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, ideal for overlapping subproblems and optimal substructure.

3. Final Answer:

   Dynamic Programming -> Option B

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 optimal substructure with greedy choice

2. Which of the following C# code snippets correctly implements a greedy approach to find the maximum number of activities that don't overlap given start and end times arrays (assuming sorted by end time)?

easy

A. int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count);

B. int count = 0; for (int i = 0; i < start.Length; i++) { if (start[i] > end[i]) count++; } Console.WriteLine(count);

C. int count = 1; for (int i = 1; i < start.Length; i++) { if (end[i] >= start[i-1]) count++; } Console.WriteLine(count);

D. int count = 0; foreach (var s in start) { count += s; } Console.WriteLine(count);

Solution

1. Step 1: Understand greedy activity selection logic

   We select the first activity, then pick next activities starting after the last selected activity ends.

2. Step 2: Check code correctness

   int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count); initializes count to 1, tracks lastEnd, and increments count only if start[i] >= lastEnd, updating lastEnd. This matches greedy logic.

3. Final Answer:

   the code that tracks lastEnd -> Option A

4. Quick Check:

   Greedy activity selection code = int count = 1; int lastEnd = end[0]; for (int i = 1; i < start.Length; i++) { if (start[i] >= lastEnd) { count++; lastEnd = end[i]; } } Console.WriteLine(count); [OK]

Hint: Pick next activity starting after last selected ends [OK]

Common Mistakes:

• Not sorting activities by end time before selection
• Comparing start[i] with wrong end time
• Counting activities incorrectly

3. What is the output of the following C# code that uses recursion to calculate Fibonacci numbers without memoization?

int Fib(int n) { if (n <= 1) return n; return Fib(n - 1) + Fib(n - 2); } Console.WriteLine(Fib(5));

medium

A. 3

B. 8

C. 5

D. 13

Solution

1. Step 1: Trace recursive calls for Fib(5)

   Fib(5) = Fib(4) + Fib(3); Fib(4) = Fib(3) + Fib(2); Fib(3) = Fib(2) + Fib(1); Fib(2) = Fib(1) + Fib(0); Fib(1)=1, Fib(0)=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: Fibonacci(5) = 5 by definition [OK]

Common Mistakes:

• Confusing index starting at 0 or 1
• Miscomputing recursive sums
• Assuming memoization changes output

4. The following C# code attempts to solve the coin change problem using recursion but has a bug. What is the bug?

int CoinChange(int[] coins, int amount) { if (amount == 0) return 0; if (amount < 0) return -1; int min = int.MaxValue; foreach (int coin in coins) { int res = CoinChange(coins, amount - coin); if (res >= 0 && res < min) min = 1 + res; } return min == int.MaxValue ? -1 : min; }

medium

A. No memoization causing repeated calculations

B. Incorrect base case for amount == 0

C. Returning -1 instead of 0 for amount < 0

D. Using foreach instead of for loop

Solution

1. Step 1: Analyze recursion and base cases

   Base cases are correct: 0 returns 0, negative returns -1. The recursion tries all coins.

2. Step 2: Identify missing optimization

   Without memoization, the function recalculates subproblems many times, causing inefficiency and possible stack overflow.

3. Final Answer:

   No memoization causing repeated calculations -> Option A

4. Quick Check:

   Missing memoization = No memoization causing repeated calculations [OK]

Hint: Add memo dictionary to avoid repeated calls [OK]

Common Mistakes:

• Thinking base cases are wrong
• Believing loop type causes bug
• Ignoring performance issues

5. You want to find the minimum number of coins needed to make a given amount using coins of different denominations. Which approach is best and why?

hard

A. Greedy algorithm may fail for some coin sets

B. Simple iteration misses subproblem reuse

C. Recursion without memoization is inefficient

D. Dynamic programming ensures optimal solution efficiently

Solution

1. Step 1: Evaluate greedy approach limitations

   Greedy works only if coin denominations are canonical (like US coins). Otherwise, it can fail to find minimum coins.

2. Step 2: Consider recursion and iteration drawbacks

   Recursion without memoization repeats work; simple iteration without storing results misses subproblem reuse.

3. Step 3: Understand dynamic programming benefits

   DP with bottom-up tabulation stores minimum coins for all amounts up to target, guaranteeing optimal and efficient solution.

4. Final Answer:

   Dynamic programming ensures optimal solution efficiently -> Option D

5. Quick Check:

   Minimum coins problem = DP bottom-up [OK]

Hint: Use DP tabulation for guaranteed minimum coins [OK]

Common Mistakes:

• Assuming greedy always works
• Ignoring performance of recursion
• Not storing intermediate results