Recursion in Java

Stand between two mirrors and you see a smaller copy of yourself, inside a smaller copy, inside another. Recursion is that idea in code: a method that solves a problem by calling itself on a smaller version of the same problem, until the problem is so small that the answer is obvious. It sounds circular, but with one rule, a base case that stops the calls, it's a clean way to solve many problems.

Factorial, Recursively

The factorial of 4 is 4 × 3 × 2 × 1. Notice that 4! is just 4 × 3!, and 3! is 3 × 2!, and so on, down to 1! = 1:

public class Factorial {
    static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
 
    public static void main(String[] args) {
        System.out.println("4! = " + factorial(4));
        System.out.println("15! = " + factorial(15));
    }
}

4! = 24
15! = 1307674368000

How it works

1. Lines 3 to 5 are the base case: for n <= 1, the answer is 1. No more calls.
2. Line 6 is the recursive case: n! is n times the factorial of a smaller number, n - 1.
3. Every call moves closer to the base case, so the calls eventually stop.

The Call Stack

Each call gets its own frame on the call stack (see "JVM Architecture Overview"), with its own n. The calls stack up until the base case returns, then unwind, each one multiplying by its own n:

Another Example: Sum of Digits

public class DigitSum {
    static int digitSum(int n) {
        if (n < 10) {
            return n;
        }
        return n % 10 + digitSum(n / 10);
    }
 
    public static void main(String[] args) {
        System.out.println(digitSum(40721));
    }
}

14

The last digit plus the digit sum of the rest: 1 + digitSum(4072), and so on, until a single digit is left.

Try it yourself: write power(base, exp), where power(2, 10) is 2 * power(2, 9). What is the base case?

When Recursion Goes Wrong

Without a base case, or with a call that doesn't get smaller, the calls never stop. Each call adds a frame until the stack is full, and Java throws StackOverflowError (the lesson "JVM Architecture Overview" shows this happening at around 44,000 calls).

Common Mistakes

No base case, or one that can be skipped. Make it cover every way the input can end, such as n <= 1, not just n == 1.

Doing too much work again. Naive recursive Fibonacci recomputes the same values many times; the next lesson shows why that's slow.

Very deep recursion. Thousands of nested calls can overflow the stack even when correct. A loop is safer for long chains.

Interview Corner

Practice

1. Easy: Write static int sumTo(int n) that returns 1 + 2 + ... + n recursively.
2. Harder: Write static boolean isPalindrome(String s) recursively: compare the first and last characters, then check the middle with s.substring(1, s.length() - 1).

Key Takeaways