Check out other books by Al Sweigart, free online or available for purchase:
...and other books as well! Or register for the online video course. You can also donate to support the author directly.
Divide-and-conquer algorithms are those that split large problems into smaller subproblems, then divide those subproblems into ones that are smaller yet, until they become trivial to conquer. This approach makes recursion an ideal technique to use: the recursive case divides the problem into self-similar subproblems, and the base case occurs when the subproblem has been reduced to a trivial size. One benefit of this approach is that these problems can be worked on in parallel, allowing multiple central processing unit (CPU) cores or computers to work on them.
In this chapter, we’ll look at some common algorithms that use recursion to divide and conquer, such as binary search, quicksort, and merge sort. We’ll also reexamine summing an array of integers, this time with a divide-and-conquer approach. Finally, we’ll take a look at the more esoteric Karatsuba multiplication algorithm, developed in 1960, that laid the basis for computer hardware’s fast integer multiplication.
Let’s say you have a bookshelf of 100 books. You can’t remember which books you have or their exact locations on the shelf, but you do know that they are sorted alphabetically by title. To find your book Zebras: The Complete Guide, you wouldn’t start at the beginning of the bookshelf, where Aaron Burr Biography is, but rather toward the end of the bookshelf. Your zebra book wouldn’t be the very last book on the shelf if you also had books on zephyrs, zoos, and zygotes, but it would be close. Thus, you can use the facts that the books are in alphabetical order and that Z is the last letter of the alphabet as heuristics, or approximate clues, to look toward the end of the shelf rather than the beginning.
Binary search is a technique for locating a target item in a sorted list by repeatedly determining which half of the list the item is in. The most impartial way to search the bookshelf is to start with a book in the middle, and then ascertain if the target book you’re looking for is in the left half or the right half.
You can then repeat this process, as shown in Figure 5-1: look at the book in the middle of your chosen half and then determine whether your target book is in the left-side quarter or the right-side quarter. You can do this until you either find the book, or find the place where the book should be but isn’t and declare that the book doesn’t exist on the shelf.
Figure 5-1: A binary search repeatedly determines which half of a range contains your target item in a sorted array of items.
This process scales efficiently; doubling the number of books to search adds only one step to the search process. A linear search of a shelf with 50 books takes 50 steps, and a linear search of a shelf with 100 books takes 100 steps. But a binary search of a shelf with 50 books takes only 6 steps, and a shelf with 100 books takes only 7 steps.
Let’s ask the three recursion questions about our binary search implementation:
left > right.)Examine the following binarySearch() function in our binarySearch.py program, which locates a value, needle, in a sorted list of values, haystack:
Python
def binarySearch(needle, haystack, left=None, right=None):
# By default, `left` and `right` are all of `haystack`:
if left is None:
left = 0 # `left` defaults to the 0 index.
if right is None:
right = len(haystack) - 1 # `right` defaults to the last index.
print('Searching:', haystack[left:right + 1])
if left > right: # BASE CASE
return None # The `needle` is not in `haystack`.
mid = (left + right) // 2
if needle == haystack[mid]: # BASE CASE
return mid # The `needle` has been found in `haystack`
elif needle < haystack[mid]: # RECURSIVE CASE
return binarySearch(needle, haystack, left, mid - 1)
elif needle > haystack[mid]: # RECURSIVE CASE
return binarySearch(needle, haystack, mid + 1, right)
print(binarySearch(13, [1, 4, 8, 11, 13, 16, 19, 19]))The binarySearch.html program has this JavaScript equivalent:
JavaScript
<script type="text/javascript">
function binarySearch(needle, haystack, left, right) {
// By default, `left` and `right` are all of `haystack`:
if (left === undefined) {
left = 0; // `left` defaults to the 0 index.
}
if (right === undefined) {
right = haystack.length - 1; // `right` defaults to the last index.
}
document.write("Searching: [" +
haystack.slice(left, right + 1).join(", ") + "]<br />");
if (left > right) { // BASE CASE
return null; // The `needle` is not in `haystack`.
}
let mid = Math.floor((left + right) / 2);
if (needle == haystack[mid]) { // BASE CASE
return mid; // The `needle` has been found in `haystack`.
} else if (needle < haystack[mid]) { // RECURSIVE CASE
return binarySearch(needle, haystack, left, mid - 1);
} else if (needle > haystack[mid]) { // RECURSIVE CASE
return binarySearch(needle, haystack, mid + 1, right);
}
}
document.write(binarySearch(13, [1, 4, 8, 11, 13, 16, 19, 19]));
</script>When you run these programs, the list [1, 4, 8, 11, 13, 16, 19, 19] is searched for 13, and the output looks like this:
Searching: [1, 4, 8, 11, 13, 16, 19, 19]
Searching: [13, 16, 19, 19]
Searching: [13]
4The target value 13 is indeed at index 4 in that list.
The code calculates the middle index (stored in mid) of the range defined by the left and right indices. At first, this range is the entire length of the items list. If the value at the mid index is the same as needle, then mid is returned. Otherwise, we need to figure out whether our target value is in the left half of the range (in which case, the new range to search is left to mid - 1) or in the right half (in which case, the new range to search is mid + 1 to end).
We already have a function that can search this new range: binarySearch() itself! A recursive call is made on the new range. If we ever get to the point where the right end of the search range comes before the left, we know that our search range has shrunk down to zero and our target value isn’t to be found.
Notice that the code performs no actions after the recursive call returns; it immediately returns the return value of the recursive function call. This feature means that we could implement tail call optimization for this recursive algorithm, a practice we explain in Chapter 8. But also, it means that binary search can easily be implemented as an iterative algorithm that doesn’t use recursive function calls. This book’s downloadable resources at https://nostarch.com/recursive-book-recursion include the source code for an iterative binary search for you to compare with the recursive binary search.
Remember that binarySearch()’s speed advantage comes from the fact that the values in items are sorted. If the values are out of order, the algorithm won’t work. Enter quicksort, a recursive sorting algorithm developed by computer scientist Tony Hoare in 1959.
Quicksort uses a divide-and-conquer technique called partitioning. Think of partitioning this way: imagine you have a large pile of unalphabetized books. Grabbing one book and placing it in the right spot on the shelf means you’ll spend a lot of time rearranging the bookshelf as it gets full. It would help if you first turned the pile of books into two piles: an A to M pile and an N to Z pile. (In this example, M would be our pivot.)
You haven’t sorted the pile, but you have partitioned it. And partitioning is easy: the book doesn’t have to go into the correct place in one of the two piles, it just has to go into the correct pile. Then you can further partition these two piles into four piles: A to G, H to M, N to T, and U to Z. This is shown in Figure 5-2. If you keep partitioning, you end up with piles that contain one book each (the base case), and the piles are now in sorted order. This means the books are now in sorted order as well. This repeated partitioning is how quicksort works.
For the first partitioning of A to Z, we select M as the pivot value because it’s the middle letter between A and Z. However, if our collection of books consisted of one book about Aaron Burr and 99 books about zebras, zephyrs, zoos, zygotes, and other Z topics, our two partitioned piles would be heavily unbalanced. We would have the single Aaron Burr book in the A to M pile and every other book in the M to Z pile. The quicksort algorithm works fastest when the partitions are evenly balanced, so selecting a good pivot value at each partition step is important.
Figure 5-2: Quicksort works by repeatedly partitioning items into two sets.
However, if you don’t know anything about the data you’re sorting, it’s impossible to select an ideal pivot. This is why the generic quicksort algorithm simply uses the last value in the range for the pivot value.
In our implementation, each call to quicksort() is given an array of items to sort. It is also given left and right arguments specifying the range of indices in that array to sort, similar to binarySearch()’s left and right arguments. The algorithm selects a pivot value to compare with the other values in the range, then places the values to either the left side of the range (if they’re less than the pivot value) or the right side (if they’re greater than the pivot value). This is the partition step. Next, the quicksort() function is recursively called on these two, smaller ranges until a range has been reduced to zero. The list becomes more and more sorted as the recursive calls are made, until finally the entire list is in the correct order.
Note that the algorithm modifies the array in place. See “Modifying a List or Array in Place” in Chapter 4 for details. Thus, the quicksort() function doesn’t return a sorted array. The base case merely returns to stop producing more recursive calls.
Let’s ask the three recursion questions about our binary search implementation:
The following quicksort() function in the quicksort.py Python program sorts the values in the items list into ascending order:
def quicksort(items, left=None, right=None):
# By default, `left` and `right` span the entire range of `items`:
if left is None:
left = 0 # `left` defaults to the 0 index.
if right is None:
right = len(items) - 1 # `right` defaults to the last index.
print('\nquicksort() called on this range:', items[left:right + 1])
print('................The full list is:', items)
if right <= left: ❶
# With only zero or one item, `items` is already sorted.
return # BASE CASE
# START OF THE PARTITIONING
i = left # i starts at the left end of the range. ❷
pivotValue = items[right] # Select the last value for the pivot.
print('....................The pivot is:', pivotValue)
# Iterate up to, but not including, the pivot:
for j in range(left, right):
# If a value is less than the pivot, swap it so that it's on the
# left side of `items`:
if items[j] <= pivotValue:
# Swap these two values:
items[i], items[j] = items[j], items[i] ❸
i += 1
# Put the pivot on the left side of `items`:
items[i], items[right] = items[right], items[i]
# END OF THE PARTITIONING
print('....After swapping, the range is:', items[left:right + 1])
print('Recursively calling quicksort on:', items[left:i], 'and', items[i + 1:right + 1])
# Call quicksort() on the two partitions:
quicksort(items, left, i - 1) # RECURSIVE CASE
quicksort(items, i + 1, right) # RECURSIVE CASE
myList = [0, 7, 6, 3, 1, 2, 5, 4]
quicksort(myList)
print(myList)The quicksort.html program contains the JavaScript equivalent:
<script type="text/javascript">
function quicksort(items, left, right) {
// By default, `left` and `right` span the entire range of `items`:
if (left === undefined) {
left = 0; // `left` defaults to the 0 index.
}
if (right === undefined) {
right = items.length - 1; // `right` defaults to the last index.
}
document.write("<br /><pre>quicksort() called on this range: [" +
items.slice(left, right + 1).join(", ") + "]</pre>");
document.write("<pre>................The full list is: [" + items.join(", ") + "]</pre>");
if (right <= left) { ❶
// With only zero or one item, `items` is already sorted.
return; // BASE CASE
}
// START OF THE PARTITIONING
let i = left; ❷ // i starts at the left end of the range.
let pivotValue = items[right]; // Select the last value for the pivot.
document.write("<pre>....................The pivot is: " + pivotValue.toString() +
"</pre>");
// Iterate up to, but not including, the pivot:
for (let j = left; j < right; j++) {
// If a value is less than the pivot, swap it so that it's on the
// left side of `items`:
if (items[j] <= pivotValue) {
// Swap these two values:
[items[i], items[j]] = [items[j], items[i]]; ❸
i++;
}
}
// Put the pivot on the left side of `items`:
[items[i], items[right]] = [items[right], items[i]];
// END OF THE PARTITIONING
document.write("<pre>....After swapping, the range is: [" + items.slice(left, right + 1).join(", ") + "]</pre>");
document.write("<pre>Recursively calling quicksort on: [" + items.slice(left, i).join(", ") + "] and [" + items.slice(i + 1, right + 1).join(", ") + "]</pre>");
// Call quicksort() on the two partitions:
quicksort(items, left, i - 1); // RECURSIVE CASE
quicksort(items, i + 1, right); // RECURSIVE CASE
}
let myList = [0, 7, 6, 3, 1, 2, 5, 4];
quicksort(myList);
document.write("<pre>[" + myList.join(", ") + "]</pre>");
</script>This code is similar to the code in the binary search algorithm. As defaults, we set the left and right ends of the range within the items array to the beginning and end of the entire array. If the algorithm reaches the base case of the right end at or before the left end (a range of one or zero items), the sorting is finished ❶.
In each call to quicksort(), we partition the items in the current range (defined by the indices in left and right), and then swap them around so that the items less than the pivot value end up on the left side of the range and the items greater than the pivot value end up on the right side of the range. For example, if 42 is the pivot value in the array [81, 48, 94, 87, 83, 14, 6, 42], a partitioned array would be [14, 6, 42, 81, 48, 94, 87, 83]. Note that a partitioned array is not the same thing as a sorted one: although the two items to the left of 42 are less than 42, and the five items to the right of 42 are greater than 42, the items are not in sorted order.
The bulk of the quicksort() function is the partitioning step. To get an idea of how partitioning works, imagine an index j that begins at the left end of the range and moves to the right end ❷. We compare the item at index j with the pivot value and then move right to compare the next item. The pivot value can be arbitrarily chosen from any value in the range, but we’ll always use the value at the right end of the range.
Imagine a second index i that also begins at the left end. If the item at index j is less than or equal to the pivot, the items at indices i and j are swapped ❸ and i is increased to the next index. So while j always increases (that is, moves right) after each comparison with the pivot value, i increases only if the item at index j is less than or equal to the pivot.
The names i and j are commonly used for variables that hold array indices. Someone else’s quicksort() implementation may instead use j and i, or even completely different variables. The important thing to remember is that two variables store indices and behave as shown here.
As an example, let’s work through the first partitioning of the array [0, 7, 6, 3, 1, 2, 5, 4], and the range defined by left of 0 and right of 7 to cover the full size of the array. The pivot will be the value at the right end, 4. The i and j index begin at index 0, the left end of the range. At each step, index j always moves to the right. Index i moves only if the value at index j is less than or equal to the pivot value. The items array, the i index, and the j index begin as follows:
items: [0, 7, 6, 3, 1, 2, 5, 4]
indices: 0 1 2 3 4 5 6 7
^
i = 0 i
j = 0 jThe value at index j (which is 0) is less than or equal to the pivot value (which is 4), so swap the values at i and j. This results in no actual change since i and j are the same index. Also, increase i so that it moves to the right. The j index increases for every comparison with the pivot value. The state of the variables now looks like this:
items: [0, 7, 6, 3, 1, 2, 5, 4]
indices: 0 1 2 3 4 5 6 7
^
i = 1 i
j = 1 jThe value at index j (which is 7) is not less than or equal to the pivot value (which is 4), so don’t swap the values. Remember, j always increases, but i increases only after a swap is performed—so i is always either at or to the left of j. The state of the variables now looks like this:
items: [0, 7, 6, 3, 1, 2, 5, 4]
indices: 0 1 2 3 4 5 6 7
^
i = 1 i ^
j = 2 jThe value at index j (which is 6) is not less than or equal to the pivot value (which is 4), so don’t swap the values. The state of the variables now looks like this:
items: [0, 7, 6, 3, 1, 2, 5, 4]
indices: 0 1 2 3 4 5 6 7
^
i = 1 i ^
j = 3 jThe value at index j (which is 3) is less than or equal to the pivot value (which is 4), so swap the values at i and j. The 7 and 3 swap positions. Also, increase i so that it moves to the right. The state of the variables now looks like this:
items: [0, 3, 6, 7, 1, 2, 5, 4]
indices: 0 1 2 3 4 5 6 7
^
i = 2 i ^
j = 4 jThe value at index j (which is 1) is less than or equal to the pivot value (which is 4), so swap the values at i and j. The 6 and 1 swap positions. Also, increase i so that it moves to the right. The state of the variables now looks like this:
items: [0, 3, 1, 7, 6, 2, 5, 4]
indices: 0 1 2 3 4 5 6 7
^
i = 3 i ^
j = 5 jThe value at index j (which is 2) is less than or equal to the pivot value (which is 4), so swap the values at i and j. The 7 and 2 swap positions. Also, increase i so that it moves to the right. The state of the variables now looks like this:
items: [0, 3, 1, 2, 6, 7, 5, 4]
indices: 0 1 2 3 4 5 6 7
^
i = 4 i ^
j = 6 jThe value at index j (which is 6) is not less than or equal to the pivot value (which is 4), so don’t swap the values. The state of the variables now looks like this:
items: [0, 3, 1, 2, 6, 7, 5, 4]
indices: 0 1 2 3 4 5 6 7
^
i = 4 i ^
j = 7 jWe’ve reached the end of the partitioning. The index j is at the pivot value (which is always the rightmost value in the range), so let’s swap i and j one last time to make sure the pivot is not on the right half of the partition. The 6 and 4 swap positions. The state of the variables now looks like this:
items: [0, 3, 1, 2, 4, 7, 5, 6]
indices: 0 1 2 3 4 5 6 7
^
i = 4 i ^
j = 7 jNotice what is happening with the i index: this index will always receive the values smaller than the pivot value as a result of swapping; then the i index moves right to receive future smaller-than-the-pivot values. As a result, everything to the left of the i index is smaller than or equal to the pivot, and everything to the right of the i index is greater than the pivot.
The entire process repeats as we recursively call quicksort() on the left and right partitions. When we partition these two halves (and then partition the four halves of these two halves with more recursive quicksort() calls, and so on), the entire array ends up sorted.
When we run these programs, the output shows the process of sorting the [0, 7, 6, 3, 1, 2, 5, 4] list. The rows of periods are meant to help you line up the output when writing the code:
quicksort() called on this range: [0, 7, 6, 3, 1, 2, 5, 4]
................The full list is: [0, 7, 6, 3, 1, 2, 5, 4]
....................The pivot is: 4
....After swapping, the range is: [0, 3, 1, 2, 4, 7, 5, 6]
Recursively calling quicksort on: [0, 3, 1, 2] and [7, 5, 6]
quicksort() called on this range: [0, 3, 1, 2]
................The full list is: [0, 3, 1, 2, 4, 7, 5, 6]
....................The pivot is: 2
....After swapping, the range is: [0, 1, 2, 3]
Recursively calling quicksort on: [0, 1] and [3]
quicksort() called on this range: [0, 1]
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
....................The pivot is: 1
....After swapping, the range is: [0, 1]
Recursively calling quicksort on: [0] and []
quicksort() called on this range: [0]
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
quicksort() called on this range: []
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
quicksort() called on this range: [3]
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
quicksort() called on this range: [7, 5, 6]
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
....................The pivot is: 6
....After swapping, the range is: [5, 6, 7]
Recursively calling quicksort on: [5] and [7]
quicksort() called on this range: [5]
................The full list is: [0, 1, 2, 3, 4, 5, 6, 7]
quicksort() called on this range: [7]
................The full list is: [0, 1, 2, 3, 4, 5, 6, 7]
Sorted: [0, 1, 2, 3, 4, 5, 6, 7]Quicksort is a commonly used sorting algorithm because it is straightforward to implement and, well, quick. The other commonly used sorting algorithm, merge sort, is also fast and uses recursion. We cover it next.
Computer scientist John von Neumann developed merge sort in 1945. It uses a divide-merge approach: each recursive call to mergeSort() divides the unsorted list into halves until they’ve been whittled down into lists of lengths of zero or one. Then, as the recursive calls return, these smaller lists are merged together into sorted order. When the last recursive call has returned, the entire list will have been sorted.
For example, the divide step takes a list, such as [2, 9, 8, 5, 3, 4, 7, 6], and splits it into two lists, like [2, 9, 8, 5] and [3, 4, 7, 6], to pass to two recursive function calls. At the base case, the lists have been divided into lists of zero or one item. A list with nothing or one item is naturally sorted. After the recursive calls return, the code merges these small, sorted lists together into larger sorted lists until finally the entire list is sorted. Figure 5-3 shows an example using merge sort on playing cards.
Figure 5-3: The divide and merge phases of merge sort
For example, at the end of the division phase, we have eight separate lists of single numbers: [2], [9], [8], [5], [3], [4], [7], [6]. A list of just one number is naturally in sorted order. Merging two sorted lists into a larger sorted list involves looking at the start of both smaller lists and appending the smaller value to the larger list. Figure 5-4 shows an example of merging [2, 9] and [5, 8]. This is repeatedly done in the merge phase until the end result is that the original