Java Recursion

A method can call other methods, and it can also call itself. This is called recursion. It is a natural way to solve problems that contain smaller copies of themselves: the factorial of 5 is 5 times the factorial of 4, a folder contains smaller folders, a sorted list can be built from two smaller sorted lists.

Base case and recursive step

Every recursive method needs two parts:

• a base case that is answered directly, without calling itself, and
• a recursive step that calls the method with a smaller problem, getting closer to the base case.

public class Main {
    static int sumUpTo(int n) {
        if (n == 0) {
            return 0;                  // base case
        }
        return n + sumUpTo(n - 1);     // recursive step
    }

    public static void main(String[] args) {
        System.out.println(sumUpTo(5));
        System.out.println(sumUpTo(100));
    }
}

15
5050

sumUpTo(5) becomes 5 + sumUpTo(4), which becomes 4 + sumUpTo(3), and so on down to sumUpTo(0), which returns 0. Then all the additions are done on the way back: 0 + 1 + 2 + 3 + 4 + 5 = 15.

Factorial

The factorial of n (written n!) is 1 × 2 × ... × n. Factorials grow very quickly, so the method uses long:

public class Main {
    static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        for (int i = 1; i <= 10; i++) {
            System.out.println(i + "! = " + factorial(i));
        }
        System.out.println("20! = " + factorial(20));
    }
}

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
20! = 2432902008176640000

Recursion with text

Recursion works on strings too. To reverse a word, take its last character and put the reverse of the rest after it:

public class Main {
    static String reverse(String s) {
        if (s.length() <= 1) {
            return s;
        }
        return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));
    }

    public static void main(String[] args) {
        System.out.println(reverse("recursion"));
        System.out.println(reverse("a"));
    }
}

noisrucer
a

When recursion goes wrong

If the base case is missing or never reached, the method calls itself again and again. Each call uses a little memory on the call stack, and eventually Java stops with a StackOverflowError:

public class Main {
    static int depth = 0;

    static void forever() {
        depth++;
        forever();
    }

    public static void main(String[] args) {
        try {
            forever();
        } catch (StackOverflowError e) {
            System.out.println("Stack overflow after many calls: " + (depth > 1000));
        }
    }
}

Stack overflow after many calls: true

The try and catch here catch the error so the program can print a message; you will learn them in Exceptions. Some problems are also slow when written recursively, such as the naive Fibonacci method that computes the same values many times. A loop is often simpler and faster; choose recursion when it makes the solution much clearer.

Practice exercises

1. Write a recursive method power(int base, int exp) that computes base to the power exp.
2. Write a recursive method that counts the digits of a positive number (n / 10 removes the last digit).
3. Write a recursive Fibonacci method and print the first 15 Fibonacci numbers.