How Does Recursion Work in Java?

Recursion is a method that calls itself with a smaller or simpler version of the same problem, until the problem is trivial enough to answer directly. Two ingredients are mandatory. The base case is the condition under which the method returns an answer without calling itself again; without it the recursion never terminates. The recursive case is the branch that makes the call, and it must move the problem towards the base case — otherwise you have infinite recursion and a StackOverflowError.

Mechanically, each call pushes a frame onto the call stack holding that invocation's parameters and locals. When the base case is reached, the frames unwind, each one combining its partial result with the value returned from the frame below it. So recursion has a cost: one stack frame per level, which is the trade-off you pay for not needing an explicit collection to hold intermediate state.

The JVM does not perform tail-call optimisation. A method whose last statement is a recursive call still consumes a stack frame per call, so writing recursion in tail position does not save you from stack overflow. That is a genuine difference from functional languages such as Scala, and it is worth stating because it is the standard reason to convert a deep recursion into a loop.

Recursion is the right tool when the problem has a naturally recursive structure — traversing a tree, walking a directory, flattening a nested list, evaluating an expression — because the code mirrors the shape of the data. It is the wrong tool for linear tasks such as summing a list, where a loop is simpler and uses constant stack depth.

Factorial is the textbook example because it maps almost one-to-one onto the definition: n factorial is n multiplied by the factorial of n minus one, with the base case at zero or one.

public class Main {
    public static void main(String[] args) {
        for (int n = 0; n <= 5; n++) {
            System.out.println(n + "! = " + factorial(n));
        }
    }

    static long factorial(int n) {
        if (n <= 1) {                     // base case: stop recursing
            return 1;
        }
        return n * factorial(n - 1);        // recursive case: shrink the problem
    }
}

Reading the code outward from the bottom of the call stack makes the mechanism obvious. The call factorial(5) pushes a frame and calls factorial(4), which pushes a frame and calls factorial(3), and so on until factorial(1) hits the base case and returns 1. That 1 propagates back up: factorial(2) computes two times one and returns 2, factorial(3) returns 6, and finally factorial(5) returns 120.

Two implementation details are worth mentioning. The base case is written as n <= 1 rather than n == 0 so that negative input also terminates instead of recursing downwards forever. And the return type is long rather than int, because 13 factorial already overflows an int; if you must handle arbitrary input, a BigInteger is the correct choice, since the recursive shape is identical.

One warning about the shape of the code: the multiplication happens after the recursive call returns, so this is not tail recursion and each level keeps its own frame. For a five-element input that is irrelevant. For a hundred thousand elements it is not.

You stop the recursion from growing the stack, usually by converting it into a loop. There are two shapes worth knowing. The first is an explicit accumulator, where you thread a running total through the recursive calls as an argument instead of holding it in a local variable; because there is nothing left to do after the call returns, the compiler can reuse a single stack frame. The second is an explicit stack, where you keep the pending work in a collection that you push and pop yourself. That is the right answer for branching data such as a tree or a graph.

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> data = new ArrayList<>();
        for (int i = 1; i <= 5000; i++) {
            data.add(i);
        }

        System.out.println("recursive sum : " + recursiveSum(data, 0));
        System.out.println("iterative sum : " + iterativeSum(data));
    }

    // One stack frame per element: deep enough to matter for big inputs.
    static int recursiveSum(List<Integer> values, int index) {
        if (index == values.size()) {
            return 0;
        }
        return values.get(index) + recursiveSum(values, index + 1);
    }

    // Constant stack depth, no matter how large the list is.
    static int iterativeSum(List<Integer> values) {
        int total = 0;
        for (int value : values) {
            total += value;
        }
        return total;
    }
}

Both produce the same total, 12502500, but the recursive version holds one live frame for every element it is processing, while the loop version needs exactly one frame no matter how large the list grows. Push the list to a hundred thousand elements and the gap stops being theoretical: the recursive version exhausts the stack and throws StackOverflowError, the loop version is unaffected.

One more option is worth knowing. For a long chain of simple tail calls you can restructure the method into a loop directly, since the JVM will not do it for you. Virtual threads give each thread a much larger stack, which raises the ceiling — but it does not make an unbounded recursion terminate, so the algorithmic fix is still the right answer.