➰Recursion

Explained with boba.

In previous chapters, we'd talked about self-reference — a function that refers to itself. We will now take this idea one step further with recursion: a function that calls itself.

A Riddle

Before we dive into what recursion looks like in code, we'll try to attempt a logical puzzle together. Imagine you are standing in a very long line at a boba shop. You have class soon, and would really like to know how many people are in front of you. But the line is too long to count from where you are standing, and to get out of line would mean to lose your spot!

You are allowed to interact with your surroundings as you'd like, talk to anyone, or ask them (within reason) to do anything you'd like. You are not allowed to move. How do you figure out how many people are in front of you?

The crucial observation here is that this problem is too big to solve by yourself: you simply do not have enough information to do so. But, what if — and stay with me, here — what if the person in front of you somehow knew how many people were in front of her? Then, you could ask that person for that number, add 1 to it, and that would be how many people would be in line in front of you!

So, you go ahead and you tap the shoulder of the person in front of you and you ask them: "How many people are in front of you?" Now, how would this person figure out how many people are in front of them? The problem is too big for them to solve by themselves, still. So they do the same thing as you did, again. They tap the shoulder of the person in front of them.

And so on, and so forth do people ask the person in front of them, again and again. This process continues until we reach the person at the very front of the line. This person does not need to ask anyone, because for this person the problem is not too big to solve, finally. They say directly, that there are zero people in the line in front of them.

And then the process continues backwards! The person second in line, adds 1 and tells the person behind them that there is 1 person in front of them. Then, two. Then, three. And the information updates and travels all the way back to you, and you finally have an answer to your question. Without ever moving out of place. The power of recursion.

The Big Picture of Recursion

The big idea behind the concept of recursion is as follows: when a problem is too big to be solved, we can figure out a way to solve a smaller problem of a similar structure. We keep making the problem smaller until we reach some state where the problem is small enough to be solved directly. Then, we build back on top of this information over and over again until our original problem is solved.

If you're confused, good! You should be. Recursion is a confusing concept, and a particularly challenging one to grasp. To develop a better understanding, let's leave the realm of metaphors and head to analyzing recursive programs in the next section.