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.
Hi Tyler, thanks for the course.
Just a FYI: I've been playing around with the final code of this lesson and figured out that final function doesn't work for all arrays. e.g. findSix for const items =[[1,2,3],[4,5,[6],[9]]] will return no because hasSix variable will be overridden in consecutive iteration. Don't know if it's the most efficient way, but I merely put if (hasSix === 'yes') return; in the beginning of forEach loop to prevent it from overriding.
@Dr.Emmett it's VS Code. The extension that shows results of console.log right in the editor window is Quokka.js.
''' const somewhere = [6,6,undefined,131212312, 123,123 , 132, '', null, [[8]]];
function findNumber(num, arr) { if(arr === num) return true; if(!arr || !Array.isArray(arr)) return false; for(let i=0; i < arr.length; i++) { if(arr[i] === num) return true; if(Array.isArray(arr[i])) isFound = findNumber(num, arr[i]); } return false; } console.time('test1'); console.log(findNumber(6, somewhere)); console.timeEnd('test1'); '''
Can someone please delete this and the above comment ?!. Thank you.
Good catch @Stanislav, that is a good way of doing it!
Thank you for this useful course. I really would like to know that which IDE you've used in this course materials?
I am using the pro version of https://quokkajs.com/
Thank you Tyler, it is wonderful course, I learn a lot
Thank you Tyler, it is wonderful course, I learn a lot
Hi,Tyler, if I have const items = [[1, 2, 3],[4, 5,[6]],7,[8,9],[10,6]], how can I find all of 6 ?
Hi,Tyler, if I have const items = [[1, 2, 3],[4, 5,[6]],7,[8,9],[10,6]], how can I find all of 6 ?
Adding a 6 in the first array wouldn't work (I think the recursive case wasn't properly handled). So I had to modify the code to this:
const items = [[1, 2, 3, [6]], [4, 5, 5]];
function findSix(i) {
let hasSix = 'no!';
i.forEach(a => {
if (hasSix === 'yes!') return;
if (a === 6) {
hasSix = 'yes!';
}
if (Array.isArray(a)) {
hasSix = findSix(a);
}
});
return hasSix;
}
console.log(findSix(items)); //=> true
https://codesandbox.io/s/recursive-findsix-lo9tb
In a functional style (while returning a boolean), I would do this:
//recursive flatten deep
function flatten(array) {
let flattend = [];
!(function flat(array) {
array.forEach(function(el) {
if (Array.isArray(el)) flat(el);
else flattend.push(el);
});
})(array);
return flattend;
}
const findSix = arr => flatten(arr).some(equals(6));
The poinfree version with ramda and crocks would look like this:
const findSix = composeB(any(equals(6)), flatten);
The video example is missing the base case of hasSix === yes!. Otherwise great tutorial
Thank you for this useful course. I really would like to know that which IDE you've used in this course materials?