Chapter 3. Recursion


In this chapter

  • You learn about recursion. Recursion is a coding technique used in many algorithms. It’s a building block for understanding later chapters in this book.
  • You learn how to break a problem down into a base case and a recursive case. The divide-and-conquer strategy (chapter 4) uses this simple concept to solve hard problems.

I’m excited about this chapter because it covers recursion, an elegant way to solve problems. Recursion is one of my favorite topics, but it’s divisive. People either love it or hate it, or hate it until they learn to love it a few years later. I personally was in that third camp. To make things easier for you, I have some advice:

  • This chapter has a lot of code examples. Run the code for yourself to see how it works.
  • I’ll talk about recursive functions. At least once, step through a recursive function with pen and paper: something like, “Let’s see, I pass 5 into factorial, and then I return 5 times passing 4 into factorial, which is ...,” and so on. Walking through a function like this will teach you how a recursive function works.

This chapter also includes a lot of pseudocode. Pseudocode is a high-level description of the problem you’re trying to solve, in code. It’s written like code, but it’s meant to be closer to human speech.


Suppose you’re digging through your grandma’s attic and come across a mysterious locked suitcase.

Grandma tells you that the key for the suitcase is probably in this other box.

Base case and recursive case

The stack