Recursion

The idea

A recursive method solves a problem by calling itself on a smaller version of the same problem, until the problem is small enough to answer directly.

static int factorial(int n) {
    if (n <= 1) return 1;             // base case
    return n * factorial(n - 1);      // recursive case
}

factorial(4) cannot answer immediately, so it asks for factorial(3), which asks for factorial(2), and so on. Once factorial(1) returns 1, the answers multiply back up the chain.

Every recursive method needs both parts:

The third is the one people forget. A base case is useless if the recursive call does not actually move toward it.

Tracing it

Working a small case by hand is the fastest way to build intuition. For factorial(4):

factorial(4) = 4 * factorial(3)
             = 4 * (3 * factorial(2))
             = 4 * (3 * (2 * factorial(1)))
             = 4 * (3 * (2 * 1))
             = 24

Notice the multiplications happen on the way back up. Nothing is computed until the base case is reached — the calls stack up first, then resolve in reverse.

The call stack

Each call gets its own copy of the parameters and local variables, stored in a stack frame. That is why n is different in each call even though they share a name.

factorial(1)   <- top, returns first
factorial(2)
factorial(3)
factorial(4)   <- bottom, returns last

This is a literal stack — the same last-in-first-out structure — which is why running out of space is a StackOverflowError.

Exception in thread "main" java.lang.StackOverflowError

public static void main(String[] args) {
    new Thread(null, Main::solve, "main", 1 << 26).start();   // 64 MB stack
}

Recursion versus iteration

Anything recursive can be written as a loop, and vice versa. The question is which is clearer.

// iterative — better here
static int factorialLoop(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

For factorial, the loop is simpler and uses no stack. Recursion earns its place when the problem itself branches.

A case where recursion is clearly better

Summing a tree with a loop requires managing your own stack. Recursively it is three lines:

static int sum(TreeNode node) {
    if (node == null) return 0;                       // base case
    return node.value + sum(node.left) + sum(node.right);
}

Two recursive calls, and the structure handles the bookkeeping. Most tree and graph work looks like this — see Tree Traversals and Depth-First Search.

Watch out for accidental exponential work

Some innocent-looking recursion does enormous amounts of repeated work:

static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

This is correct but recomputes the same values constantly — fib(40) makes over a billion calls. The fix is to remember results you have already computed, covered in Memoization and Dynamic Programming.

Correct and fast are separate questions. Recursion makes it easy to write something correct that is unusably slow.

Helper methods

Often the natural recursion needs extra parameters the caller should not supply. Use a wrapper:

static int countMatches(int[] values, int target) {
    return countFrom(values, target, 0);       // caller-friendly
}

private static int countFrom(int[] values, int target, int index) {
    if (index == values.length) return 0;
    int here = (values[index] == target) ? 1 : 0;
    return here + countFrom(values, target, index + 1);
}

The public method has a clean signature; the private one carries the position. This pattern appears constantly.

Next

Related