Algorithms in JavaScript
Refactor a Loop in JavaScript to Use Recursion
Recursion is when a function calls itself. This self calling function handles at least two cases, the recursive case and the base case. People seem to either love it or hate it because it can be difficult to understand and implement correctly. Let’s walk through a recursive function and refactor a loop to instead perform the same result with a recursive function.
Instructor: [00:00] Let's write a counter function. Inside of this function, we'll do a for loop. We'll do let n equals zero. While n is less than or equal to 10, we're going to n-plus-plus. Inside of this, we'll console.log our n. Now, let's invoke our function. Our console.log shows us that we were successful in creating a simple looping counter function.
[00:20] Let's refactor this to use recursion now, instead of a loop. The first thing we'll do is comment out our function call here, and remove our for loop. We're going to return counter n plus one. We'll pass in an n as a parameter to our counter, and then pass in zero to our function call. Recursion, simply put, is when a function calls itself.
[00:41] As we can see here, we're returning the result of our own function, adding to the argument by one each time. Adding a console.log here with n will give us the same result that our for loop gave us, however when dealing with recursion it's important to understand two concepts of a recursion function.
[00:58] It needs to have at least one base case and one recursion case. The reason why we commented out our function call is if we were to run this function, it's going to enter an infinite loop. This is because we don't have our base case yet. We do if n equals 10, we return our function.
[01:13] Now with that in place, we can invoke our function, and we'll see from our console.log that we get numbers 0through 10 successfully. This is because we have our base case, if-check to stop at 10, and a recursion case to continue until we hit that 10. Now, as a side note, there's no performance benefit to using recursion.
[01:31] In fact, loops are sometimes better for performance. On the other hand, recursion can sometimes be easier to understand. If you struggle to understand what the base case is supposed to be, just think of it as, "What are you trying to get from this recursion function?" In our case, we wanted to create a loop that counted from 0to 10.
[01:49] 10 was the goal, and that was our base case. Let's run another example to understand this. Let's say we had an array of arrays with numbers in them. Our job is to look through the arrays for the number six. If it's anywhere inside of this parent array, then we need to return true, or just the string, yes. I've already gone ahead and traded this function for us.
[02:11] I've called it findSix. It's going to take a list of items, as you can see down here. Instead of that, we're going to say just start off with initially it does not have a six inside of any of the arrays. For that first set of array, we're going to step through each one. We're going to get this first array and the second array inside this first for-each.
[02:30] Then, once we're inside these two arrays, we're going to for-each again, looking for six. If we do have six somewhere in there, as we do on that second inner array, we're going to update our hasSix variable. That's what we're going to return. As you can see here, that we get yes. If I change that to five, our function switches to no.
[02:48] This accomplishes our task, however, it's not very dynamic. Meaning if we were to add this six around another array, inside of here, we'll see that our function returns no when we still have a six in here, and we want it to return yes. In order to accomplish this, we'd have to add another for-each loop inside of here.
[03:07] Where we say if it's an array, we need to do another for-each inside of its contents. Instead of adding more and more for-eaches, or another type of loop, we can refactor this to use recursion.
[03:18] This entails getting rid of one of the for-eaches, and adding an additional if check, where we say if A is an array, then we need to call this function again in our hasSix function, passing in this level array, and assigning its return value to our hasSix variable.
[03:33] Now with our console.log, we'll see that we're getting a yes back here, even though we have this third inner array. It stays yes as we remove it, and goes to no if we get rid of the six. Our base case, or the goal of our function, was to find the number six.
[03:52] This was our base case. We're basically repeating this simple logic over and over for the amounts of arrays that we have within our parent array, which makes our function more dynamic. It's why it's said recursion can be easier to read and understand than just using loops.