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 (fib(5) alone calls fib(2) three times). The fix in real code is either memoization or a plain loop.

Memoization keeps the recursive shape but caches each result the first time it's computed, so every subproblem runs once:

public static long fibMemo(int n, long[] cache) {
  if (n < 2) return n;
  if (cache[n] != 0) return cache[n];      // already computed
  return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}
// call as: fibMemo(50, new long[51])

A plain loop drops the recursion entirely and uses constant memory:

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.

Recursion vs iteration

Any recursive method can be rewritten as a loop, and any loop can be rewritten as recursion — they are equally powerful. The choice is about clarity and cost:

• Reach for recursion when the data itself is recursive (trees, nested folders, JSON) or when the recursive definition reads more clearly than the loop, as with factorial or reverse.
• Reach for a loop when recursion would be deep enough to risk a StackOverflowError, or when an iterative version is just as readable and avoids the per-call overhead, as with fib.

When the two are equally clear, prefer the loop in Java: it has no stack-depth ceiling and no call-frame cost.

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