Recursion mechanics

The base case is the input for which the answer is known directly, with no further recursive call. Without it the method calls itself forever.

Choose the smallest input that is still meaningful: n == 0 for factorial, an empty or one-element range for array problems, null for linked structures. A recursion can have several base cases, such as fib(0) and fib(1).

1static long factorial(int n) {
2    if (n == 0) return 1;              // base case: 0! is 1 by definition
3    return n * factorial(n - 1);       // recursive case
4}

The recursive case reduces the problem and trusts the recursive call to solve the smaller version. You do not need to follow every call in your head: assume factorial(n - 1) works, and then check that n * factorial(n - 1) is correct for n.

That trust is justified by induction: if the base case is correct and each call is correct whenever its smaller calls are, the whole method is correct.

Each call gets its own frame on the call stack, holding its parameters, local variables and the place to return to. A new call pushes a frame, and a return pops it.

The animation shows factorial(4). Watch the stack grow as each call waits for the next, and shrink as the answers come back. The recursion tree on top is the same story drawn as a picture: each box is one call, and its value appears when it returns.

1static long factorial(int n) {
2    if (n == 0) return 1;              // base case
3    return n * factorial(n - 1);       // recursive case
4}

Work can happen on the way down (before the recursive call), on the way back up (after it returns), or both. In n * factorial(n - 1) the multiplication happens on the return path: no multiplication is done until the base case has returned 1.

Step through the animation after the base case. Each frame resumes, multiplies by its own n, and returns to its caller. That return path is where the answer is actually assembled.

A stack frame stores the method's parameters, local variables, and the return address. Because each frame has its own copy of the variables, recursive calls do not overwrite each other: the n in factorial(3) and the n in factorial(2) are different variables.

Frames take memory, typically tens to a few hundred bytes each. The JVM thread stack is limited (often 512 KB to 1 MB by default, settable with -Xss), which is why very deep recursion fails. Objects live on the heap, not in the frame; the frame holds only references to them.

A recursion terminates if every call moves strictly closer to a base case. Name the quantity that shrinks: n decreases by 1, the range hi - lo halves, the list gets shorter. If you cannot name one, the recursion may loop forever.

Check two things: the base case is reachable from every valid input, and the recursive call makes progress. factorial(n) with a negative n never reaches n == 0 because it keeps subtracting. Guard against it or use n <= 0 for the base case with an input check.

An invariant is a fact that holds at the start of every call. Stating it is the best way to prove a recursion correct. For recursive binary search the invariant is: "if the target is in the array, it is in arr[lo..hi]". Each call keeps it true while shrinking the range.

For reverse(a, lo, hi): "everything outside lo..hi is already in its final place". Each call fixes two more elements and the invariant still holds for the smaller range.

A call is a tail call when it is the very last thing the method does and its result is returned unchanged. gcd(b, a % b) is a tail call. n * factorial(n - 1) is not, because the multiplication still has to happen afterwards.

Some languages reuse the current frame for a tail call, so the recursion uses no extra stack. The JVM does not do this. A tail-recursive Java method still uses one frame per call, so convert it to a loop when the depth could be large (see lesson 5.07).

1// not a tail call: the multiplication waits for the result
2static long fact(int n) { return n == 0 ? 1 : n * fact(n - 1); }
3
4// tail call with an accumulator: nothing is left to do after the call
5static long factTail(int n, long acc) { return n == 0 ? acc : factTail(n - 1, acc * n); }