Recursion in Java

A recursive method calls itself on a smaller version of the same problem. Every recursion needs a base case (when to stop) and a recursive case (how to reduce the problem).

Classic: factorial

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

factorial(5);                         // 120

Tree traversal — recursion's home turf

public static int depth(Node node) {
    if (node == null) return 0;
    int left  = depth(node.left);
    int right = depth(node.right);
    return 1 + Math.max(left, right);
}

Fibonacci — and why naive recursion hurts

public static long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);    // exponential calls — O(2ⁿ)
}

// Memoised — O(n)
public static long fibFast(int n, long[] cache) {
    if (n <= 1) return n;
    if (cache[n] != 0) return cache[n];
    return cache[n] = fibFast(n - 1, cache) + fibFast(n - 2, cache);
}

Stack overflow

Each call adds a frame to the thread's stack. The JVM default is typically 512 KB — roughly 5 000 to 50 000 frames depending on locals. Very deep recursion (e.g. a linked list with a million nodes) blows up with StackOverflowError.

Java doesn't optimise tail calls

// Tail call — the recursive call is the last thing we do
public static int sum(int n, int acc) {
    if (n == 0) return acc;
    return sum(n - 1, acc + n);     // still adds a stack frame in Java
}

Scala, Kotlin and Clojure optimise tail calls. The JVM doesn't, and Java the language doesn't either. For deep iteration, convert to a loop:

public static int sumIter(int n) {
    int acc = 0;
    for (int i = 1; i <= n; i++) acc += i;
    return acc;
}

Common mistakes

• Missing base case — infinite recursion → StackOverflowError.
• Base case that never triggers — n - 1 with a double parameter never equals zero exactly.
• Exponential branching without memoisation — Fibonacci, unweighted graph search without visited set.
• Choosing recursion for iteration — a simple for uses a single frame; deep recursion uses one per level.

Related

Pillar: Java methods. See also for loop.