What Is Recursion?

Recursion is an important concept in mathematics and programming. It's an elegant means of packing complex functionality into a compact function. Let's take a look at a simple example to break down how it works.

Recursion in programming

At first, recursion can be a little mind-boggling. The general rule is that a recursive function will call itself, and continue to call itself, until it reaches what is known as the "base case." A base case is a condition inside the function where something can be returned without making another call to itself. As soon as we reach this base case, the recursion has finished its job, and the recursive function will begin to "unroll" itself. Think about a potentially infinite number of nesting dolls. You keep nesting the dolls inside of larger and larger dolls, each with a slightly different design, until finally some condition about the design is met, and then it's time to open them all back up.

Let's say we need to calculate the sum of all numbers from 1 until some arbitrary number, commonly abbreviated as n. Before we talk about how to do this with a recursive function, let's first show how this could be done with a loop:

The code above will take whatever argument we initially pass, then initialize a loop that will terminate whenever the value of i reaches that same value that we've passed. So, essentially, if we pass a value of 3 to this function, this loop will be performed 3 times.

We also create a variable called sum and initialize it with the value of the passed argument. Each time we go through the loop, the current value of i will be added to this sum variable. Finally when the loop is complete, we'll return the value of sum. If we pass 3, we get back 6. In the code above, we pass 10 with the result of 55.

Making a recursive function

Alternatively, we could make a general recursive function. We'll just need to input the number to which everything needs to be counted, and the function itself will do the rest.

First, let's write this in JavaScript and then we'll figure out how the magic works:

First, we'll create the base case: if (x === 1){return(1)}. Naturally, this means that if x is 1, we return 1. If this were the only line of our function, it would work exactly as intended, provided we never pass anything above the number 1. Of course, that's not what we want.

Up next, things get a little more interesting. What happens if we don't get 1? If this is the case, we take whatever the current value of x is, and we add this to the result of the rec() function called again, this time with x - 1 as the argument: return x + rec(x - 1);. For example, if we run rec(10), the code is processed like this:

1. First, check to see if 1 has been reached.
2. If it hasn't, it will add the value of x and the result of rec() called again, this time passing the value of x - 1, like so: 10 + rec(9). Even though it says return on this line, we won't return anything yet because we need to process rec(9).
3. Next, rec(9) is run, the first step: check again to see if 1 was received.
4. Again the answer is no, and we'll again run x + rec(x - 1). Since x is equal to 9 this time, it will look like:  9 + rec(8). Again, nothing is returned yet, as we now must wait for the result of rec(8).
5. Next, check to see if 1 has been reached... again.
6. ... and this process will continue again and again, until finally...
7. We check to see if 1 was received and, hey, wait — it was!
8. At this point we start "unrolling" the process and returning values, so first 1 is returned back up one level. So, rec(1) returns 1.
9. One level up we had return 2 + rec(1). Since we've returned 1, it now looks like this: return 2 + 1. So we return 3 up to a higher level.
10. At that level we had return 3 + rec(2). Since rec(2) returns a value of 3, this will become return 3 + 3, which means a value of 6 is returned.
11. ... this process will now repeat again and again, returning and unwrapping all the values of the rec() function and adding this result to each iteration's value of x.
12. Finally, we end up with 10 + rec(9). Since rec(9) returns 45 from the previous level, our function adds 10 and 45 together, which gives the final result of 55, the sum of all numbers from 1 to 10.
13. We get this final result and save it to the variable result, which we then log to the console. Hooray, the recursion is over!

If you're feeling confused — don't worry! This concept can be slightly mind bending the first time you encounter it. A good exercise is to try and duplicate the code above on your own and make a note of what is happening during each step of the recursive function.

Special features of recursion

Here's a big question — what happens if we don't establish a base case in the first place? We'll quickly get into infinite loop territory. Since a recursive function calls itself, if it's incorrectly implemented, it can consume a lot of memory and resources. Further, the deeper the level of recursion, the more resources are required.

For instance, in the example above, it's important to note that this function will only work properly with positive numbers as arguments. Trying to pass a negative number will result in an infinite loop. Just as with any loop, this can be an issue to watch out for when working with your own recursive functions!

Sometimes, programmers can get carried away with recursion and forget to include an exit condition. As a result, the recursion infinitely deepens into itself, consumes all available resources, and the program crashes as a result. Some say this is how black holes are formed, but who knows?

But why do we use recursion at all? There are times when recursion is the only way to get things done. For example, it is needed when parsing HTML code or building a dependency tree.

What's next?

Now that you know a little more about recursion, you can make an interesting project. For example, you can make a program that solves sudoku at any difficulty level, or a program that draws cool mazes by continuing building on top of previous constructions.

Hopefully, you feel a little bit more enlightened about the topic of recursion. Never forget, each day is like a new iteration in your own cosmic recursive function, and if your base case is something like change my career and change my life, then here's some good news — we've got you covered! At TripleTen, we offer online education and mentorship to help you develop a career in tech, and allow you to take a deep dive into interesting topics like data science, web development, and more, in an awesome and supportive environment.