Recursion and Recurrences¶

Recursion solves a problem using solutions to smaller instances of the same problem. A valid recursive design needs base cases and progress toward them.

The call stack¶

static long factorial(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("n must be non-negative");
    }
    return n < 2 ? 1L : Math.multiplyExact(n, factorial(n - 1));
}

The mathematical definition is clear, but Java does not guarantee tail-call elimination. The method uses Θ(n) stack frames and overflows long for relatively small n; mathematical correctness does not remove machine limits.

Recurrences¶

A recurrence relates the cost for size n to smaller costs.

Recurrence	Typical result	Example
`T(n) = T(n - 1) + Θ(1)`	`Θ(n)`	Linear recursion
`T(n) = T(n/2) + Θ(1)`	`Θ(log n)`	Binary search
`T(n) = 2T(n/2) + Θ(n)`	`Θ(n log n)`	Merge sort
`T(n) = T(n - 1) + Θ(n)`	`Θ(n²)`	Poorly balanced partitioning

Recursion tree intuition¶

For merge sort, each level performs Θ(n) total merge work. There are Θ(log n) levels, so the total is Θ(n log n).

The Master Theorem applies to recurrences of the form T(n) = aT(n/b) + f(n) under its stated regularity conditions. It does not directly handle T(n - 1) or arbitrary unequal subproblem sizes.

Memoization¶

Naive Fibonacci recursion repeats subproblems and takes exponential time. Memoization stores results, reducing the work to Θ(n) time and Θ(n) space. Bottom-up dynamic programming can remove recursion while preserving the same dependency structure. The dedicated memoization guide explains key correctness, lifetime, concurrency, and the distinction from an application cache.

Exercises¶

Draw the recursion tree for T(n) = 3T(n/2) + Θ(n).
Convert recursive factorial to an iterative method.
Identify the base case and progress measure in recursive binary search.