Head First Algorithms and Data Structures

Chapter 4. Thinking Recursively: Recursion

A Note for Early Release Readers

With Early Release ebooks, you get books in their earliest form—the author’s raw and unedited content as they write—so you can take advantage of these technologies long before the official release of these titles.

This will be the 4th chapter of the final book.

If you’d like to be actively involved in reviewing and commenting on this draft, please reach out to the editor at [e-mail].

Recursion is one of the most powerful and elegant tools in the study of algorithms, and one you may not have been exposed to. If you haven’t met recursive algorithms before, get ready to change the way you think about code. Suddenly, problems that looked to big to handle, are easily cracked into smaller approachable pieces. You’ll find that recursion is a natural fit for many classic algorithms—like searching, sorting, and divide-and-conquer strategies—and can lead to solutions that are not only correct but simple. In this chapter, we’ll introduce you to recursion, show you why it’s so useful in algorithm design, and point out a few common potholes to avoid (yes, stack overflows are waiting if you’re careless). After this chapter you’ll never think about coding the same way again.

Let’s get some ice cream