Recursion and Recurrence Relations: Analyzing Self-Referential Algorithms

Understand recursion — a function defined in terms of itself, stopped by a base case — as the prerequisite both the sibling algorithm-analysis-order-of-growth and dynamic-programming-fundamentals concepts lean on without re-deriving: every recursive algorithm's running time is itself defined by a recurrence relation (T(n) in terms of T at smaller inputs), and how that recurrence is shaped — subtracting a constant from n versus dividing n — is the single biggest lever on whether the result is linear, exponential, or logarithmic. This concept is where that shape gets read off a recursive definition and turned into a closed-form bound, by hand, before either sibling concept is needed.

• Recognizing, from a recursive function's own structure, roughly what its running time will be before running it — the difference between T(n) = T(n-1) + O(1) (linear) and T(n) = 2T(n-1) + O(1) (exponential) is one multiplier, and it decides whether an input of size 40 finishes instantly or effectively never.
• Any naturally self-referential problem: tree/graph traversal, divide-and-conquer algorithms (mergesort, quicksort, Strassen's matrix multiplication), backtracking search — anywhere the problem's own definition already describes itself in terms of a smaller version of itself.
• Deciding whether a recursive solution needs the fix the sibling dynamic-programming-fundamentals concept covers — a recursive algorithm that calls itself on the same smaller subproblem more than once (naive Fibonacci, naive rod cutting) is a memoization/tabulation candidate; one that never revisits a subproblem (mergesort's two halves) isn't, and caching it would only add overhead.
• Estimating whether a recursive implementation is even safe to run in Java specifically, where deep recursion risks a real, JVM-level failure (StackOverflowError), not just slowness.

What makes a definition recursive: a base case, and a step that shrinks toward it

A function (or, more generally, a class of objects) is recursive when it is defined in terms of itself, via exactly two ingredients: a base case — a condition where the process terminates and produces an answer directly, with no further self-reference — and a recursive step — a rule that reduces every other case to a smaller instance of the same problem, eventually reaching the base case. Factorial is the simplest possible worked example: n! = n · (n-1)!, bottoming out at 1! = 1.

java
static long factorial(int n) {
    if (n <= 1) return 1;             // base case
    return n * factorial(n - 1);      // recursive step: n! in terms of (n-1)!
}

Its recurrence is immediate from the code: one multiplication and one recursive call per level, T(n) = T(n-1) + O(1), unrolling to T(n) = T(0) + n·O(1) = O(n) — linear, because each step peels off exactly one unit of n and does a constant amount of extra work.

The "subtract one" recurrence family: Fibonacci and its exponential blowup

The naive recursive translation of the Fibonacci definition (F(0)=0, F(1)=F(2)=1, F(n) = F(n-1) + F(n-2) for n > 2) looks just as direct as factorial's:

java
static long fib(int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

But counting actual recursive calls made while evaluating fib(n) tells a very different story than factorial's:

n	3	4	5	6	7
recursive calls	2	4	8	14	24

This isn't linear growth, and the reason is visible directly in the recursion tree for something as small as fib(5): computing fib(5) calls fib(4) and fib(3) — but fib(4) itself calls fib(3) again, from scratch, as one of its own two subcalls. The exact same subproblem, fib(3), gets fully recomputed in two different branches of the tree, and each of those branches recomputes fib(2) multiple times in turn. The recurrence for the number of calls is T(n) = T(n-1) + T(n-2) + O(1). Since T(n-1) and T(n-2) are close in size for large n, approximating T(n-1) ≈ T(n-2) gives T(n) ≈ 2T(n-1) + O(1) — the same "subtract one, double" shape Towers of Hanoi produces below — which unrolls (substituting repeatedly, exactly as the sibling dynamic-programming-fundamentals concept's CUT-ROD recurrence does) to T(n) = O(2^n). Concretely: fib(100) alone would need on the order of 2^100 ≈ 1.27 × 10^30 calls — at one call per nanosecond, roughly 4 × 10^13 years, thousands of times the age of the universe. (The precise, tight bound — not just this doubling approximation — is Θ(φ^n), where φ = (1+√5)/2 ≈ 1.618 is the golden ratio; φ < 2, so the true growth is somewhat slower than the 2^n approximation, but still fully exponential.)

The same "subtract one, double" shape: Towers of Hanoi

Moving n disks from one peg to another, one at a time, never placing a larger disk on a smaller one, decomposes recursively: move the top n-1 disks out of the way, move the single largest disk, then move the n-1 disks back on top of it.

java
static void hanoi(int n, char from, char to, char aux) {
    if (n == 0) return;
    hanoi(n - 1, from, aux, to);                                   // move n-1 disks out of the way
    System.out.println("Move disk " + n + " from " + from + " to " + to);
    hanoi(n - 1, aux, to, from);                                   // move them back on top
}

Each call to hanoi(n, ...) makes exactly two recursive calls on n-1, plus one constant-time disk move: T(n) = 2T(n-1) + O(1). Tracing small cases by hand confirms the doubling directly — 1, 3, 7, 15, 31 moves for n = 1..5 (each is 2× the previous +1) — and unrolling the recurrence the same way as Fibonacci's approximation above (substitute repeatedly until reaching the base case T(0)) gives T(n) = 2^n · T(0) + O(1) = O(2^n), exactly matching 2^n - 1 moves. Unlike Fibonacci's exponential blowup, though, this one is not fixable by memoization — Towers of Hanoi has no overlapping subproblems (both recursive calls at every level operate on genuinely disjoint disk arrangements), so 2^n - 1 moves is a hard lower bound on any correct solution, not naive recursion's fault.

A different recurrence shape entirely: "divide" instead of "subtract"

Sequential search over an unsorted array of size n costs T(n) = T(n-1) + O(1) in the worst case (check one element, recurse on the rest) — the same subtract-one shape as factorial, giving O(n). Binary search over a sorted array instead throws away half the remaining elements at every step: T(n) = T(n/2) + O(1). Substituting repeatedly — T(n) = T(n/2) + 1 = T(n/4) + 2 = T(n/8) + 3 = ... = T(n/2^k) + k — and stopping when n/2^k = 1, i.e. k = log_2 n, gives T(n) = T(1) + log_2 n = O(log n). The practical gap is enormous, not just asymptotic: over 1,024 elements, sequential search needs up to 1,023 comparisons in the worst case, binary search needs at most log_2 1024 = 10 — about 1% of the work — purely because dividing n shrinks it far faster than subtracting a constant from it, for the exact same "do O(1) work and recurse once" shape.

Solving a recurrence in general: three methods, one theorem

The two recurrence shapes above (T(n) = T(n-1) + f(n), T(n) = T(n/b) + f(n)) are special cases of the recurrences that arise from any divide-and-conquer or self-referential algorithm. CLRS names three general techniques for solving them, in Chapter 4 ("Divide-and-Conquer"):

• The substitution method — guess the closed-form answer, then prove it by induction, substituting the guess back into the recurrence to check the inductive step holds. Works for anything, but requires already suspecting the right answer.

• The recursion-tree method — draw the recursion as a tree (exactly the fib and hanoi trees above), sum the work done at each level, and sum across levels. This is the method actually used above to arrive at both O(2^n) results by hand.

• The master method — a direct plug-in formula for recurrences of the specific shape T(n) = a·T(n/b) + f(n) (a >= 1 subproblems, each of size n/b, plus f(n) extra work to divide/combine), comparing f(n) against n^(log_b a):

  • Case 1: if f(n) = O(n^(log_b a - ε)) for some ε > 0 (the recursive calls dominate), then T(n) = Θ(n^(log_b a)).
  • Case 2: if f(n) = Θ(n^(log_b a) · log^k n) for some k >= 0 (the two are comparable), then T(n) = Θ(n^(log_b a) · log^(k+1) n).
  • Case 3: if f(n) = Ω(n^(log_b a + ε)) for some ε > 0 and a regularity condition holds (the extra work dominates), then T(n) = Θ(f(n)).

  Mergesort's own recurrence — Sedgewick & Wayne's own running example — is the textbook Case 2 application: T(n) = 2T(n/2) + O(n) has a=2, b=2, so n^(log_2 2) = n^1 = n, and f(n) = O(n) = Θ(n^1 · log^0 n) matches Case 2 with k=0, giving T(n) = Θ(n log n) — the linearithmic bound both books state directly for mergesort, arrived at here from the general formula instead of a dedicated proof.

Why this concept sits upstream of dynamic programming

Fibonacci's T(n) = T(n-1) + T(n-2) + O(1) and rod cutting's T(n) = 1 + sum(T(j) for j=0..n-1) (the sibling dynamic-programming-fundamentals concept's own recurrence) are both exponential for the identical reason: the recursion revisits the same smaller subproblem — the same n value — from more than one place in the call tree. Nothing about the recursive definition itself needs to change to fix this; what changes is bookkeeping — caching each subproblem's answer the first time it's computed (memoization) or filling a table smallest-value-first so nothing is ever recomputed (tabulation), turning fib's O(2^n) (or, tightly, Θ(φ^n)) into O(n) by ensuring each of the n distinct subproblem sizes is solved exactly once. That fix — and the vocabulary of "overlapping subproblems" that names when it applies — is the sibling concept's subject; this concept is what makes "the recursion recomputes the same thing twice" a claim you can actually see and count, rather than take on faith.

The real cost of recursion in Java: the call stack

Every recursive call is a real stack frame, not a mathematical abstraction — parameters, local variables, and the return address all get pushed onto the JVM's call stack, and popped only when that call returns. A recursion that's correct and even reasonably efficient in Big-O terms (say, O(n)) can still fail outright in Java if n is large enough to exhaust the stack, throwing java.lang.StackOverflowError — a real, JVM-specific risk, not merely a performance concern the way a slow O(n^2) algorithm is. This matters more in Java than in languages that guarantee tail-call elimination (rewriting a self-recursive call in tail position into a loop, reusing the same stack frame): the JVM does not perform this optimization even when a Java method's recursive call is written in tail position, so a deeply recursive Java function needs either an explicit iterative rewrite or an explicit stack-based simulation to be safe on large inputs — writing "tail-recursive-looking" Java code buys none of the stack safety it would in a language whose runtime actually eliminates the tail call.

Watch it happen: naive Fibonacci recomputes the same call three times

Tracing fib(4)'s full call tree by hand — 9 calls total — makes the "same subproblem revisited from multiple places" claim concrete: fib(2) is computed twice from scratch (once under each of fib(4)'s two subcalls), and fib(1) three times, each one redoing identical work the other already did.

• The recurrence's shape, not its constant factors, decides the asymptotic outcome. T(n) = T(n-1) + O(1) is linear; T(n) = 2T(n-1) + O(1) is exponential; T(n) = T(n/2) + O(1) is logarithmic — three recurrences that differ only in how the recursive call's argument shrinks, producing three completely different complexity classes. Reading a recursive definition's recurrence off by inspection, before ever running it, is the actual skill this concept builds.
• Overlapping subproblems are a property of the recursive structure, not of the problem being hard — Fibonacci and rod cutting are both easy problems (an O(n) and O(n²) table fill, respectively, once memoized) that merely look exponential in their most direct, naive recursive translation. Towers of Hanoi's exponential cost, by contrast, is real and unavoidable — there is no memoization fix, because there is nothing overlapping to cache.
• A guaranteed-correct recursive algorithm can still fail in Java specifically, at a size no Big-O bound warns about, because StackOverflowError is a fixed physical resource limit (stack depth), not a function of asymptotic running time — an O(n) recursion can be fully practical time-wise at n = 10^7 and still crash the JVM outright, something an equivalent iterative loop over the same n would never do.
• Recognizing which of the two recurrence families you actually have is a modeling judgment call, not a mechanical step — nothing about a recursive function's syntax announces whether it's the "subtract a constant" shape or the "divide by a constant" shape; that has to be read from what the recursive call actually does to its argument, which is exactly what separates factorial/Fibonacci/Hanoi's linear-or-exponential family from binary search's logarithmic one.