Algorithmic Foundations

Recursion & Recurrences

A recursive algorithm solves a problem by solving smaller instances of itself; a recurrence relation is the equation describing its running time in terms of those smaller instances.

Every recursive method needs a base case that terminates without recursing, and progress toward it on every call
The call stack is real memory: depth n recursion uses O(n) stack frames and can overflow
A recurrence like T(n) = 2T(n/2) + O(n) describes divide-and-conquer cost; the Master Theorem solves the common shapes directly
Tail-recursive-looking Java code is not optimized away — the JVM keeps every frame, unlike languages with guaranteed tail-call elimination
Memoization turns exponential naive recursion into polynomial time by caching subproblem results (Dynamic Programming)

Recursion is a direct translation of an inductive proof into code: establish a base case, assume the recursive call correctly solves a smaller instance, then show how to combine that result into a solution for the current instance (Correctness And Invariants). The two failure modes are symmetric: no base case (infinite recursion, StackOverflowError) and a recursive call that does not shrink the problem (same failure, disguised).

Master Theorem cheat sheet for T(n) = aT(n/b) + f(n)
Compare f(n) to n^(log_b a)	Result	Example
f(n) smaller	T(n) = Θ(n^(log_b a))	T(n) = 8T(n/2) + n² → Θ(n³)
f(n) equal	T(n) = Θ(n^(log_b a) · log n)	T(n) = 2T(n/2) + n → Θ(n log n) (mergesort)
f(n) larger	T(n) = Θ(f(n))	T(n) = T(n/2) + n² → Θ(n²)

Naive vs memoized Fibonacci — the recurrence made visible

static long fibNaive(int n) {                 // T(n) = T(n-1) + T(n-2) + O(1) -> Θ(φ^n)
    if (n <= 1) return n;                      // base case
    return fibNaive(n - 1) + fibNaive(n - 2);  // two smaller instances
}

static long fibMemo(int n, long[] cache) {    // Θ(n) — each subproblem solved once
    if (n <= 1) return n;
    if (cache[n] != 0) return cache[n];
    return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}