Chapter 13
Recursive Algorithms for Speed

We’ve seen that understanding recursion unlocks all sorts of new algorithms, such as traversing a filesystem or producing anagrams. In this chapter, you’re going to learn that recursion is also the key to algorithms that can make our code run much, much faster.

In previous chapters, we’ve encountered a number of sorting algorithms, including Bubble Sort, Selection Sort, and Insertion Sort. In real life, however, none of these methods are actually used to sort arrays. Most computer languages have built-in sorting functions for arrays that save us the time and effort of implementing our own. And in many of these languages, the sorting algorithm that is employed under the hood is Quicksort.

The reason we’re going to dig into Quicksort (even though it’s already built into many computer languages) is because by studying how it works, you can learn how to use recursion to greatly speed up an algorithm, and you can do the same for other practical algorithms of the real world.

Quicksort is an extremely fast sorting algorithm that is particularly efficient for average scenarios. While in worst-case scenarios (that is, inversely sorted arrays) it performs similarly to Insertion Sort and Selection Sort, it’s much faster for average scenarios—which are what occur most of the time.

Quicksort relies on a concept called partitioning, so we’ll jump into that first.