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 choosing a path in a maze: recursion tries every path, greedy picks the closest exit at each step, and DP remembers which paths lead to dead ends to avoid repeating mistakes.

Recursion: Tree of calls branching out
DP: Table storing answers to subproblems
Greedy: Step-by-step choices

Example:
Start
 ↓
[Try all paths]
 ↙   ↓   ↘
Path1 Path2 Path3

DP Table:
+-----+-----+-----+
|  0  |  1  |  2  |
+-----+-----+-----+

Greedy Steps:
Start -> Best choice -> Next best -> End

Dry Run Walkthrough

Input: Find minimum coins to make 6 using coins [1, 3, 4]

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

Step 1: Recursion tries all coin combinations to make 6

Recursion tree:
6
├─ 6-1=5
│  ├─ 5-1=4
│  ├─ 5-3=2
│  └─ 5-4=1
├─ 6-3=3
└─ 6-4=2

Why: Recursion explores every possible way to find minimum coins

Step 2: Greedy picks largest coin <= current amount repeatedly

Greedy steps:
6 - 4 = 2
2 - 1 = 1
1 - 1 = 0
Coins used: 3 (4,1,1)

Why: Greedy makes local best choice without checking all options

Step 3: DP builds table from 0 to 6 storing minimum coins needed

DP table:
Amount: 0 1 2 3 4 5 6
Coins: 0 1 2 1 1 2 2

Why: DP remembers best answers for smaller amounts to build up solution

Result:

DP final answer: 2 coins (3 + 3)
Greedy answer: 3 coins (4 + 1 + 1)
Recursion finds minimum but is slow

Annotated Code

DSA C

#include <stdio.h>
#include <limits.h>

int min(int a, int b) {
    return (a < b) ? a : b;
}

// Recursive solution
int minCoinsRec(int coins[], int n, int amount) {
    if (amount == 0) return 0;
    int res = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (coins[i] <= amount) {
            int sub_res = minCoinsRec(coins, n, amount - coins[i]);
            if (sub_res != INT_MAX && sub_res + 1 < res)
                res = sub_res + 1;
        }
    }
    return res;
}

// Greedy solution
int minCoinsGreedy(int coins[], int n, int amount) {
    int count = 0;
    int remaining = amount;
    while (remaining > 0) {
        int coin = -1;
        for (int i = 0; i < n; i++) {
            if (coins[i] <= remaining && (coin == -1 || coins[i] > coins[coin]))
                coin = i;
        }
        if (coin == -1) return -1; // no coin fits
        remaining -= coins[coin];
        count++;
    }
    return count;
}

// DP solution
int minCoinsDP(int coins[], int n, int amount) {
    int dp[amount + 1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    return dp[amount];
}

int main() {
    int coins[] = {1, 3, 4};
    int n = sizeof(coins) / sizeof(coins[0]);
    int amount = 6;

    int resRec = minCoinsRec(coins, n, amount);
    int resGreedy = minCoinsGreedy(coins, n, amount);
    int resDP = minCoinsDP(coins, n, amount);

    printf("Recursion: Minimum coins needed = %d\n", resRec);
    printf("Greedy: Minimum coins needed = %d\n", resGreedy);
    printf("DP: Minimum coins needed = %d\n", resDP);

    return 0;
}

for (int i = 0; i < n; i++) { if (coins[i] <= amount) { int sub_res = minCoinsRec(coins, n, amount - coins[i]); if (sub_res != INT_MAX && sub_res + 1 < res) res = sub_res + 1; } }

try all coin choices recursively to find minimum coins

while (remaining > 0) { int coin = -1; for (int i = 0; i < n; i++) { if (coins[i] <= remaining && (coin == -1 || coins[i] > coins[coin])) coin = i; } if (coin == -1) return -1; remaining -= coins[coin]; count++; }

pick largest coin possible repeatedly until amount is zero

for (int i = 1; i <= amount; i++) { dp[i] = INT_MAX; for (int j = 0; j < n; j++) { if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) { dp[i] = min(dp[i], dp[i - coins[j]] + 1); } } }

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

Output

Recursion: Minimum coins needed = 2

Greedy: Minimum coins needed = 3

DP: Minimum coins needed = 2

Complexity Analysis

Time: Recursion: O(n^amount) because it tries all combinations; Greedy: O(amount * n) because it picks coins repeatedly; DP: O(n * amount) because it fills a table for all amounts and coins

Space: Recursion: O(amount) due to call stack; Greedy: O(1) uses no extra storage; DP: O(amount) for the dp table

vs Alternative: DP is faster than recursion by avoiding repeated work; greedy is fastest but can give wrong answers if problem needs global view

Edge Cases

amount = 0

All methods return 0 coins needed

