Java Recursion

Some problems are naturally made of smaller copies of themselves. A folder contains folders, which contain more folders. The factorial of 5 is 5 times the factorial of 4. Java recursion lets a method solve a problem like this by calling itself on a smaller piece. In this lesson, you'll learn the two parts every recursive method needs, watch the call stack grow and shrink, write classic examples like factorial and Fibonacci, and learn when a plain loop is the better choice.

What is recursion in Java?

Recursion is a technique where a method calls itself. A method that does this is called a recursive method. Every correct recursive method has two parts:

• A base case: a simple situation where the method returns an answer directly, without calling itself. This is what stops the recursion.
• A recursive case: the method calls itself with a smaller or simpler input, moving one step closer to the base case.

Here's a rocket launch countdown written recursively:

public class Launch {
    public static void main(String[] args) {
        countdown(5);
    }

    public static void countdown(int seconds) {
        if (seconds == 0) {                 // base case
            System.out.println("Liftoff!");
            return;
        }
        System.out.println(seconds + "...");
        countdown(seconds - 1);             // recursive case: a smaller problem
    }
}

5...
4...
3...
2...
1...
Liftoff!

Each call prints one number and hands the rest of the countdown to a new call with one second less. When seconds reaches 0, the base case prints "Liftoff!" and the calls stop.

How does recursion work? The call stack

As you learned in Java variable scope, every method call gets its own stack frame with its own parameters and local variables. Recursion is no different: each call to the same method gets a separate frame, with its own copy of n. Let's use the classic example, the factorial. The factorial of n, written n!, is n × (n-1) × ... × 1. So 4! = 4 × 3 × 2 × 1 = 24. Notice that 4! = 4 × 3!: a smaller copy of the same problem.

public class Factorial {
    public static void main(String[] args) {
        System.out.println("4! = " + factorial(4));
        System.out.println("10! = " + factorial(10));
    }

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

4! = 24
10! = 3628800

There are two phases:

1. Winding: factorial(4) can't finish until it knows factorial(3), which waits for factorial(2), which waits for factorial(1). Four frames now sit on the stack.
2. Unwinding: factorial(1) returns 1. Then factorial(2) returns 2 × 1 = 2, factorial(3) returns 3 × 2 = 6, and finally factorial(4) returns 4 × 6 = 24.

We used long as the return type because factorials grow very fast; 13! is already too big for an int.

How do you write a recursive method?

Ask yourself three questions:

1. What's the simplest version of the problem? That's your base case (for example, a number with one digit, an empty string, n == 0).
2. How can I make the problem a bit smaller? (Remove one digit, one character, subtract 1.)
3. If I trust the method to solve the smaller problem, how do I use that answer?

Let's apply this to adding up the digits of a number, like 4096 → 4 + 0 + 9 + 6 = 19. The simplest case is a single digit (less than 10): its sum is itself. To make the problem smaller, chop off the last digit with / 10; the last digit itself is % 10.

public class DigitSum {
    public static void main(String[] args) {
        System.out.println(sumDigits(4096));
        System.out.println(sumDigits(7));
        System.out.println(sumDigits(123456789));
    }

    public static int sumDigits(int number) {
        if (number < 10) {                                // base case: one digit
            return number;
        }
        return number % 10 + sumDigits(number / 10);      // last digit + sum of the rest
    }
}

19
7
45

The same recipe works for text. A word is a palindrome if it reads the same backwards, like "level". An empty or one-letter string is always a palindrome (base case). Otherwise, the first and last letters must match, and the middle must be a palindrome too:

public class Palindrome {
    public static void main(String[] args) {
        System.out.println(isPalindrome("level"));
        System.out.println(isPalindrome("racecar"));
        System.out.println(isPalindrome("rocket"));
    }

