Recursion in Java

Definition

Recursion is a method calling itself, directly or through another method, to solve a smaller instance of the same problem.

The two required parts

• A base case that returns without recursing.
• A recursive case that moves strictly closer to the base case.

Remove either one and the method never terminates.

Example

public static long factorial(int n) {
    if (n < 0) {
        throw new IllegalArgumentException("n must not be negative");
    }
    if (n <= 1) {
        return 1;              // base case
    }
    return n * factorial(n - 1);   // recursive case
}

How it works on the call stack

Every call gets its own stack frame holding its parameters and locals. Frames stack up until the base case returns, and then unwind.

factorial(4)
  -> 4 * factorial(3)
       -> 3 * factorial(2)
            -> 2 * factorial(1)
                 -> 1            base case reached
            <- 2
       <- 6
  <- 24

Each pending call occupies memory. Recursion depth is therefore bounded by the stack, and exceeding it throws StackOverflowError, which is an Error and not something to catch and continue from.

A more natural fit

Factorial is easier as a loop. Recursion earns its place when the data itself is recursive, such as a directory tree or a binary tree.

record Node(int value, Node left, Node right) { }

public static int sum(Node node) {
    if (node == null) {
        return 0;
    }
    return node.value() + sum(node.left()) + sum(node.right());
}

Writing that with an explicit stack is possible but considerably longer, and the recursive version matches the shape of the data.

Recursion compared with iteration

Tail recursion

public static long factorialTail(int n, long accumulated) {
    if (n <= 1) {
        return accumulated;
    }
    return factorialTail(n - 1, n * accumulated);   // nothing left to do after the call
}

In some languages the compiler rewrites such a call as a loop. Java does not guarantee tail call optimisation, so this version still consumes one frame per call. Do not rely on it for deep recursion in Java.

Overlapping subproblems and memoisation

// Exponential: fib(40) recomputes the same values millions of times
public static long fibSlow(int n) {
    return n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2);
}

// Linear: each value is computed once and remembered
public static long fib(int n, Map<Integer, Long> cache) {
    if (n < 2) {
        return n;
    }
    return cache.computeIfAbsent(n, key -> fib(key - 1, cache) + fib(key - 2, cache));
}

The recursion did not change; only the repeated work did. Recognising overlapping subproblems is the step from plain recursion towards dynamic programming.

Common mistakes

• No base case, or a base case that the recursive step can step over.
• Recursing on the same value, so the problem never shrinks.
• Assuming Java optimises tail calls.
• Using recursion on a long list, where the depth grows with the input size.
• Catching StackOverflowError and carrying on. The stack is already unreliable at that point.

Best practices

• Write the base case first, then the recursive case.
• Validate arguments once in a public method and recurse in a private helper, so the check is not repeated at every level.
• Prefer iteration for linear data and recursion for branching data.
• Cache results when subproblems repeat.

Practice

1. Write a recursive method that reverses a String, then rewrite it iteratively and compare.
2. What is printed by factorial(0), and which branch handles it?
3. Find the defect: int f(int n) { return n == 0 ? 0 : f(n) - 1; }
4. Write a recursive method that counts the files in a directory tree, taking the folder as a parameter.
5. Explain why fibSlow(45) is slow even though the code is short.

Conclusion

Recursion is the natural way to walk recursive data. Guarantee that every call shrinks the problem, remember that Java charges you a stack frame for each one, and cache when the same subproblem appears twice.