Recursion patterns

Linear recursion makes at most one recursive call per invocation. The call tree is a single chain: factorial, sum of digits, reversing an array. For n levels it makes n calls and uses O(n) stack.

Many linear recursions are really loops in disguise, and the iterative version needs no stack.

1static int sum(int[] a, int i) {
2    if (i == a.length) return 0;       // base case
3    return a[i] + sum(a, i + 1);       // exactly one recursive call
4}

Binary recursion makes two recursive calls. The call tree is a binary tree, and the number of calls depends on how the problem shrinks: Fibonacci shrinks by 1 and 2 (exponential calls), merge sort halves (O(n) calls), and Tower of Hanoi shrinks by 1 twice (2^n - 1 moves).

In the animation each disk move is one visit of the middle step: move n - 1 disks away, move the biggest, move n - 1 disks back on top. The call count doubles with each extra disk, which is why 64 disks would take about 1.8 × 10^19 moves.

1static void hanoi(int n, char from, char to, char via) {
2    if (n == 0) return;
3    hanoi(n - 1, from, via, to);                    // park the n-1 smaller disks on 'via'
4    System.out.println("Move disk " + n + ": " + from + " -> " + to);
5    hanoi(n - 1, via, to, from);                    // bring them onto the big disk
6}

Multiple branching makes several recursive calls in a loop: generating permutations, subsets, or all paths through a grid. The tree has many children per node, and its size is bounded by the branching factor raised to the depth.

This is the structure of backtracking (Chapter 20). The recursion tree for permutations of n items has n! leaves.

1static void permutations(int[] a, int k, List<int[]> out) {
2    if (k == a.length) { out.add(a.clone()); return; }     // one complete arrangement
3    for (int i = k; i < a.length; i++) {                   // up to n - k branches
4        swap(a, k, i);
5        permutations(a, k + 1, out);
6        swap(a, k, i);                                     // undo, so the next branch starts clean
7    }
8}

In head recursion the recursive call comes first and the work is done afterwards, on the return path. In tail recursion the work comes first and the recursive call is the last action. The two print in opposite orders.

Tail recursion can be turned into a loop mechanically, which is what some compilers do. Head recursion usually needs a stack, explicit or implicit, because work is still pending when the call is made.

1static void countDown(int n) {      // work before the call
2    if (n == 0) return;
3    System.out.print(n + " ");
4    countDown(n - 1);               // prints 3 2 1
5}
6
7static void countUp(int n) {        // work after the call
8    if (n == 0) return;
9    countUp(n - 1);
10    System.out.print(n + " ");      // prints 1 2 3
11}

In mutual recursion two or more methods call each other. Each call moves toward the base case, but through the other method. Typical uses are parsers (an expression contains a term, which contains an expression in parentheses) and state machines.

The same termination rules apply: every cycle of calls must shrink the input.

1static boolean isEven(int n) { return n == 0 ? true  : isOdd(n - 1); }
2static boolean isOdd(int n)  { return n == 0 ? false : isEven(n - 1); }
3// isEven(3) -> isOdd(2) -> isEven(1) -> isOdd(0) -> false

A recursion can return a value that is combined on the way back (sum, max, count), or return nothing and act through side effects (printing, filling a list, swapping array elements).

Return values keep the state local to each call and are easier to reason about. Side effects need careful handling of shared state: if a recursive call changes a list or array, every later call sees the change, so undo it (backtracking) or copy it.