Head First Algorithms and Data Structures

Chapter 4. Thinking Recursively: Recursion

Recursion is one of the most powerful and elegant tools in the study of algorithms, and it’s 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 too big to handle are easily cracked into smaller, more 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 also 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

Your local ice cream shop just rolled out 10 new flavors you can’t wait to try. Instead of picking just one or two, you decide to go all in and stack all 10 scoops on a single cone. The fun part is that the order matters: chocolate on the bottom with vanilla on top is a totally different cone than vanilla on the bottom with chocolate on top. So the big question is: how many different cones could you make if you tried ...