Recursion: base case, call stack and divide and conquer

← Back to the section

Recursion is when a method calls itself. At first glance that looks like a bug — won't the program loop forever? — but it is one of the most elegant techniques in programming: some tasks split into recursive steps so naturally that any other solution looks clumsy. Under the hood recursion leans on the call stack, which we have already met.

The idea: reduce the task to a simpler one

Take the factorial: 5! = 5 × 4 × 3 × 2 × 1 = 120. The key observation is that the factorial is defined through itself: 5! = 5 × 4!, and 4! = 4 × 3!, and so on. So the task "compute n!" can be reduced to the simpler task "compute (n−1)!" and a multiplication by n.

int factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // step toward a simpler task
}

The whole skeleton of recursion is visible here. The method calls itself with a smaller argument, the task gets simpler every time, and once it becomes trivial the stop kicks in.

The base case — what stops the recursion

If a method called itself with no way out, it would do that forever, until the program crashed. That is why every recursive method has a base case — simple enough that the answer is known right away, without another call. For the factorial it is n ≤ 1 → 1. Every call inches toward it (the argument shrinks) and sooner or later hits it — then the chain starts unwinding back.

A good analogy is a relay race. You are asked to compute 5!, but all you can do is multiply 5 by 4! — so you pass the task on. And so on, down to the person who answers immediately: "1! = 1". From that moment answers run back along the chain, each multiplied on the way — and 120 reaches you.

What happens on the call stack

While the chain goes deeper, every unfinished call has to be stored somewhere — with its arguments and the point to return control to. The language uses the call stack for this: each call pushes a frame (arguments + return address), each return pops one. That is why factorial(5) at some moment keeps five nested calls alive at once, and the deepest one (n = 1) is the first to hand back a result.

You can see it by asking the method to report on itself: the indent shows the depth of the stack.

live example

class Factorial {
    static int depth = 0;

    static int factorial(int n) {
        System.out.println("  ".repeat(depth++) + "called factorial(" + n + ")");
        int result = (n <= 1) ? 1 : n * factorial(n - 1);
        System.out.println("  ".repeat(--depth) + "returned " + result);
        return result;
    }

    public static void main(String[] args) {
        factorial(4);
    }
}

The staircase going right is the descent, the staircase coming back is the unwinding of the stack.

Two limits follow. First, every call costs time to make and memory for the frame. Second, deep enough recursion overflows the stack (the famous stack overflow error). So recursion is used for clarity of the solution, not for speed — almost any recursion can be rewritten as a loop (sometimes with a stack of your own), and that version runs faster, even if it reads worse.

Three signs of a recursive method

To sum up. A method is recursive if:

1. it calls itself;
2. that call solves a simpler version of the same task (a smaller argument, a smaller range);
3. there is a base case simple enough to solve without recursion.

No point 3 — the recursion is infinite. No point 2 — the task never converges to the base case.

Recursion and mathematical induction

Recursion is the programming twin of mathematical induction: a way to define something "through itself". The factorial is defined inductively in two lines: f(1) = 1 and f(n) = n · f(n−1). That looks like a vicious circle, but with a base case it is perfectly legitimate: the base gives a foothold, the step reduces the complex to the simple.

Where recursion really fits

Recursion shines where a task naturally splits into subtasks of the same kind.

Towers of Hanoi. The puzzle: move a stack of disks from one peg to another, never putting a larger disk on a smaller one. The recursive solution is almost comically short: to move n disks, move the top n−1 to the spare peg, move the largest one to the target, then move those same n−1 on top of it. Every step is the same task, one size smaller — with a loop it is far more painful.

Merge sort. One of the first genuinely fast sorts and a vivid example of divide and conquer: the array is split in half, each half is sorted recursively, and then the two ordered pieces are merged into one in a linear pass. Splitting gives log N levels, merging costs N per level, so the total is O(N·log N) — fundamentally faster than the O(N²) of simple sorts. The price is extra memory for the merge. The same "split in half" idea is behind recursive binary search.

Recursion will serve us again when traversing trees and graphs — there it is especially natural.

How it works in Java

You don't need to write the merge sort we just walked through — it is already in the standard library. But you do have to choose between the variants, and for that it helps to know what actually gets called.

Collections.sort(list), list.sort(comparator) and Arrays.sort(Object[]) are all the same algorithm, TimSort: an improved merge sort. It first looks for stretches of the input that already run up or down, and only then merges them pairwise. On partially ordered data — a list topped up with new rows, a slightly changed query result — it approaches O(N); in the worst case it gives honest O(N·log N), and it is stable: elements with equal keys keep their original relative order. The price is the same as for a plain merge — a temporary array up to half the length of the original.

For primitives something else is called. Arrays.sort(int[]) is not a merge sort but a quicksort with two pivots and a guard against unlucky inputs: it sorts in place, but it is not stable. For primitives stability isn't even observable (two equal fives are indistinguishable), so the substitution is harmless — just remember that one name, Arrays.sort, hides two algorithms with different memory behaviour.

TimSort has one pitfall, and it is a nasty one: it relies on the comparator being correct. The most common way to break it is comparison by subtraction, (a, b) -> a.getValue() - b.getValue(): on large values the subtraction overflows, the sign comes out reversed, the ordering stops being consistent, and the sort fails with IllegalArgumentException: Comparison method violates its general contract!. It doesn't fail every time — only when there is enough data and it lands badly — so the error likes to show up on large volumes, not on a small check. The overflow is visible on just two numbers:

live example

class CompareTrap {
    public static void main(String[] args) {
        int a = 2_000_000_000, b = -2_000_000_000;
        System.out.println("a really is greater than b: " + (a > b));
        System.out.println("wrong way, a - b: " + (a - b));
        System.out.println("right way, Integer.compare: " + Integer.compare(a, b));
    }
}

The difference came out negative even though a is larger: the subtraction ran out of the int range. That is why a comparator uses a ready-made comparison — Comparator.comparingInt(Item::getValue).

The second thing worth knowing is about the call stack itself. Its size per thread is limited (around a megabyte by default, set with the -Xss option), and deep recursion hits that limit with a StackOverflowError. The JVM does not turn tail recursion into a loop — unlike some other languages — so "recursion over a million elements" does not work in Java even where it looks harmless. When such recursion is rewritten as a loop, the explicit stack is built on ArrayDeque (a circular array, push and pop amortized O(1)) rather than on Stack: the latter wraps a synchronized Vector from the earliest versions of Java, and new code doesn't use it.

In short

• Recursion is a method calling itself, reducing the task to a simpler version of the same task.
• A base case is mandatory — a simple variant with a ready answer; it stops the recursion, after which results unwind back along the chain.
• Unfinished calls live on the call stack; hence the time and memory overhead and the risk of overflowing it.
• Recursion is used for clarity, not speed: it can usually be rewritten as a loop that runs faster but reads worse.
• It is irreplaceable in divide-and-conquer tasks — merge sort O(N·log N), the Towers of Hanoi, traversing trees and graphs.

What to read next

• Advanced sorting — quicksort and Shell sort: the same divide and conquer, but without a temporary array.
• Binary trees — traversal, where recursion turns out to be the shortest solution.
• Backtracking — recursion that tries an option and rolls it back.
• Dynamic programming — what to do when recursion computes the same thing over and over.