Recursion · Java Methods in Java | Java

A Method that Calls Itself

Recursion is when a method calls itself to solve a smaller version of the same problem. Every recursive method needs a base case that stops the calls.

Example

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

    static int fibonacci(int n) {
        if (n < 2) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    static int sumDigits(int n) {
        if (n == 0) return 0;
        return n % 10 + sumDigits(n / 10);
    }

    public static void main(String[] args) {
        System.out.println("5! = " + factorial(5));
        for (int i = 0; i < 10; i++) System.out.print(fibonacci(i) + " ");
        System.out.println();
        System.out.println("Digit sum of 4096 = " + sumDigits(4096));
    }
}

Output

5! = 120
0 1 1 2 3 5 8 13 21 34 
Digit sum of 4096 = 19

How the Calls Stack Up

factorial(4)
   = 4 * factorial(3)
          = 3 * factorial(2)
                 = 2 * factorial(1)
                        = 1            <- base case, start returning
                 = 2 * 1 = 2
          = 3 * 2 = 6
   = 4 * 6 = 24

Example

Without a base case the calls never stop and the program crashes with StackOverflowError.

public class Main {
    static int countDown(int n) {
        return countDown(n - 1);   // no base case!
    }

    public static void main(String[] args) {
        countDown(10);
    }
}

Output

Exception: java.lang.StackOverflowError

Practice

Exercise: Write a recursive method power(int base, int exp) that returns base^exp.

Show answer

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