Recursion

A method that calls itself. The exam tests tracing it by hand far more often than writing it.

By the end of this chapter you can

Identify the base case and the recursive case
Trace a recursive call by hand and produce its output
Explain why a missing base case causes StackOverflowError
Recognise recursion over arrays and strings

Recursion questions on the exam are almost always tracing questions: here is a recursive method, what does f(4) return? Writing recursion is a smaller part of the mark than reading it, so this chapter emphasises the reading.

Every recursive method has exactly two parts:

a base case that returns without recursing, and
a recursive case that calls itself on a smaller input.

Miss either and it never terminates.

Tracing, with the calls made visible

Factorial, printing every call and return

public class Main {
    static int indent = 0;

    static int factorial(int n) {
        System.out.println("  ".repeat(indent) + "factorial(" + n + ") called");
        indent++;

        int result;
        if (n <= 1) {
            result = 1;                          // base case
        } else {
            result = n * factorial(n - 1);       // recursive case
        }

        indent--;
        System.out.println("  ".repeat(indent) + "factorial(" + n + ") returns " + result);
        return result;
    }

    public static void main(String[] args) {
        factorial(4);
    }
}

The shape of that output is the thing to internalise. The calls go all the way down to the base case before any of them return, and then the returns unwind back up. Nothing is multiplied until the bottom is reached.

That is why a trace question is answered from the bottom up: find the base case value first, then work outwards.

The base case is not optional

What a missing base case does

public class Main {
    static int broken(int n) {
        return n + broken(n - 1);     // nothing stops it
    }

    public static void main(String[] args) {
        System.out.println("about to recurse without a base case…");
        System.out.println(broken(5));
    }
}

That is asserted to throw, and it does: StackOverflowError. Each call needs a stack frame holding its parameters and its place in the code, and the stack is finite. A few thousand frames deep, it runs out.

Note that broken(5) does eventually reach negative numbers and keeps going — the condition that would stop it simply does not exist. A base case that exists but is never reached fails the same way:

static int alsoBroken(int n) {
    if (n == 0) return 0;
    return alsoBroken(n - 2);      // from an odd n, steps straight past 0
}

Starting from an odd number this skips zero forever. The base case must be reachable from every legal input, not merely present.

Recursion over an array

The pattern: do something with one element, recurse on the rest.

Sum and reverse, recursively

public class Main {
    static int sum(int[] a, int i) {
        if (i >= a.length) return 0;          // past the end: nothing left
        return a[i] + sum(a, i + 1);          // this one, plus the rest
    }

    static String reverse(String s) {
        if (s.length() <= 1) return s;                        // base case
        return reverse(s.substring(1)) + s.charAt(0);         // rest, then first
    }

    public static void main(String[] args) {
        System.out.println(sum(new int[]{3, 1, 4, 1, 5}, 0));
        System.out.println(reverse("recursion"));
        System.out.println(reverse(""));       // base case: empty stays empty
    }
}

An index parameter is how an array recursion shrinks — the array itself does not get smaller, so something else must.

Binary search, recursively

The same algorithm as chapter 4.4, expressed as recursion — and the exam shows it both ways:

Binary search as recursion

public class Main {
    static int search(int[] a, int target, int lo, int hi) {
        if (lo > hi) return -1;                       // base: window is empty
        int mid = (lo + hi) / 2;
        if (a[mid] == target) return mid;             // base: found it
        if (a[mid] < target) return search(a, target, mid + 1, hi);
        return search(a, target, lo, mid - 1);
    }

    public static void main(String[] args) {
        int[] sorted = {1, 3, 5, 7, 9, 11, 13};
        System.out.println("11 -> " + search(sorted, 11, 0, sorted.length - 1));
        System.out.println("4  -> " + search(sorted, 4, 0, sorted.length - 1));
    }
}

Two base cases here, which is normal: one for success and one for exhausting the search space. The “smaller input” is the shrinking lo–hi window.

Tracing quickly

For an exam trace, work bottom-up:

Find the base case and its value.
Substitute upward, one level at a time.
Write each level down. Do not hold four levels in your head.

For factorial(4):

factorial(1) = 1
factorial(2) = 2 × 1 = 2
factorial(3) = 3 × 2 = 6
factorial(4) = 4 × 6 = 24

Four lines, no mental stack, and it is very hard to get wrong.