For many new developers, recursion is one of the most misunderstood concepts in JavaScript. Unfortunately, this misunderstanding manifests itself in many different ways, generally falling somewhere between total indifference to abject terror.
Today I hope to demystify the concept of recursion and work through a few examples that DON'T involve the tricky math concepts you likely forgot from your "glory days" of high school.
So... what is recursion again?
Simply put, recursion is a programming technique where a function CALLS ITSELF.
Yup. Mind-bending, I know.
But let's break it down a little more to hopefully clear things up.
More specifically, a recursive function is a function that calls itself until it arrives at a final result.
Well, how do we know when we've arrived at a final result? Great question. Before we can get into that, we need to first understand what situations recursion might be useful for!
When You Might Use Recursion
Recursion is great for when we want to perform the same action over and over. The only that will change when we repeat the action will be the data involved.
Sound familiar? That's because many of the techniques we use for iteration, such as for loops, while loops, etc. do a very similar thing! So remember, while we can often use recursion in place of these foundational tools, we usually don't NEED to use recursion.
One pitfall I see many of my students encounter is as soon as they learn recursion they try implementing it EVERYWHERE, even in settings where iteration may be easier to read/understand from a developer empathy perspective!
There are definitely situations where recursion is a better choice than relying solely on iteration - but remember, there are multiple ways to do the same thing in programming!
How to Build a Recursive Function
While recursion may be a very intimidating concept, the actual construction of a recursive function is fairly straightforward. For this breakdown, we will use the following scenario to start building our recursive function.
// Create a function that takes in an array of numbers
// and adds the numbers together
let superCoolNumbers = [1, 2, 3, 4, 5]
getSum(superCoolNumbers) // 10
Part I - Creating a Base Case
Our base case is our condition that we will write that tells our recursive function to STOP calling itself over and over again. Think of it like an big stop button or an emergency break.
One thing I've learned in my time programming is that computers aren't super smart - we have to give them explicit instructions on what we want them to do. Recursion is no exception. We have to create a base case to tell our function when to stop executing!
If we don't, we run the risk of recursively calling the function FOREVER. You'll know you've entered this zone if you get an error that says something like RangeError: Maximum call stack size exceeded. For the purposes of this post, we will not cover the nitty gritty of the JavaScript call stack, but we will talk about how it works in relation to some of our later examples.
OK, so back to our getSum problem. In simple terms, when do we want the function to STOP? Well, when there aren't any numbers left to add together, that seems like a pretty good time to stop!
//create a function that takes in an array of numbers
//create a base case
//when there are no more numbers, stop executing
Great! Now we have some steps we can follow to write out our actual code! It may look something like this...
const getSum = numbers => {
//base case
if (numbers.length === 0) {
return 0
}
}
So, why did I choose to return 0? Well, let's remember what we are trying to do with this function. If we are adding numbers together to get a sum, then adding zero won't affect the sum and will allow us to stop execution by using the return statement!
Part II - Creating the Recursive Case
Alright campers, buckle up. This is where things often get a little wild.
With our recursive case, all we want to do is come up with a set of repeatable instructions that move us closer to our base case. The one caveat is that this part needs to include calling the function we are currently writing.
Let that settle in for a second... Great. Now that we've addressed it, let's focus on making it seem a little less wonky.
So if we look back at our base case, we are trying to get to a place where we no longer have any numbers to use for our recursive case. Sounds like we need to do some manipulating of the numbers array that we are feeding this function.
Also, we want to keep our eye on the prize - what are we trying to do? Add numbers! OK, what is easier...
- Adding two numbers together?
- Adding more than two numbers together?
This is an important concept of recursion. Being able to break the problem down into the smallest, simplest form will often allow you to write more simple, repeatable steps that make recursion an excellent tool for the job!
So, if all our function does is remove a number and add that number to another number, we can start to break this down recursively!
//create a function that takes in an array of numbers
//create a base case
//when there are no more numbers, stop executing
//create recursive case
//take out the first number and store in variable
//add that variable to the result of calling the function recursively with the remaining numbers
Essentially what our recursive case will do is remove one of the numbers and add it to the result of the next call.
But what is the result of the next call?
Well, simply put, it will be the next number that we remove! All this recursive function will do is remove a number and add it to the next number until we have no more numbers to add. It might look a little something like this:
const getSum = numbers => {
//base case
if (!numbers.length) {
return 0
}
let firstNum = numbers.shift()
return firstNum + getSum(numbers)
}
Whoa. That might seem like a big step, but let's break it down how it's working step by step.
One thing to be aware of is that each time we make a recursive call, it gets added to the call stack. Think of the call stack like a Pringles can - the first chip that goes in is the last chip that is taken out. So in our example, the first call that is added to the stack is the last one that will be executed.
If this part feels a little fuzzy, that's OK! The JavaScript call stack is a really tricky concept, but there are ton of great resources out there to help understand it better, including this awesome video.
- When we first call the function, we are removing the number
1and adding it to the recursive function call with our remaining numbers, like so:
//1st Call
// 1 + getSum([2, 3, 4])
- We still have not hit our base case, so we continue our execution by removing the first number, in this case
2, and adding that to the result of our upcoming recursive call, like so:
//1st call
//1 + getSum([2, 3, 4])
//2nd call
// 2 + getSum([3, 4])
- This will repeat until we have no numbers left and we hit our base case. This will look like:
//1st call
//1 + getSum([2, 3, 4])
//2nd call
// 1 + 2 + getSum([3, 4])
//3rd call
//1+ 2 + 3 + getSum([4])
//4th call
//1 + 2 + 3 + 4 + getSum([]) <- triggers our base case!
//5th call (triggers base case!)
//1 + 2 + 3 + 4 + 0
- Now, the call stack will resolve the same way we would eat chips from a Pringles can - pulling the top layer off and working our way one level at a time until we get to the bottom! So this would look something like this...
1 + 2 + 3 + 4 + 0
1 + 2 + 3 + 4
1 + 2 + 7
1 + 9
Result = 10
Congrats! We have written our first recursive function!
Recursion Example without Math!
If you're like me, I imagine you've been doing quite a bit of Googlin' to start building your understanding of recursion. One frustration I encountered was most of the example problems dealt with mathematical concepts like the Collatz conjecture, the Fibonacci sequence, etc. Unfortunately, these problems provided a barrier to entry of sorts for me because I had a hard time teasing out the WHAT I was trying to do while also learning recursion. So, let's try a non-math problem that we can use recursion to solve!
Write a function called `isPalindrome` that takes in a string.
Using recursion, determine if the string is a palindrome - a word that reads the same forwards and backwards. A few conditions to be aware of...
- An empty string can be considered a palindrome
- A single character can be considered a palindrome
OK - so remember, for any recursive function we need:
- A base case
- A recursive case
We need to figure out how we can start to determine if the string is a palindrome. To accomplish this recursively, it's best to try to break this problem down into small, repeatable steps.
When I think about this problem, my approach would be to compare the first and last letters of the string to determine if they are the same. If they are, we can move inwards from the front and back and compare those letters to determine if they are the same. If we do that all the way through with matching letters, that means we have a palindrome.
But if anywhere along the way they are NOT equal, that means we cannot possibly have a palindrome.
Alright, now what about the recursive case. Well thankfully, this problem gives us some big hints that can lead us to the base case. If our string is either empty (no letters) or is one character, that means we have a palindrome. So we can wait until we get to zero or one character remaining and kick out of our recursive function!
Before we dive into the actual syntax, let's capture our approach in some psuedocode so we have a strong plan of attack.
//isPalindrome(string)
//base case
//if the string is either one letter OR an empty string
// return true
//recursive case
// grab first letter
// grab last letter
// if the two letters are the same
//return isPalindrome with the remaining letters
//otherwise, return false (can't be a palindrome)
Part I - Base Case
Based on our psuedocode, this should be fairly easy to translate into actual syntax.
const isPalindrome = string => {
//base case
if (string.length <= 1) {
return true
}
}
Part II - Recursive Case
There are a few more moving parts in our recursive case compared to our base case. We need to figure out how to do several things...
- How to capture the first letter from a string
- How to capture the last letter from a string
- How to capture the "remaining" letters from the string we are manipulating.
Time to hit the ol' Googleator! After about 5-10 minutes of reading the documentation, I've found a few tools that can work for our given psuedocode.
- I can use the index position of
[0]to capture the first letter of the string - I can use the index position of
[string.length - 1]to capture the last letter of the string - I can use the substring method to capture the "remaining" letters of the string after comparing the first and last letters from steps 1 and 2. Specifically, I will need to feed this method the following arguments:
-
1- the index I want to start on (since we captured the first letter with[0]) -
substring.length - 1this will capture the remainder of the letters remaining in the string
-
Now we have all the necessary tools at our disposal to implement our recursive case!
const isPalindrome = string => {
//base case
if (string.length <= 1) {
return true
}
//recursive case
let first = string[0]
let last = string[string.length - 1]
let remaining = string.substring(1, string.length -1)
if (first === last) {
return isPalindrome(remaining)
}
return false
}
To prove this works, let's run my favorite palindrome through our brand, spankin' new recursive function... TACOCAT!
And voilà! It works! Hopefully, this article allowed you to start understanding recursion just a little bit better.
However, recursion is definitely a tricky topic and will take a lot of practice to really feel comfortable with - so keep at it and you'll be a Recursion Rockstar before you know it!
Top comments (1)
Nice post!