Java Recursion

Recursion is when a method calls itself. It's a natural way to express problems whose structure repeats at a smaller scale — counting down, walking a tree, computing a factorial, reversing a string.

Every recursive method has two parts: a base case that returns directly without recursing, and a recursive case that calls the method on a smaller piece of the problem. Get either part wrong and the program either gives a wrong answer or runs forever (until the JVM blows the stack).

A first example: factorial

The factorial of n is n × (n-1) × (n-2) × … × 1. By definition, 0! = 1. That definition is itself recursive: n! = n × (n-1)!.

The Java translation maps directly:

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

Calling factorial(4) produces:

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

Each call sits on the stack waiting for the next one to return. When factorial(0) finally returns 1, the answers ripple back up the chain.

The base case is non-negotiable

Without a base case, the method has nothing to stop the recursion. The classic mistake:

public static int factorial(int n) {
  return n * factorial(n - 1);    // no base case
}

This recurses forever — well, until the call stack runs out and the JVM throws StackOverflowError. The base case is what ends the chain; the recursive case is what advances toward it.

The other classic mistake is a base case the recursion never reaches:

public static int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n + 1);    // wrong direction
}

factorial(4) here would try factorial(5), factorial(6), … and crash. The recursive call must move the argument closer to the base case.

Recursion on integers: countdown

A trivial second example for clarity — print the numbers from n down to 1:

public static void countdown(int n) {
  if (n <= 0) return;             // base case
  System.out.println(n);
  countdown(n - 1);                // recursive case
}

countdown(3) prints 3, 2, 1. Swap the order to print 1, 2, 3:

public static void countup(int n) {
  if (n <= 0) return;
  countup(n - 1);                  // recurse first, print after
  System.out.println(n);
}

Same recursion, different print order — because the recursive call happens before the print. The lesson: what you do before the recursive call runs on the way down, what you do after runs on the way back up.

Recursion on strings: reverse

You can think of reversing a string as "take the first character off, reverse the rest, stick the first character on the end":

public static String reverse(String s) {
  if (s.length() <= 1) return s;            // base case
  return reverse(s.substring(1)) + s.charAt(0);
}

reverse("cat") → reverse("at") + 'c' → reverse("t") + 'a' + 'c' → "t" + 'a' + 'c' → "tac".

This is elegant but inefficient — every recursive call allocates a new substring. A StringBuilder loop would be faster. Recursion is often the clearest expression of an idea; it's not always the fastest implementation.

Fibonacci and the cost of recursion

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, …, defined as fib(n) = fib(n-1) + fib(n-2). The direct translation:

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

This is correct but exponentially slow — fib(40) already runs noticeably, fib(50) is painful. The recursion tree recomputes the same subproblems billions of times. The fix in real code is either memoization (cache results) or a plain loop:

public static long fibLoop(int n) {
  long a = 0, b = 1;
  for (int i = 0; i < n; i++) {
    long next = a + b;
    a = b;
    b = next;
  }
  return a;
}

Knowing when recursion is the wrong tool is as important as knowing when it's the right one.

StackOverflowError

Each pending call uses a chunk of the JVM stack. With the default stack size, you can usually nest a few thousand calls before things break:

factorial(100000);    // StackOverflowError

Java does not do tail-call optimization — even a recursive call that's the last thing the method does still consumes a stack frame. If the problem can require very deep recursion, switch to a loop or use an explicit Deque as your own stack.

A worked example

What's next

You've defined methods, passed parameters, overloaded names, and recursed. The next concept is scope — which parts of a method can see which variables, and what happens when a name appears in more than one place. Read on in the variable scope chapter.

Practice