Recursion

The two ingredients: base case and recursive case

Every correct recursive function has exactly two parts. The base case is the smallest version of the problem, the one you can answer instantly without any more work. The recursive case is everything else: it does a little bit of work, then hands a smaller version of the problem back to the same function.

Take factorial. The factorial of n (written n!) is n times (n-1) times (n-2) all the way down to 1. Notice the pattern hiding inside: n! is just n times (n-1)!. That is a smaller copy of the same problem. And when n reaches 1, the answer is simply 1, no more shrinking needed. That is the base case.

If you forget the base case, the function never stops calling itself and your program crashes with a StackOverflowError. Rule number one of recursion: write the base case first.

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

The call stack: where the magic actually lives

So who remembers all those unfinished multiplications? The call stack does. The call stack is a region of memory where the program keeps one frame per active function call. Each frame stores that call's local variables and where to resume when the call returns.

When factorial(3) runs, it cannot finish until factorial(2) returns, so its frame waits on the stack. factorial(2) likewise waits on factorial(1). The frames pile up: factorial(3) on the bottom, factorial(2) above it, factorial(1) on top. Then factorial(1) hits the base case and returns 1. Its frame pops off. factorial(2) wakes up, computes 2 * 1 = 2, and returns. factorial(3) wakes up, computes 3 * 2 = 6, and returns the final answer.

This is why deep recursion uses memory: n stacked frames means O(n) space, even though you never created an array. It is also why recursion depth has a limit. The stack is finite, and Java will throw StackOverflowError if you blow past it (typically around ten thousand frames).

Tracing by hand: your best debugging tool

Beginners often try to mentally simulate every frame of a big recursion and get lost. Do not. Instead, trace a tiny input on paper and then trust the pattern.

Here is the trace for sum(3), a function that adds the numbers 1 through n. Calls going down: sum(3) asks for sum(2), which asks for sum(1), which returns 1 immediately. Returns coming back up: sum(2) computes 2 + 1 = 3, then sum(3) computes 3 + 3 = 6. Two directions, every time: the descent breaks the problem apart, the ascent assembles the answer.

There is also a mindset called the recursive leap of faith: when writing the recursive case, assume the smaller call already works. If sum(n - 1) correctly sums 1 through n-1, then n + sum(n - 1) is obviously correct for n. You verify the base case, verify one step, and induction does the rest. Exactly like a mathematical proof.

static int sum(int n) {
    if (n == 1) {
        return 1;
    }
    return n + sum(n - 1);
}

Recursion vs iteration: when to use which

Anything recursion can do, a loop plus an explicit stack can also do, and vice versa. The sum example above is honestly better as a loop: a for loop from 1 to n uses O(1) memory instead of O(n) stack frames and cannot overflow. When the problem is a straight line (do step 1, then step 2, then step 3) iteration wins.

Recursion shines when the problem branches. A file system folder contains files and more folders; a binary tree node has two subtrees; a maze cell has several neighbors. Writing that with loops means managing your own stack by hand, while recursion gives you that bookkeeping for free and the code reads like the problem's own definition.

So the practical rule: linear problems, prefer loops; self-similar or branching problems, prefer recursion. You now have the single most important building block in this section. Backtracking, tree traversals, and dynamic programming are all recursion wearing different outfits, and they are up next.

Frequently asked