DSA C

if (amount == 0) return 0;

coins array empty

Greedy returns -1, recursion and DP return INT_MAX or no solution

DSA C

if (coin == -1) return -1;

amount cannot be formed by coins

Recursion and DP return INT_MAX, greedy returns -1

DSA C

if (sub_res != INT_MAX && sub_res + 1 < res)

When to Use This Pattern

When a problem asks for optimal choices over subproblems, consider DP; if it can be solved by local best choices, try greedy; if unsure, recursion helps explore all options but may be slow.

Common Mistakes

Mistake: Using greedy for problems where local best choice is not optimal globally
Fix: Use DP or recursion to explore all options or remember past results

Mistake: Not handling base case amount=0 in recursion
Fix: Add base case to return 0 when amount is zero

Summary

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

Use recursion to explore all options, greedy when local choices lead to global optimum, and DP when overlapping subproblems exist.

The key is to know if the problem has optimal substructure and overlapping subproblems to pick DP, or if greedy choices are safe.

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 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 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 causing slow code
• Confusing optimal substructure with greedy choice property

2. Which of the following is the correct syntax to implement memoization in C for a recursive Fibonacci function?

easy

A. Use a global array to store results and check before recursive calls

B. Use a local variable inside the function to store results

C. Use a static variable without initialization inside the function

D. Use a pointer without allocating memory for memoization

Solution

1. Step 1: Understand memoization storage

   Memoization requires storing results outside the recursive calls to reuse them. A global or static array is suitable.

2. Step 2: Check options for correct usage

   Only a global array checked before recursion ensures stored results are reused properly. Local variables reset each call, static without init may cause errors, pointers need allocation.

3. Final Answer:

   Use a global array to store results and check before recursive calls -> Option A

4. Quick Check:

   Memoization needs persistent storage = global array [OK]

Hint: Memoize with global/static array checked before recursion [OK]

Common Mistakes:

• Using local variables that reset each call
• Not initializing static variables properly
• Using pointers without memory allocation

3. What will be the output of the following C code snippet implementing a greedy approach for coin change?

int coins[] = {25, 10, 5, 1};
int amount = 30;
int count = 0;
for (int i = 0; i < 4; i++) {
    while (amount >= coins[i]) {
        amount -= coins[i];
        count++;
    }
}
printf("%d\n", count);

medium

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Trace the greedy coin selection

   Start with 30 amount. Use 25 coin once (30-25=5), count=1. Then 10 coin can't be used (5<10). Use 5 coin once (5-5=0), count=2.

2. Step 2: Count total coins used

   Coins used: 25 (1), 5 (1), total count = 2 coins. The code increments count inside while loop, so count=2.

3. Step 3: Check for remaining coins

   Amount is now 0, so no more coins used.

4. Final Answer:

   2 -> Option B

5. Quick Check:

   Greedy coin count for 30 = 2 coins [OK]

Hint: Subtract largest coin repeatedly until amount zero [OK]

Common Mistakes:

• Counting coins incorrectly by missing loops
• Assuming greedy always gives minimum coins
• Confusing coin values and counts

4. Identify the error in this recursive function for factorial and suggest the fix:

int factorial(int n) {
    if (n == 0) return 0;
    return n * factorial(n - 1);
}

medium

A. Recursive call should be factorial(n + 1)

B. Function should return void

C. Base case should return 1 instead of 0

D. No error, code is correct

Solution

1. Step 1: Analyze base case correctness

   Factorial of 0 is 1, but code returns 0, which will cause all results to be zero.

2. Step 2: Suggest correct base case

   Change base case to return 1 when n == 0 to correctly end recursion and compute factorial.

3. Final Answer:

   Base case should return 1 instead of 0 -> Option C

4. Quick Check:

   Factorial(0) = 1 base case [OK]

Hint: Factorial base case returns 1, not 0 [OK]

Common Mistakes:

• Returning 0 in base case causing zero product
• Changing recursion direction incorrectly
• Ignoring base case leading to infinite recursion

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

hard

A. Brute force, to try all combinations without optimization

B. Recursion without memoization, to explore all possibilities

C. Greedy, because always picking largest coin works

D. Dynamic Programming, to store and reuse subproblem results

Solution

1. Step 1: Understand problem requirements

   Minimum coins for amount with coins {1,3,4} needs checking all combinations to find optimal solution.

2. Step 2: Evaluate approaches

   Greedy fails here because picking largest coin first may not yield minimum coins. Recursion without memoization is slow. Dynamic Programming stores results of smaller amounts to build 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 when greedy fails to find minimum coins [OK]

Common Mistakes:

• Assuming greedy always works for coin change
• Using recursion without memo causing slow code
• Ignoring overlapping subproblems in coin change