How Does Recursion Work in Java and When Is It Worth It?

Recursion means solving a problem by calling the same method again with a smaller version of that problem, until you reach a base case that answers it without calling anybody. Every recursive method is those two halves: a stopping condition, and a step that moves towards it.

What makes a recursive method work?

A recursive method has two parts. The base case returns an answer straight away. The recursive case calls the same method with an input that is closer to the base case, and combines that result with its own work. Without a base case the calls never stop.

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

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

The output is:

5! = 120
10! = 3628800

The call to factorial(10) is answered by nine more calls, each with a smaller number, and the base case stops the chain at 1. Notice that the multiplication happens on the way back, not on the way in, which is the part that usually confuses people the first time they see it.

How does the call stack grow and unwind?

Each call pushes a frame onto the call stack holding that call's parameters and its place to return to. The frames pile up until the base case is hit, and then they unwind one by one as the returns travel back up.

public class RecursiveCountdown {
    static void countDown(int n) {
        if (n <= 0) {
            System.out.println("liftoff");
            return;
        }
        System.out.println(n);
        countDown(n - 1);
    }

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

The output shows the way down and then the base case firing:

3
2
1
liftoff

Nothing is printed on the way back because this method returns nothing. A method that returns a value does its combining step during that unwinding, which is exactly why a recursive method can build a result from nothing but smaller results.

Why does naive Fibonacci recursion repeat so much work?

A recursive solution that computes the same sub-problem again and again looks efficient and is not. The instrumented version below counts how many times the method is entered.

import java.util.HashMap;
import java.util.Map;

public class FibonacciCompare {
    static final Map<Long, Long> CACHE = new HashMap<>();
    static int naiveCalls = 0;
    static int cachedCalls = 0;

    static long fibNaive(int n) {
        naiveCalls++;
        if (n < 2) {
            return n;
        }
        return fibNaive(n - 1) + fibNaive(n - 2);
    }

    static long fibCached(int n) {
        cachedCalls++;
        if (n < 2) {
            return n;
        }
        Long known = CACHE.get((long) n);
        if (known != null) {
            return known;
        }
        long value = fibCached(n - 1) + fibCached(n - 2);
        CACHE.put((long) n, value);
        return value;
    }

    public static void main(String[] args) {
        System.out.println("fib(20) = " + fibNaive(20));
        System.out.println("naive calls = " + naiveCalls);
        System.out.println("fib(20) with a cache = " + fibCached(20));
        System.out.println("cached calls = " + cachedCalls);
    }
}

Both versions return the same answer, but the work is wildly different:

fib(20) = 6765
naive calls = 21891
fib(20) with a cache = 6765
cached calls = 39

Those counts were measured by the program itself, not estimated. The naive version recomputes the same values over and over, so its call count climbs much faster than the number you asked for. The cached version remembers each result it has already computed, so almost every call is either a first visit or a cheap lookup. Whenever a recursive method keeps recalculating the same thing, a map or a set of results fixes it.

What other shapes does recursion fit?

Recursion suits anything built out of smaller copies of itself. Splitting a number into its last digit and its remaining digits is one example.

public class SumDigits {
    static int digitSum(int n) {
        if (n == 0) {
            return 0;
        }
        return n % 10 + digitSum(n / 10);
    }

    public static void main(String[] args) {
        System.out.println("digit sum of 90210 = " + digitSum(90210));
    }
}

The output is digit sum of 90210 = 12, because the method takes the last digit with the remainder operator and recurses on the number with that digit removed. A search over a sorted array is another good fit, since each step throws away half of what is left.

public class RecursiveBinarySearch {
    static int indexOf(int[] sorted, int target, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = low + (high - low) / 2;
        if (sorted[mid] == target) {
            return mid;
        }
        if (sorted[mid] < target) {
            return indexOf(sorted, target, mid + 1, high);
        }
        return indexOf(sorted, target, low, mid - 1);
    }

    public static void main(String[] args) {
        int[] data = {2, 5, 8, 12, 16, 23, 38, 56};
        System.out.println("23 sits at index " + indexOf(data, 23, 0, data.length - 1));
        System.out.println("99 sits at index " + indexOf(data, 99, 0, data.length - 1));
    }
}

The output shows the index of the value that was found and minus one for the value that was not:

23 sits at index 5
99 sits at index -1

The low and high parameters carry the shrinking range, and the base case low > high means the range has collapsed to nothing.

How deep can a recursion go?

Every level of recursion holds a frame on the call stack, and the stack has a limited size set when the program starts. Push too many frames and the program fails with a stack overflow error rather than a wrong answer.

public class RecursionDepth {
    static int depth = 0;

    static void descend(int limit) {
        depth++;
        if (depth < limit) {
            descend(limit);
        }
    }

    public static void main(String[] args) {
        descend(1000);
        System.out.println("recursed " + depth + " levels deep");
    }
}

The output is recursed 1000 levels deep. A thousand frames is comfortable; a million is not, and it fails with a stack overflow error instead of finishing. Two things follow from that. Keep the depth proportional to the size of the input, and never let a recursive method depend on a value that shrinks very slowly, because the depth grows with the input and the stack is finite.

Recursion or a loop?

Many of the classic recursive examples, such as factorial and the naive Fibonacci, are shorter as loops and clearer as loops. Recursion earns its place when the problem itself is defined in terms of smaller versions of itself.

Remember this

• Every recursive method needs a base case that returns without calling itself.
• The recursive case must move towards the base case, or the calls never end.
• Calls pile up on the stack and unwind on the way back, which is where the combining happens.
• If the same sub-problem is solved more than once, cache the result.
• Stack depth grows with the size of the input, so keep the reduction per step large.
• Use a loop when the problem is a flat repetition, and recursion when the data is shaped like a tree.

Try it yourself: write a recursive method that adds up the digits of a number, then a recursive method that counts how many digits a number has, and check them against each other for a few values. Next, add a counter to the Fibonacci method and watch the call count grow as you raise the input from 10 to 20, then add a cache and watch it shrink. Finally, write a recursive method that would recurse forever if the base case were missing, and confirm that you get a stack overflow error rather than a wrong answer.