How I Finally Figured Out Recursion

Let’s start at the end, a very good place to start.

As I suspect a lot of people feel at some point, writing recursive functions seemed dense and counterintuitive to me for a while. You call a function, inside that function itself? How does that even work? Why would you do it? What’s the actual design pattern of making it properly?

While working through a coding challenge, I finally had a breakthrough that helped me answer all those questions, as well as identify the source of my previous hang-ups. I realized that I’d been approaching recursion problems backwards, because I’d been approaching them forwards. When you’re starting to write a recursive problem, it’s a good idea to start it from the end and work backwards from there. Because that’s the path forwards. Confusing? Yeah, recursion is. But I’ll explain. I’m by no means an expert, but hopefully this will help other greenhorns have a similar breakthrough and start down the path towards mastering recursion.

Here are the general realizations I had about recursion, and then we’ll look at an example:

• Recursion patterns can be used to do some kind of repeated work for an indefinite number of times until certain criteria are met.
• At the end of a recursion pattern, there should be some kind of check to see if the work needs to be done again. If not, exit the function and return the desired result. But if so, start the pattern over.
• This means that when writing a recursive function, you can start at the end with a simple if-else statement. In your if statement, check if your desired work is done and return the result if so. If not, just invoke the function again.

Let’s look at an example problem. Let’s say we’re trying a function to return a count of colleges and universities that A) have a given substring in their name and B) are over a given student population size. We’ll say that to accomplish this, we’re querying an API where a name= argument in the URL will return only results containing the matching substring. Our challenge, however, is that the API results are paginated and we need to go through all the result pages to get our final answer.

The full function is below (or at least the essential elements), and then we’ll break it down.

Our API query always returns an object with a total_pages key, so we can use that to control our recursive function:

const json = JSON.parse(body)
const lastPage = json['total_pages']

Using that lastPage variable, we can set up the recursive logic at the end of the makeRequest() function:

if (page === lastPage) {
  return count
} else {
  page++
  makeRequest()
}

If there are no more pages to query, then we can return our count variable. Otherwise, we increment the page number (which is interpolated into the URL for our next query) and makeRequest() calls itself, within itself.

The main body of makeRequest() involves sending a query, looping over results, and incrementing the count variable, but honestly — none of that matters here. This is just a basic example. We’re talking about recursion as a general concept. The body of the function can do whatever you want it to; the important part is the logic at the end. By its very definition, something recursive will keep repeating forever until it breaks. It’s technically recursion if we accidentally write a while loop and forget to increment the counter. In this case, the recursion breaks (eventually) through computer error. When we write recursive functions, however, we harness the chaos of recursion by intentionally writing in conditions to break the cycle. As long as you know when you want your cycle to break, you can write a recursive function. All it takes is a simple if-else statement to check at the end of each cycle.

Begin from the end.