Java Recursion

Recursion is a technique where a method solves a problem by calling itself with a smaller version of the same problem, until it reaches a case simple enough to answer directly. In Java, recursion is a first-class way to express solutions to problems that are naturally self-similar, such as traversing trees, computing mathematical sequences, or breaking a task into identical smaller sub-tasks. Every recursive method you will ever write follows the same underlying pattern, and understanding how the Java Virtual Machine executes that pattern will help you write correct, efficient recursive code and avoid its most common pitfall.

Overview / How Recursion Works

A recursive method is simply a method that calls itself, directly or indirectly (through another method), as part of its own body. Every well-formed recursive method needs two essential parts:

  • Base case — the condition under which the method stops calling itself and returns a concrete value. Without this, the method calls itself forever.
  • Recursive case — the part where the method calls itself with an argument that is closer to the base case (usually a smaller or simpler input).

Internally, every method call in Java — recursive or not — creates a new stack frame (also called an activation record) on the thread’s call stack. This frame stores the method’s parameters, local variables, and the address to return to once the method finishes. When a method calls itself, the JVM does not somehow “merge” the calls together; it pushes a brand new, completely independent frame on top of the stack for each call. So if factorial(5) calls factorial(4), which calls factorial(3), and so on, you end up with five separate stack frames stacked on top of each other, each waiting for the call above it to return a value before it can finish its own computation and pop off the stack.

This is why recursion has a memory cost proportional to the depth of the recursion (how many calls are pending at once), not just the number of calls made overall. The JVM’s call stack has a fixed size (configurable with the -Xss flag), and if recursion goes too deep — usually because the base case is missing or unreachable — the JVM throws a StackOverflowError.

Syntax

returnType methodName(parameters) {
    if (baseCondition) {
        return baseValue;      // base case: stops the recursion
    }
    // recursive case: calls itself with a smaller/simpler argument
    return methodName(smallerParameters);
}
  • returnType — the type of value the method produces (can be void, but recursive methods most often return a value).
  • baseCondition — a check that must eventually become true as the recursive case shrinks the input; this stops the recursion.
  • baseValue — the known, direct answer for the simplest possible input (e.g. factorial(0) is 1).
  • methodName(smallerParameters) — the recursive call itself, which must move the input measurably closer to the base case.

Examples

Example 1: Factorial

The factorial of a non-negative integer n (written n!) is the product of all positive integers up to n, and 0! is defined as 1. This is a textbook recursive definition: n! = n * (n-1)!.

public class Main {
    public static void main(String[] args) {
        int number = 5;
        long result = factorial(number);
        System.out.println("Factorial of " + number + " is " + result);
    }

    static long factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
}
Output:
Factorial of 5 is 120

Here, n == 0 || n == 1 is the base case. Every recursive call passes n - 1, so the argument shrinks by exactly one on each call, guaranteeing the base case is eventually reached.

Example 2: Fibonacci Sequence

The Fibonacci sequence defines each number as the sum of the two before it, with fibonacci(0) = 0 and fibonacci(1) = 1. This example shows a method with two base cases and two recursive calls per invocation.

public class Main {
    public static void main(String[] args) {
        int count = 10;
        for (int i = 0; i < count; i++) {
            System.out.print(fibonacci(i) + " ");
        }
        System.out.println();
    }

    static int fibonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
Output:
0 1 1 2 3 5 8 13 21 34

Because fibonacci(n) calls itself twice, the number of calls grows exponentially with n — this is important, and we'll return to it in Common Mistakes.

Example 3: Tower of Hanoi (a realistic use case)

Recursion truly shines on problems that are recursive by nature. The Tower of Hanoi puzzle asks you to move a stack of disks from one peg to another, using a third peg as a helper, never placing a larger disk on a smaller one. The recursive insight: to move n disks from source to destination, move the top n-1 disks out of the way, move the largest disk directly, then move the n-1 disks onto the destination.

public class Main {
    public static void main(String[] args) {
        int numberOfDisks = 3;
        solveHanoi(numberOfDisks, 'A', 'C', 'B');
    }

    static void solveHanoi(int n, char source, char destination, char auxiliary) {
        if (n == 0) {
            return;
        }
        solveHanoi(n - 1, source, auxiliary, destination);
        System.out.println("Move disk " + n + " from " + source + " to " + destination);
        solveHanoi(n - 1, auxiliary, destination, source);
    }
}
Output:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Trying to write this iteratively with explicit stacks is possible but far less intuitive than the recursive version, which mirrors the way you would explain the algorithm to another person.

Under the Hood: Step by Step

Walking through factorial(3) shows exactly what the JVM does:

