Java Recursion

›Short versionOpen if you only have a minute.

A recursive method calls itself on a smaller input and combines the result with the work at this level.
A base case returns without another call. Every chain of calls has to reach one.
Each call has its own stack frame. Locals at one level do not overwrite the caller’s locals.
Work after the recursive call runs on the way back up, so the outer frame stays live.
Java does not reuse a frame for a tail call. Depth still costs stack.
Use recursion when the data is nested and the depth stays bounded. Use a loop when the data is a flat sequence.

A folder contains files and more folders. Counting the files with a single index assumes the entries sit in one row. They do not. Each folder asks the same question of its children, and the children may ask it again.

is that question written as a method. The method handles one folder, and it calls itself for each folder inside. The call stack holds the folders you have entered and not yet finished. The same shape solves nested expressions and trees. It is the wrong shape for a countdown.

A stop, and a smaller call

factorial(0) is the . It returns 1 and does not call factorial again. Every positive n calls factorial(n - 1). The argument shrinks, so the chain reaches 0. The multiplication sits after the call, so this level’s contribution happens once the smaller factorial is known.

Factorial.java

public class Factorial {
    static int factorial(int n) {
        if (n == 0) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(3));
    }
}

Terminal

$ javac Factorial.java
$ java Factorial
6

Without the base case, or with a call that passes n unchanged, the chain does not shorten. Each call still does real work in the sense that it pushes a frame. The thread runs out of stack. A base case that exists in the source and is never reached, because the test is n == -1 while n stays non-negative, fails the same way.

Two methods can recurse together: isEven calls isOdd, and isOdd calls isEven, each on a smaller number, with zero as the stop. Mutual recursion is still recursion. Both methods need a path that stops, and the arguments still have to shrink toward it.

What the frames hold

factorial(3) pushes a with n equal to 3, then waits inside the multiplication. The next frame has n equal to 2. Then 1. Then 0, which returns 1 and pushes nothing further. The frame for 1 multiplies 1 * 1 and returns 1. The frame for 2 multiplies 2 * 1. The frame for 3 multiplies 3 * 2 and returns 6. Those three values of n exist at the same time, in three frames. They are not one variable being overwritten.

Terminal

factorial(3)  waits on 3 * factorial(2)
  factorial(2)  waits on 2 * factorial(1)
    factorial(1)  waits on 1 * factorial(0)
      factorial(0)  returns 1
    factorial(1)  returns 1
  factorial(2)  returns 2
factorial(3)  returns 6

The work after the recursive call is why the outer frames cannot disappear yet. If the method only returned the inner call, with no multiplication left, a language that reuses frames could treat it as a . Java does not make that promise. HotSpot still allocates a frame for the inner call. Writing return factorial(n - 1); saves no stack. A chain of a few thousand such calls, the exact ceiling depending on frame size and the thread’s -Xss setting, throws .

That error is not a signal to catch and continue. The stack is exhausted, so the remaining frames are in a bad state for ordinary recovery. Shrink the problem, bound the depth, or stop using recursion for that input. A missing base case is a bug. A base case that is correct for a tree of depth ten thousand can still be the wrong tool on a default stack.

When a loop is the method you wanted

factorial is a clear picture of frames, and a poor production habit. int overflows long before the stack does, and the computation is a running product. One frame and a loop keep that product in a local. The result for small n matches. The stack stays constant.

java

static int factorialLoop(int n) {
    int product = 1;
    for (int i = 1; i <= n; i++) {
        product *= i;
    }
    return product;
}

Recursion is the wrong tool when the data is a sequence and the next step is “the next element.” Summing an array, counting to zero, and scanning a long linked list are loops. Each would compile as recursion, and each would spend a frame per element for no structure you needed to remember on the way back down. If the work after the recursive call is empty, a loop usually states the same process.

Recursion fits when the data is nested and the call depth stays well under the stack you actually have. A directory walker, an expression tree, and a divide-and-conquer sort on a balanced split are that shape. The method does one node, then the calls do the children. On the way back it combines counts, products, or sorted halves. You could build an explicit stack and write the same walk as a loop. Recursion is that stack, maintained by the JVM, with the base case as the empty-stack condition. Choose it when that reading is the one you want to maintain, and when a hostile or merely large input cannot push the depth into StackOverflowError.

factorial is rewritten so the recursive call is the last action: the method updates a parameter and returns factorial of the smaller value, with no multiplication after the call. For a large n, does the JVM reuse one frame?

No. That form is a tail call, and the JVM does not promise to reuse the caller’s frame. HotSpot still pushes a frame per call. A large enough n throws StackOverflowError. A loop keeps a single frame and updates one local. Recursion remains appropriate when the nesting is real and the depth is bounded, not because the call sits in tail position.