Algorithms and Data Structures · Chapter 6

Recursion and Backtracking

You already know recursion from the basics: a method calls itself. In this chapter you see what happens in memory, when recursion fits better than a loop, and how backtracking systematically tries out all possibilities: arrangements, subsets, paths through a maze.

Base case and recursive case

Every recursive method has two parts:

The base case is so small that the result is known right away: a number with one digit, a text with at most one character, an empty array.
The recursive case reduces the problem to a smaller version of the same problem and calls the method itself for it.

You always check the base case first. With arrays, the problem gets smaller by moving an index along (index + 1), with texts by substring(1), with numbers by n - 1 or n / 10.

1public class Main {2    public static int countDigits(int n) {3        if (n < 10) {4            return 1;5        }6        return 1 + countDigits(n / 10);7    }8
9    public static String reverse(String s) {10        if (s.length() <= 1) {11            return s;12        }13        return reverse(s.substring(1)) + s.charAt(0);14    }15
16    public static void main(String[] args) {17        System.out.println(countDigits(7));18        System.out.println(countDigits(2026));19        System.out.println(reverse("stack"));20    }21}

The call stack

Every method call gets its own area on the call stack with its own parameters and local variables. When factorial(4) calls itself, four calls end up on top of each other, each with its own n. Only when the top one is done does the one below continue.

It follows that whatever comes before the recursive call runs in the order of the calls, whatever comes after it runs in reverse order. The indentation in the example shows how deep the stack currently is.

1public class Main {2    public static int factorial(int n, String indent) {3        System.out.println(indent + "factorial(" + n + ") called");4        int result;5        if (n <= 1) {6            result = 1;7        } else {8            result = n * factorial(n - 1, indent + "  ");9        }10        System.out.println(indent + "factorial(" + n + ") returns " + result);11        return result;12    }13
14    public static void main(String[] args) {15        factorial(4, "");16    }17}

The stack is limited. A few thousand calls on top of each other work fine, millions do not: then Java stops with a StackOverflowError.

Recursion or loop?

Anything a loop can do, recursion can do too, and vice versa. Both sums in the example need O(n) steps. The recursive version, however, also needs O(n) space on the stack, the loop only one variable.

Rule of thumb:

Loop when you simply go through an array or a list from front to back.
Recursion when the problem naturally splits into subproblems of the same kind: Towers of Hanoi, trees (next chapter), quicksort and merge sort, and all tasks where you try out possibilities.

1public class Main {2    public static int sumRecursive(int[] numbers, int index) {3        if (index == numbers.length) {4            return 0;5        }6        return numbers[index] + sumRecursive(numbers, index + 1);7    }8
9    public static int sumLoop(int[] numbers) {10        int total = 0;11        for (int number : numbers) {12            total += number;13        }14        return total;15    }16
17    public static void main(String[] args) {18        int[] numbers = {4, 8, 15, 16, 23, 42};19        System.out.println(sumRecursive(numbers, 0));20        System.out.println(sumLoop(numbers));21    }22}

Backtracking: choose, explore, undo

Backtracking builds a solution step by step. At each point there are several possibilities. For each of them, the same pattern applies:

Choose: fix one possibility, for example append a letter and mark it as used.
Explore: solve the next step recursively.
Undo: reverse the choice so that the next possibility starts from a clean state.

When the solution is complete (all letters placed, exit reached), it is printed, counted or stored. If a partial solution no longer fits (queen threatened, wall in the way), you abandon this branch right away. That is exactly what makes backtracking faster than blindly trying all combinations.

1public class Main {2    static int found = 0;3
4    public static void permute(char[] letters, boolean[] used, StringBuilder current) {5        if (current.length() == letters.length) {6            System.out.println(current);7            found++;8            return;9        }10        for (int i = 0; i < letters.length; i++) {11            if (used[i]) {12                continue;13            }14            used[i] = true;                          // choose15            current.append(letters[i]);16            permute(letters, used, current);         // explore17            current.deleteCharAt(current.length() - 1);18            used[i] = false;                         // undo19        }20    }21
22    public static void main(String[] args) {23        char[] letters = {'a', 'b', 'c'};24        permute(letters, new boolean[letters.length], new StringBuilder());25        System.out.println(found + " permutations");26    }27}

Running time: quickly exponential

Recursive solutions that call themselves twice per call grow fast. The Towers of Hanoi need 2ⁿ − 1 moves for n disks, so O(2ⁿ). Every extra disk doubles the work.

The same goes for backtracking: there are 2ⁿ subsets and n! arrangements of n elements. For n = 20 that is more than a million subsets and more than 2 quintillion arrangements. Such algorithms are only suitable for small n. Abandoning a branch as soon as it no longer fits helps a lot, but often does not change the order of magnitude in the worst case.

1public class Main {2    static long moves = 0;3
4    public static void move(int n, char from, char to, char via) {5        if (n == 0) {6            return;7        }8        move(n - 1, from, via, to);9        moves++;10        move(n - 1, via, to, from);11    }12
13    public static void main(String[] args) {14        for (int n = 1; n <= 20; n += 4) {15            moves = 0;16            move(n, 'A', 'C', 'B');17            System.out.println(n + " disks: " + moves + " moves");18        }19    }20}

Common mistakes

Missing or wrong base case
Without a base case, the method calls itself endlessly until a StackOverflowError comes. A wrong base case is just as tricky: if (n <= 1) return n; gives 0 instead of 1 for factorial(0). Check the base case with the smallest inputs, including 0 and the empty array.
The problem does not get smaller
sumFrom(numbers, index) instead of sumFrom(numbers, index + 1) always calls itself with the same value and never reaches the base case. Every recursive call has to get closer to the base case. With n - 2 instead of n - 1 it can also be skipped: n == 0 never matches an odd number, n <= 0 does.
Forgetting to undo
In backtracking, every choice has to be reversed after exploring: remove the letter again, set used[i] back to false, set the maze cell back to '.'. Otherwise the next possibility starts with leftovers from the previous one. And if you store a partial solution, store a copy (new ArrayList<>(current)), because the list itself is about to change again.