  • factorial(3) is called. A stack frame is pushed. Since 3 != 0/1, it needs factorial(2) before it can compute 3 * factorial(2).
  • factorial(2) is called. Another frame is pushed on top. It needs factorial(1).
  • factorial(1) is called. Another frame is pushed. Since n == 1, this returns 1 immediately — no further calls.
  • Control returns to factorial(2)'s frame, which computes 2 * 1 = 2 and returns 2. Its frame is popped.
  • Control returns to factorial(3)'s frame, which computes 3 * 2 = 6 and returns 6. Its frame is popped.

At the deepest point of this call, three stack frames existed simultaneously. This is why the maximum recursion depth is bounded by stack size, not heap size — deep recursion can fail even when there is plenty of free heap memory.

Common Mistakes

Mistake 1: Forgetting the base case

If a recursive method never reaches a condition that stops it, every call keeps pushing new stack frames until the stack runs out of space, throwing a StackOverflowError at runtime.

// Wrong: no base case, so this never stops calling itself
static void countDown(int n) {
    System.out.println(n);
    countDown(n - 1);
}

The fix is to add a condition that stops the recursion once the problem can no longer shrink meaningfully:

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

Mistake 2: Forgetting to return the recursive result

A subtler bug is calling the recursive method but not using (or returning) its result, which for a non-void method also fails to compile because not every path returns a value:

// Wrong: does not compile — "missing return statement"
static int factorialBroken(int n) {
    if (n == 0) {
        return 1;
    }
    n * factorialBroken(n - 1); // result is computed and discarded!
}

The corrected version explicitly returns the combined result:

static int factorialFixed(int n) {
    if (n == 0) {
        return 1;
    }
    return n * factorialFixed(n - 1);
}

Mistake 3: Ignoring exponential blowup (overlapping subproblems)

The naive fibonacci method from Example 2 recomputes the same values repeatedly — fibonacci(5) calls fibonacci(3) twice, fibonacci(2) three times, and so on. The number of calls roughly doubles with each increase in n, so fibonacci(40) alone makes well over a billion calls and becomes unusably slow. The fix is memoization: cache each result the first time it is computed so it is never recomputed.

import java.util.HashMap;
import java.util.Map;

public class Main {
    static Map memo = new HashMap<>();

    public static void main(String[] args) {
        int n = 40;
        System.out.println("Fibonacci(" + n + ") = " + fibonacciMemo(n));
    }

    static long fibonacciMemo(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        long result = fibonacciMemo(n - 1) + fibonacciMemo(n - 2);
        memo.put(n, result);
        return result;
    }
}
Output:
Fibonacci(40) = 102334155

With memoization, each value from 0 to n is computed exactly once, turning an exponential-time algorithm into a linear-time one.

Best Practices

  • Always write the base case first and make sure it is actually reachable from every recursive path.
  • Make sure every recursive call moves strictly closer to the base case (smaller number, shorter list, shallower tree, etc.).
  • Prefer recursion for problems that are naturally recursive (trees, graphs, divide-and-conquer, backtracking); prefer a loop for simple linear iteration, since it uses constant stack space.
  • Watch for overlapping subproblems — if the same input recomputes the same sub-answer many times, add memoization or switch to an iterative/dynamic-programming approach.
  • Keep an eye on recursion depth for large inputs; very deep recursion (tens of thousands of calls) risks StackOverflowError regardless of how much heap memory is available.
  • Use private static helper methods for recursion inside a class when the recursive logic is an implementation detail, not part of the public API.

Practice Exercises

  • Write a recursive method sumDigits(int n) that returns the sum of the digits of a positive integer (e.g. sumDigits(1234) should return 10).
  • Write a recursive method power(int base, int exponent) that computes base raised to exponent without using Math.pow.
  • Write a recursive method isPalindrome(String s) that returns true if a string reads the same forwards and backwards, by comparing the first and last characters and recursing on the substring in between.

Summary

  • A recursive method calls itself with a smaller version of the same problem until it reaches a base case.
  • Every method call — including a recursive one — pushes a new stack frame; deeply nested recursion uses proportionally more stack memory.
  • Missing or unreachable base cases cause infinite recursion and a StackOverflowError.
  • Recursive methods must return (and use) the result of their recursive call to produce a correct answer.
  • Naive recursion can recompute the same subproblem many times; memoization or an iterative rewrite fixes the resulting exponential slowdown.
  • Recursion is most valuable for problems that are naturally self-similar, like tree traversal, divide-and-conquer, and puzzles like the Tower of Hanoi.