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.