If you are here, it is because you are a coding newbie trying to understand the concept of recursion. Well, rest assured you have found the right place. Simply speaking, recursion is JUST a function that calls itself. Thank you for coming to my Ted talk!
Okay okay, so perhaps it is not that simple. When I first started learning about recursion, I was so lost, and the deeper I went, the more lost I became. Like Dorothy from “The Wizard of Oz”, I found myself saying “Toto, I don’t think we are in Kansas anymore” and I was longing to go back to the comfort of my vanilla JavaScript. Knowing the only way out is to move forward, I pressed on, all while looking out for those pesky lions and tigers and bears “Oh my!”. In this blog, I am going to try to break down the basic concepts in the simplest way, so you can click-click-click those sparkly red slippers and get back home.
Basic Components:
There are three basic components of recursion that are crucial to understanding:
- A base case, which is just a fancy way of referring to a condition that once met will stop the function from calling itself. We need this so we aren’t stuck in an infinite loop, or in this case, the call stack exceeding its limit.
- The function must call itself recursively, which simply means the function will continue to run repeatedly by calling itself until it reaches the base case.
- The function must change its state to move toward the base case. Huh?? I know, this one confused me as well. This means the parameter within the function must update/change its value to work its way toward the conditional set in the base case. This will result in the function coming to a completion.
Let’s go over an example to ensure we are on the same page, but first, we will start with a basic for loop. Below we have a regular for loop that is passing in the value of 3. Based on the function below, what do you predict will display in the console?
function countDown(n) {
for (let i = n; i > 0; i--){
console.log(i)
}
console.log('This is the end of my loop')
}
countDown(3)
If you answered with 3, 2, 1, “This is the end of my loop”, you are correct! Now let’s turn this regular for loop into a recursive function and explain what is happening. First, we need to make sure we have all the necessary components: our base case, a function that calls itself, and a way to move closer to the base case.
Example of a Recursive Function:
function recursiveCountDown(n){
if(n <= 0){
console.log('You made it to the end again!')
return
}
console.log(n)
recursiveCountDown(n-1)
}
recursiveCountDown(3)
Example of a Recursive Function with a breakdown of the necessary parts:
In the example above, you will see we have broken down the function into three parts:
Part 1: The section contained in the blue box is our base case. Here you will see we are using an if statement to say, if n <= 0 then console.log “You made it to the end again!”. If n is not less than or equal to 0 then move on to the next part of the function.
Part 2: In the red box, we have the next essential component of a recursion function. This small line of code is where the function calls itself.
Part 3: In the yellow box, we have the final necessary component. Rather than recalling n (which would just result in an infinite loop), we call n - 1. This will ensure the value of n continues to change at each function call until it finally meets the condition of our if statement.
Based on the explanation, what do you think will be displayed in the console? If you said 3,2,1, “You made it to the end again!”, you would be correct. Just in case you came up with a different answer, here is a step-by-step breakdown, along with a video showing how the function behaved at each function call:
- Pass 3 as the value of n into the function and check to see if 3 meets the condition of 3 <= 0. Since this results in false, the value of 3 moves on to the next part of the function.
- Console log the value of n
- Call the function again but change the parameter from n to n – 1
- When the function runs, the process repeats but this time the value of n updates to equal 2. After passing the value through, we check to see if the condition of 2 <= 0 is met and when its not, we move on to the next part of the function.
- Console log the value of n.
- Run the function with the updated value of n.
- Repeat the same steps above:
- check the condition
- console.log n
- call the function after changing the parameter from 1 to 0
- pass 0 into the function
- check if 0 <= 0
- This returns true and we can now console log the last expression.
- The return that follows the console.log is the last part needed to close out the function and bring this charade to an end. Congratulations, you just made it through your first recursive function!
Since that was kind of a mouth full, I have included a video below that will visually show you how the function is behaving:
If you are anything like me, you are feeling great, everything seems to be making perfect sense but like any “sugar-free” brownie recipe, some things are just too good to be true. So, buckle up because we have one more major hurdle to jump over before we can be reunited with Auntie Em and Uncle Henry.
NOTE: Before we move any further, you will need a basic understanding of the call stack. Philip Roberts has a fantastic video on the event loop and the call stack that should help if you aren’t unfamiliar.
Last Hurdle of Recursion:
While researching more complex recursive examples to ensure I understood, I noticed people kept referring to "the chain reaction of returns" or “moving back up into the calls”. I had no idea what this meant and realized I was not fully understanding what recursive functions were doing. Why were there so many returns? Why wasn't the function just returning the return within the base case? Let's use one last example to answer these questions.
Imagine it is your birthday and you receive a huge present from your parents. Excitedly you unwrap the gift to discover a box labeled 52-inch flat-screen television. While thrilled, you are a little skeptical since the box seems too light to be a television. Deciding to investigate further, you open the television box and discover a box labeled PS5. Whoa! They bought you a PlayStation?? Thinking this might be too good to be true, you open the PlayStation and discover a box labeled MacBook Pro. This time you are not falling for your parent’s tricks! Upon opening the MacBook Pro you find another box but this time it isn't labeled. Hoping this is the end and hoping this box contains your gift, you open it up and discover…… an avocado. Man that was an evil prank!
Perhaps if we had written a function that searched through all those boxes until it returned a value, we could have avoided all those highs and lows and went on our merry way to make some guacamole.
Visually this function might look something like this:
function whatsInTheBox(box){
if(box <= 0) {
return "This is your present"
}
return whatsInTheBox(box - 1)
}
whatsInTheBox(4)
Below you will find a short video that demonstrates what is happening in our box function. I advise you to pause the video at each step to make sure you understand what the function is doing.
Below you will find the function written out with all the function calls and their values:
function whatsInTheBox(box){
if(box <= 0) {
return "This is your present"
}
return whatsInTheBox(box - 1)
}
//Below is just a visual representation of what is happening with the calls and returns
//The function continues to run until every box has been opened.
whatsInTheBox(4)
whatsInTheBox(3) //since 4 - 1 = 3
whatsInTheBox(2) //since 3 - 1 = 2
whatsInTheBox(1) //since 2 - 1 = 1
whatsInTheBox(0)//since 1 - 1 = 0
return "This is your present"
return "This is your present"
return "This is your present"
return "This is your present"
return "This is your present"
Did you notice each function call was added to the call stack before the function went through another iteration? This is because the function was looking for a value but since it didn't actually find one, it passed off the task to the call stack and kept looking. When the last box finally open to reveal an avocado, JavaScript still needed to go back through to let the other boxes know their worth. Since the last box contained the value of "avocado", all the boxes that precede the last box, also contained the value of avocado.
At this point in your recursive journey, you might be questioning why anyone would use this style of iteration over a regular for loop. After all, don't they accomplish the same thing with roughly the same amount of syntax? In these two examples, the simple answer is yes… but like so many other things in JavaScript, when code becomes too messy, a good developer tries to incorporate some syntactical sugar.
Recursive functions won't always make your life easier, but they might. So keep this little gem in your back pocket, after all, you never know when one might be asked during your next interview.