Recursion, Dynamic Programming, Greedy, Backtracking

This chapter covers the four major algorithmic paradigms: recursion, dynamic programming, greedy algorithms, and backtracking.

Why This Matters

These paradigms solve a huge fraction of algorithmic problems. Recognizing which one applies — and converting a naive recursive solution into an efficient one — is a core engineering skill.

Prerequisites

• c.ds.1 — complexity.
• c.core.18 — recursion.

Core Concept

Recursion

Express a problem in terms of smaller instances, with a base case.

Dynamic programming (DP)

Solve overlapping subproblems once and store results (memoization or bottom-up tabulation) to avoid recomputation.

Greedy

Make the locally optimal choice at each step, hoping for a global optimum. Works only when the problem has optimal substructure and the greedy choice is provably safe.

Backtracking

Systematically explore candidate solutions, abandoning a partial solution as soon as it cannot lead to a valid one (pruning).

Examples

Fibonacci (recursion → DP)

/* Naive: O(2^n) */
unsigned long fib_rec(unsigned n)
{
    return n <= 1 ? n : fib_rec(n - 1) + fib_rec(n - 2);
}

/* DP (bottom-up): O(n), O(1) space */
unsigned long fib_dp(unsigned n)
{
    unsigned long a = 0, b = 1;
    if (n == 0) return a;
    for (unsigned i = 2; i <= n; i++) {
        unsigned long c = a + b;
        a = b; b = c;
    }
    return b;
}

Knapsack (0/1 DP)

/* dp[w] = max value for capacity w */
for (int i = 0; i < n; i++)
    for (int w = W; w >= weight[i]; w--)
        if (dp[w - weight[i]] + value[i] > dp[w])
            dp[w] = dp[w - weight[i]] + value[i];

Greedy coin change (with canonical denominations)

int coins[] = {25, 10, 5, 1};
int n = 0;
for (int i = 0; amount > 0; i++) {
    n += amount / coins[i];
    amount %= coins[i];
}

Backtracking (N-queens skeleton)

void solve(int row, int *cols, int n)
{
    if (row == n) { /* found a placement */ return; }
    for (int c = 0; c < n; c++) {
        if (is_safe(cols, row, c)) {
            cols[row] = c;
            solve(row + 1, cols, n);
        }
    }
}

How It Works

Recursion breaks a problem down; DP memoizes/tabulates overlapping results; greedy commits to local choices; backtracking searches the space with pruning.

Variations

Top-down vs. bottom-up DP

Memoization (top-down) is easy to write but uses recursion; tabulation (bottom-up) is iterative and often uses less space.

Branch and bound

Backtracking plus a bound to prune suboptimal branches (used in optimization).

Common Mistakes

• Missing the base case in recursion.
• Forgetting to memoize (exponential blowup).
• Applying greedy to problems where it is not optimal (e.g., 0/1 knapsack).
• Not pruning in backtracking (exponential search).

Undefined Behavior

• Stack overflow from excessive recursion depth. VERIFIED
• Signed overflow in DP state (e.g., int Fibonacci). VERIFIED

Portability

• Plain C, portable.

Under the Hood

Recursion uses the call stack (c.core.18). DP trades memory for time. Greedy and backtracking are control-flow patterns, not special machinery.

Practical Usage

• Use DP for optimization problems with overlapping subproblems.
• Use greedy only when you can prove correctness.
• Use backtracking for constraint satisfaction and exhaustive search.

Exercises

1. Implement Fibonacci recursively and with DP; compare runtimes. 2. Solve 0/1 knapsack with bottom-up DP. 3. Solve coin change with greedy and explain when it fails. 4. Implement N-queens with backtracking.

Deep Challenge

Implement the longest common subsequence (LCS) with DP, and recover the actual subsequence (not just its length). Explain the time/space complexity and how to reduce space to O(min(n, m)).

Related Concepts

• c.ds.2 — arrays for DP tables.
• c.core.18 — recursion.
• c.alg.3 — graph algorithms.

References

• CLRS, Sedgewick.

Verification

• Paradigm definitions and example algorithms. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Recursion
• [ ] Dynamic programming
• [ ] Greedy algorithms
• [ ] Backtracking

Mastery levels