Recursive Algorithm Strategies

A recursive algorithm strategy is a family of trade-offs about when to split a problem, whether subproblems overlap, and whether a previously computed answer can be reused instead of recomputed — the choice of strategy (divide & conquer, dynamic programming, backtracking, greedy-recursion) follows directly from answering those three questions before you write a single line of code.

Recognize the pattern

• Problem naturally splits into independent halves/parts (sort, search, matrix) whose solutions combine with a cheap merge step → divide & conquer.
• Same exact subproblem (same parameters) gets asked for repeatedly as recursion unfolds → dynamic programming (memoize or tabulate).
• You must explore all valid configurations / need to enumerate or search a decision tree, abandoning a path as soon as it violates a constraint → backtracking.
• A locally-optimal recursive choice provably leads to a globally optimal one, no need to explore alternatives → greedy recursion.

Brute force vs optimal

Take Fibonacci as the running example because it cleanly exposes the difference between divide & conquer applied naively and dynamic programming.

Brute-force recursion (naive divide & conquer, no reuse): fib(n) = fib(n-1) + fib(n-2). Each call spawns two more, and fib(n-2) is recomputed independently inside both the fib(n-1) branch and directly — the subproblems overlap but nothing remembers that. Cost: exponential time, O(n) space (call stack depth).

Optimal (DP): cache each fib(k) the first time it is computed; every later request for fib(k) is an O(1) lookup. Cost: linear time, O(n) space (cache + stack, or O(1) with iterative bottom-up).

Complexity, derived

Brute force: let T(n) be the number of calls to compute fib(n). T(n) = T(n-1) + T(n-2) + 1, same recurrence shape as Fibonacci itself, so T(n) grows as φⁿ where φ ≈ 1.618 → O(φⁿ) time, O(n) space for the deepest call stack.

Memoized DP: there are only n+1 distinct subproblems (fib(0)..fib(n)); each is computed exactly once doing O(1) work beyond its two recursive lookups → O(n) time, O(n) space (memo table + recursion stack).

General divide & conquer recurrence (non-overlapping subproblems, e.g. merge sort): T(n) = a·T(n/b) + f(n). By the Master Theorem, if f(n) = O(n^log_ba), T(n) = O(n^log_ba log n). Merge sort: a=2, b=2, f(n)=O(n) → T(n) = O(n log n), space O(n) for merge buffers + O(log n) stack. Binary search is the degenerate case with a=1: T(n) = T(n/2) + O(1) → Θ(log n) — divide & conquer where one half is discarded instead of solved.

Traced worked example: fib(5)

Brute force makes 15 total calls for n=5 (growing exponentially); memoized DP makes exactly 6 distinct computations plus O(1) lookups for every repeat request.

Java: brute force vs memoized vs bottom-up

class Fib {
    // Brute force divide & conquer: O(phi^n) time, O(n) space
    static long fibBrute(int n) {
        if (n <= 1) return n;
        return fibBrute(n - 1) + fibBrute(n - 2);
    }

    // Top-down DP (memoized recursion): O(n) time, O(n) space
    // Entry point: the memo MUST be seeded with -1. A bare new long[n+1]
    // defaults to 0, so the guard below would treat every slot as "already
    // computed" and silently return 0 for all n >= 2.
    static long fib(int n) {
        long[] memo = new long[n + 1];
        java.util.Arrays.fill(memo, -1);   // -1 = "not computed yet"
        return fibMemo(n, memo);
    }

    static long fibMemo(int n, long[] memo) {
        if (n <= 1) return n;
        if (memo[n] != -1) return memo[n];
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }

    // Bottom-up DP (tabulation, no recursion): O(n) time, O(1) space
    static long fibIter(int n) {
        if (n <= 1) return n;
        long prev2 = 0, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            long cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Pitfalls

• Assuming overlap without checking: memoizing a problem whose subproblems never repeat (e.g. merge sort's ranges) wastes memory and a hashmap lookup for nothing.
• Wrong memo key: memoizing on a subset of the parameters that actually determine the answer silently returns stale results for a different state.
• Stack overflow: deep recursion (n ~ 10⁵+) on a non-tail-optimized language like Java blows the call stack; convert to bottom-up iteration for large n.
• Backtracking without pruning: exploring the full decision tree without early constraint checks turns exponential-but-prunable into actually-exponential.
• Divide & conquer overhead: combine step costlier than expected (e.g. naive concatenation instead of a linear merge) silently degrades the Master Theorem bound.

When to use / when not, vs alternatives

Takeaways

• Before coding a recursive algorithm, answer: how do I divide, how do I combine, and do subproblems repeat?
• Overlapping subproblems + optimal substructure is the exact signal to switch from divide & conquer to dynamic programming.
• The same recurrence that describes the problem (T(n) = T(n-1) + T(n-2)) also describes the brute-force call count — recognize this to derive complexity without a trace.
• Memoization trades space for time by turning repeated computation into O(1) lookups.

Recall: Why does naive recursive Fibonacci take exponential time while the recursion for merge sort (also two recursive calls) takes only O(n log n)?

Sources: CLRS (Cormen, Leiserson, Rivest, Stein), Introduction to Algorithms, ch. 4 & 15; original page content on recursive algorithm strategies.