Anything that, in happening,
causes itself to happen again,
happens again.
— Douglas Adams, Mostly Harmless
Computer programming is the art of solving complex problems by dividing them into smaller pieces that can be solved more easily. In the previous chapter we saw how iteration splits computations into long chains of steps, each of which incrementally builds on the steps that come before it. But not all problems lend themselves to simple iterative solutions. In this chapter we will discuss an alternative approach
known as divide-and-conquer, which organizes the steps of an algorithm hierarchically instead of linearly.
The idea behind the divide-and-conquer method is simple: Instead of trying to solve the problem directly, we first divide it into multiple simpler parts, solve those parts individually, and then combine these results into the solution of the original problem. In many cases, the
subdivision step can be repeated: We split a problem into sub-problems, each of which can be split into sub-sub-problems, and so on, until we get something that is so simple that is can be solved without further subdivision. In contrast to the sequence of computational steps used by iterative algorithms,
this approach produces a hierarchy of computational steps.
To illustrate this approach, let’s start with the problem of finding the smallest element in a list of \(n\) integers. There is an obvious iterative solution for this problem: loop over the list while keeping track of the smallest element found so far:
public static int minIterative(int[] array) {
int smallest = Integer.MAX_VALUE;
for (int element : array)
smallest = Math.min(smallest, element);
return smallest;
}
We start by initializing smallest to MAX_VALUE, which is the largest number that can be stored in an int, and then iterate over all elements of array. In each iteration, we update smallest if it is larger than the
current element and leave it unchanged otherwise. At the end of the loop, smallest contains the smallest element of array or MAX_VALUE if the array is empty.
While a plain loop is arguably the simplest way to solve the problem, we can also find the smallest element using divide-and-conquer. The idea behind all divide-and-conquer algorithms is to split a problem into multiple smaller problems, solve those sub-problems individually, and then combine the partial
results to find the solution of the original problem.
The divide-and-conquer algorithm for finding the smallest number in an array works as follows. First, we split the numbers into two parts. For instance, if the original array is (8, 5, 1, 2, 4, 9, 0), we split this list in the middle into a left half (8, 5, 1, 2) and a right half (4, 9, 0).
We can now search for the smallest element in these two smaller arrays, which gives us 1 for left half and 0 in the right half. The smallest element of the whole list must the smaller of these two partial results, namely 0.
The beauty of the divide-and-conquer method is that it can often be applied repeatedly to divide the original problem into a hierarchy of smaller and smaller sub-problems. To find the smallest number in each of the two halves, for instance, we can split them again to obtain four lists of numbers
and splitting once more gives us six additional elementary lists.
The entire process can be visualized as a tree with the original problem forming the tree’s root and the sub-problems its nodes, as shown in the left part of Fig. 3.1.
Figure 3.1 The smallest element in a list can be found using divide-and-conquer. The divide phase (left) repeatedly splits the list in half until only individual elements are left; it constructs a tree from the top down. The conquer phase walks
the tree from the leaves upwards, repeatedly propagating the smaller of two numbers to its parent node. The number at the root of the tree is the minimum of all numbers.
The right part of the figure illustrates how, after subdividing the original array, we can now find its smallest element by walking upwards in the tree, from the leaves to its root. First, we compare adjacent leaves and move the smaller number to their common ancestor in the tree; this gives us the
number 5 for the first pair of leaves, 1 for the second, and 4 for the third. We then compare adjacent numbers in the previous layer of the tree, which gives us 1 for the left half of the tree and 0 for the right. One final comparison then gives us the minimum of the original
list, which is 0.
You can think of a divide-and-conquer algorithm as proceeding in two phases: the divide phase builds the tree from the top down by repeatedly subdividing the original problem into smaller, more manageable tasks, and the conquer phase moves in the opposite direction, computing the final solution by working its way up from the leaves to the root.
While it is possible to implement divide-and-conquer methods such as this one using iteration, recursion is usually the simpler and more natural approach. In the following listing, the recursive function minRecursive() computes the smallest element in array in the index range from start to end using the
approach we have just described:
public static int minRecursive(int[] array, int start, int end) {
return switch (end - start) {
case 0 -> Integer.MAX_VALUE;
case 1 -> array[start];
default -> Math.min(
minRecursive(array, start, (start + end) / 2),
minRecursive(array, (start + end) / 2, end));
};
}
If the range is empty, the function returns MAX_VALUE; this can only happen if the original list is empty, since the subdivision process never produces empty ranges. If the range contains a single element array[start] it is returned immediately.
Otherwise, if the range contains two or more elements, we split it into two roughly equal halves, call minRecursive() recursively to find the smallest element in each, and use min() to select the smaller of the two results.
Of course, minRecursive() doesn’t actually construct a full tree like the one in Fig. 3.1 explicitly, but its execution follows the same tree-like structure: Every invocation of minRecursive() corresponds to a particular
node in the tree, and the call stack at that point represents the path from the root to that node. There is a close relationship between recursion and trees in general: Just as the structure of recursive algorithms can be naturally visualized using
trees, most tree-like shapes and data structures are most easily constructed and processed using recursive algorithms.
Despite the obvious differences, iteration and recursion are actually two sides of the same coin: every computation that can be expressed using iteration can also be expressed using recursion and vice versa. It’s not difficult to see why that’s the case: Every loop can be simulated by a recursive function that
calls itself for as long as the loop condition is fulfilled, and every recursive algorithm can be simulated by an iterative algorithm by keeping track of recursive calls in a stack-like data structure.
Even though iteration and recursion are equally powerful in theory, there are reasons to prefer one over the other in practice. Iteration often leads to simpler programs if a computation can be expressed as a well-defined sequence of steps, and iterative algorithms tend to run slightly faster since most
compilers are better at optimizing loops than recursive function calls. Recursion, on the other hand, excels at problems that branch into multiple sub-problems, and in such cases leads to algorithms that are simpler and easier to prove correct. At the end of the day, both approaches are equally
indispensable for expressing repetition in computer programs.
Exercises
Exercise 3.1.Write a recursive function that has the same effect as the following for loop:
for (int i = 0; i < 10; i++)
System.out.println(i):
Exercise 3.2.Devise and implement a recursive algorithm for reversing lists.