    public static boolean isPalindrome(String word) {
        if (word.length() <= 1) {
            return true;
        }
        if (word.charAt(0) != word.charAt(word.length() - 1)) {
            return false;
        }
        return isPalindrome(word.substring(1, word.length() - 1));
    }
}

true
true
false

Fibonacci with recursion (and why it's slow)

The Fibonacci sequence starts 0, 1, and each next number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13... The definition is itself recursive: fib(n) = fib(n-1) + fib(n-2), with fib(0) = 0 and fib(1) = 1 as base cases. It translates almost word for word into Java:

public class Fibonacci {
    public static void main(String[] args) {
        for (int n = 0; n <= 10; n++) {
            System.out.print(fib(n) + " ");
        }
        System.out.println();
    }

    public static long fib(int n) {
        if (n <= 1) {
            return n;                        // fib(0) = 0, fib(1) = 1
        }
        return fib(n - 1) + fib(n - 2);
    }
}

0 1 1 2 3 5 8 13 21 34 55 

It looks elegant, but there's a hidden problem. Each call makes two more calls, and the same values get recalculated again and again: fib(5) computes fib(3) twice, fib(2) three times, and so on. Let's count the calls with a counter stored in a field (a variable outside the methods, which you met briefly in the scope lesson):

public class FibonacciCalls {
    static long calls = 0;

    public static void main(String[] args) {
        int[] tests = {10, 20, 30};
        for (int n : tests) {
            calls = 0;
            long result = fib(n);
            System.out.println("fib(" + n + ") = " + result + " took " + calls + " calls");
        }
    }

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

fib(10) = 55 took 177 calls
fib(20) = 6765 took 21891 calls
fib(30) = 832040 took 2692537 calls

Almost 2.7 million calls for fib(30)! The number of calls roughly doubles each time n grows, so fib(50) would need about 40 billion calls. A simple loop that remembers the last two values needs only n steps:

public class FibonacciLoop {
    public static void main(String[] args) {
        System.out.println(fib(50));
    }

    public static long fib(int n) {
        long previous = 0;
        long current = 1;
        if (n == 0) {
            return 0;
        }
        for (int i = 2; i <= n; i++) {
            long next = previous + current;
            previous = current;
            current = next;
        }
        return current;
    }
}

12586269025

This prints instantly. The lesson: a recursive solution can be correct but very slow if it repeats work.

What causes a StackOverflowError?

The call stack has a limited size. If a recursive method never reaches its base case, it keeps pushing frames until the stack is full, and Java stops the program with a StackOverflowError. Here's a countdown with the base case forgotten:

public static void countdown(int n) {
    System.out.println(n);
    countdown(n - 1);    // no base case: never stops
}

It prints thousands of numbers (3, 2, 1, 0, -1, -2...) and then crashes with:

Exception in thread "main" java.lang.StackOverflowError

The same thing happens if the base case exists but can't be reached. For example, if (n == 0) with a recursive call on n - 2 never stops for an odd starting number, because n jumps from 1 to -1 and skips 0. A safer base case is if (n <= 0).

Recursion vs loops: which should you use?

Anything you can do with recursion, you can also do with a loop (and vice versa). The choice is about clarity and cost:

Common mistakes with recursion

1. No base case

Without one, the method calls itself forever until the stack overflows.

2. A base case that's never reached

Check that the input actually moves toward the base case. countdown(n + 1) instead of countdown(n - 1) heads the wrong way.

3. Forgetting to return the recursive result

public static long factorial(int n) {
    if (n <= 1) {
        return 1;
    }
    factorial(n - 1);      // result thrown away
    return n;              // wrong answer
}

The recursive call's result must be used: return n * factorial(n - 1);.

4. Using recursion where it repeats work

Like the naive Fibonacci, some recursive designs recalculate the same answers over and over. If a recursive method is mysteriously slow, count the calls.

Practice exercise

public class Power {
    public static void main(String[] args) {
        System.out.println(power(2, 10));
        System.out.println(power(5, 3));
        System.out.println(power(7, 0));
    }

    public static long power(int base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        return base * power(base, exponent - 1);
    }
}

1024
125
1

What's next?

You've written your own calculations, from tips to factorials. Java also ships with a ready-made toolbox for math: square roots, powers, rounding and more. Explore it in the Java Math class.