Recursion

⚠ Optional chapter.

A Method That Calls Itself

Recursion is when a method calls itself — another form of repetition, alongside loops (Ch.5). Without care, this goes wrong immediately:

public static void neverEnd()
{
    System.out.println("This never stops!");
    neverEnd(); // calls itself again, forever
}

This is infinite recursion — it eventually crashes with StackOverflowError, since a program can only recurse so deep before running out of space to track all those in-progress calls.

Every well-behaved recursive method needs at least one base case (a condition that stops the recursion and returns directly, no further self-call) and at least one recursive call (that moves the problem closer to the base case). The classic example, factorial:

public static int factorial(int n)
{
    if (n == 0)         // base case — the smallest input this method answers directly
    {
        return 1;
    }
    else
    {
        return n * factorial(n - 1); // recursive call — moves toward the base case
    }
}

Every recursive call should shrink the problem: factorial's call passes n - 1, one step closer to the n == 0 base case that eventually stops the recursion.

Tracing: The Call Stack

Each recursive call gets pushed onto the call stack with its own independent copy of local variables and parameters — exactly like the method-call mechanics from Ch.4/17.2, just calling the same method repeatedly. Tracing factorial(3):

factorial(3) returns 3 * factorial(2)
factorial(2) returns 2 * factorial(1)
factorial(1) returns 1 * factorial(0)
factorial(0) returns 1

Then substituting values back upward from the base case:

factorial(1) returns 1 * factorial(0) = 1 * 1 = 1
factorial(2) returns 2 * factorial(1) = 2 * 1 = 2
factorial(3) returns 3 * factorial(2) = 3 * 2 = 6

factorial(3) returns 6.

Why Bother? Loops for Trees

Any loop can, in principle, be rewritten recursively, and vice versa — so why use recursion at all? It shines on branching structures (computer scientists call these "trees") rather than simple linear ones. A useful mental model: a for loop for a linear structure like an array (Ch.9), nested loops for a 2D array (Ch.10), and recursion for something that branches — like calculating the total number of subsystems nested inside an equipment group that can itself contain further nested groups, where each nested group is the same problem, just smaller. A for loop naturally handles "walk through this flat list"; it struggles to naturally express "walk through this, and every branch inside it, and every branch inside those."

Common Pitfalls

Forgetting the base case entirely. Without one, every recursive method is really just neverEnd() in disguise — infinite recursion and a crash.
A recursive call that doesn't actually shrink the problem. If the argument passed to the next call doesn't move closer to the base case, the recursion never terminates, even with a base case defined.
Confusing "recursion is elegant here" with "recursion is required here." Simple linear traversal (an array, a String) is usually clearer and more efficient as a loop — recursion earns its keep on genuinely branching structures.

Key Takeaways

Recursion is a method calling itself — repetition, like a loop, but structured around self-calls instead of a loop construct.
Every correct recursive method needs a base case (stops the recursion) and a recursive call that moves toward it.
Each recursive call gets its own independent local variables/parameters, tracked via the call stack — tracing means writing out each call, then substituting values back up from the base case.
Recursion is most valuable for branching ("tree") structures — a simple for loop remains the better tool for flat, linear ones.

Derived from csawesome-2026: unit-4-data-collections/4.16-recursion.md (CSA 4.16)