Recursion is a powerful programming technique that allows us to break down large, complicated problems into smaller, more manageable pieces. Not only is it a valuable tool in our coding toolkit, but understanding recursion will also help us improve our logical thinking and problem-solving skills. So why wait? In this article, we'll get a good overview on what recursion and why knowing more about it will kick our coding skills up a bunch of notches!

Onwards!

Our Giant Cookie Problem

One way to think about recursion is as follows: we start with a large problem, and we break this large problem down into smaller and smaller pieces until we reach a point where the problem is simple enough to solve directly. This will make more sense with an example, so let's imagine our job is to eat this gigantic cookie:

Because of how large the cookie is, most people will have no way to eat this entire cookie in one bite. What we can do is break this cookie into smaller pieces:

As we can see, these smaller pieces are still too big to eat in one bite. What we need to do is keep breaking our pieces down into even smaller pieces. Eventually, we will have broken our cookie down into a small bite-sized piece that we can easily eat:

The part to notice is that we now have many bite-sized cookies that we need to eat. We don't have just one big cookie, nor do we have just one small cookie. The quantity of cookies we eat remains the same. The only difference is that the quantity is now spread across many cookies. This process of taking something large and breaking it into ever smaller pieces is very similar to how recursion works in the context of our programming problems.

Recursion in Programming

While thinking about recursion in the form of a cookie is all good and great...and delicious, we'll find the biggest bang when we throw recursion at thorny programming problems. Echoing what we started off with, the textbook definition of recursion involves two parts: a function that calls itself repeatedly and a condition that stops our function from calling itself. Let's go into more detail on what these two parts do.

Recursive Function Call

The first part involves what is known as a recursive function call where a function calls itself repeatedly. Taken literally, it would look a little bit like this:

function hello() {
  console.log("I'm a little function, short and stout!");
  
  hello();
}

We have a function called hello, and inside the function body, we are calling hello again. Now, this code won't actually run if we try it. This will cause an infinite loop since the code will never stop running. More specifically, our code will cause a stack overflow error:

The way we avoid this brings us to the second part...

Terminating Condition

The second part is a condition that stops our function from calling itself forever, the scary-sounding terminating condition. Leaning on our cookie example from earlier, we kept dividing our cookies into smaller pieces until it became bite-sized. The terminating condition is to check if the size of the cookie is bite-sized. If the size is bite-sized, then eat the cookie. If the size isn't bite-sized, then divide the cookie further into smaller pieces.

Turning all of those words into code, let's say we want our hello function to act as an accumulator where we pass in a number, and it returns the sum of all the numbers leading up to the number we passed in. For example, if pass in the number 5, our code will add up all numbers leading up to it, where it will calculate 5 + 4 + 3 + 2 + 1 and return a final value of 15. Below is what our revised hello function will look like if we did all of this:

function hello(num) {
  if (num <= 1) {
    // terminating condition
    return num;
  } else {
    // recursive function call
    return num + hello(num - 1);
  }
}

console.log(hello(5)); // 15

Take a moment to look at what our code is doing. If we had to visualize how this code runs, it would look as follows where we have our initial hello(5) call at the top and the results of our return statements following it:

At each row where our num argument is greater than 1, we show the result of num + hello(num - 1):

We keep repeating this until our num value hits 1. When this happens, we hit our terminating condition (num <= 1) and return the value of num itself, which is just 1 in our case:

Taking a step back, for just one more time, we can see how we started with a large problem and, with each recursive call, broke the problem down into much smaller steps. We continued until we hit our terminating condition and were left with an easily digestible nugget, a plain old number. Really cool, right?

Conclusion

As we can see, recursion is the gift that keeps on giving...and giving...and giving! Jokes aside, while our hello accumulator function is a bit contrived, it does do a good job highlighting the two basic ingredients needed to solve a problem using recursion. Those ingredients are the:

1. Recursive function call
2. Terminating condition

We are going to go a bit deeper in future tutorials where we apply recursive techniques to solve more realistic and more complicated problems. Also, as with any problem-solving tool, recursion is only the cure for some things. There are situations (quite a bunch, as it turns out) where we need to look beyond recursion to solve problems in a more efficient way, and we'll cross that bridge shortly as well.

Just a final word before we wrap up. If you have a question and/or want to be part of a friendly, collaborative community of over 220k other developers like yourself, post on the forums for a quick response!