Recursion

[00:00:00]
>> WebDevSimplified: Now moving on, we are going to move on to what is hopefully the very last really confusing topic in this workshop, and that is the idea of recursion. And recursion is a function that calls itself, which sounds really confusing, but let me try to break down exactly what's going on. We have an example here that's called print numbers. It takes in a number and then it's going to later on call itself.

[00:00:20]
Let's copy over this code to see what it actually looks like when it's printing out this. That's going on. You can see this code prints out 1 2 3 4 5 6 7 8 9 and 10. So it's at least printing out some stuff that makes relative sense to us. It's printing out a list of 10 different numbers. So now let's break down how that actual code works. First of all, we call print numbers with the number of 1. We then check here if the number is greater than 10.

[00:00:42]
It is not, so we skip this section completely. Whoops, and we move on down here where we log out our number, which is 1, and then we call the print numbers function again by adding 1 to the number. So we're calling print numbers with 2. We will then start back at the top of this function because we're recalling it from itself. Is 2 greater than 10? No, it's not. So we log out 2 and call it with 3.

[00:01:02]
We then continue to do this with 3 4 5 6 7 8 9, 10 until we get to the number 11. 10 plus 1 is 11, so we call this with 11. 11 is greater than 10, so now we use this return to exit out of the function to stop calling itself. And this is a very common pattern inside of recursion. You're essentially going to have two main parts in your recursion. You're going to have a section that allows you to break out of your recursion, some type of check that ends the calling of your function, and then you're going to have the recursive part where you call that function over and over again.

[00:01:35]
Now this is a relatively confusing topic to understand, so I have a few little, I don't want to call them diagrams, but a few different ways that kind of explain what's going on. Like I said, we have our base case, that's what stops our loop from running, and then we have the ability to actually do the recursive, which is just calling that loop over and over again, calling that same function. Now if you forget to put in that base case, that stopping condition, you will get an error because you're going to be calling the same function infinitely a number of times.

[00:02:01]
It's essentially the recursive version of an infinite loop, and your code will throw an error, usually it'll look something like range error, maximum call stack size exceeded, something along those lines. Now I want to understand how this actually works because this plays into something called the call stack. The call stack is just essentially a list of all the functions that you've called and the order that you called them if you get to where you are.

[00:02:23]
So here we have a function called countdown, which takes in a number and it logs out what that number is. And if that number is less than or equal to 0, that's our base case that allows us to stop executing the code. Otherwise we call that countdown function again with a smaller number. So we pass in 3 for our countdown, it should log out 3 2 1 0, and then boom, the countdown is completely done. But I added in these before and after logs so we can really see what's going on inside of our code.

[00:02:50]
Let's just copy this and actually run it inside VS Code so we can see what the output is, and you'll notice the output logs out 3, and then it logs out the word before. It then logs out 2 and before. It logs out 1 and then before, and finally it logs out 0 before logging out the after word 3 separate times. This is what makes recursion really difficult to understand. Essentially what we want to think about is we call countdown with 3, so we're inside of our countdown function and it's obviously not less than or equal to 0, so we can kind of potentially pretend this line doesn't exist.

[00:03:22]
So all our function does is call a log of 3, log out the text of before, which, as we've seen is exactly what happens, and then we call countdown again. And instead of continuing the rest of our code, we stop our code right here because now we've called a new function. So we start back at the top here, but now our number is 2, so we log out 2, we log out before, and again we get to countdown and we stop right here again.

[00:03:45]
So now we go back to the top. We call log out 1, call before, call our countdown again. Back to the top, we call it with 0, and finally here we get to our return statement. This is what stops all the rest of our execution. And you may remember earlier when we hit a return statement, that means that we exit out of the function and we continue on with the rest of our code. So when we hit our first return statement, we go back to where we called our countdown function right here, which was where we called it with the value of 0, and then we log out the text of after.

[00:04:13]
That ends our function, which is essentially the equivalent of calling return. So we go to where that function was called, which is right here. We call the countdown right here. So now we finish that one where it logs out after. This happens again because we end that function, we log out after, and finally we've exited out of all the different functions that we've called inside of each other. So now we go to where we call the original countdown function.

[00:04:35]
That's why it logs out after 3 separate times down here because we've called this countdown function multiple different times, we called it 3 separate times, and we need to make sure we finish the function every single time we go through it. A little bit of a visual of how that looks, we kind of have this nested visualization. You can see when we call countdown with 3, inside of that we're calling countdown with the value of 2, so we can kind of nest them inside of each other.

[00:04:59]
Inside of countdown of 2, we're calling countdown of 1, so we nest that one inside of itself as well. Finally, inside countdown 1 we call countdown 0, so we nest that one step further. And this one just returns. There's no more recursive calling going on. So now we go back up that nested chain. So we go back to countdown 1, which exits out. We go back to countdown 2, which exits out, and finally we get to countdown 3, which exits out, and that brings us back to our code where we originally started.

[00:05:23]
So this recursion essentially you just nest yourself deeper and deeper and deeper, and then to exit out you have to burrow yourself back up through all the different levels of nesting that you went through. Now recursion is something that again, when would you want to use this? It's mostly useful when you have like tree-like structure, kind of like how you could use a while loop. Recursion is another way to solve very similar problems that while loops would solve.

[00:05:44]
For example, here we have a file system and we want to be able to get all the files inside of here. So some of these things are folders with children and some of them are going to just be files. So we can use recursion to essentially count all the different files we have. If our file here is of the type file, we just add one to our count. Otherwise we can loop through each one of the children and count the files for them.

[00:06:06]
So this is the same thing as when I have that while loop with that friends array. It's the exact same thing. If we have this nested style of tree-like data, this is a very common use case where recursion may be a solution. But the important thing to know about recursion is it doesn't matter if you use recursion, a for loop, a while loop, you can use all three of them to solve the same problem. Some problems are just easier to solve with recursion, some are easier to solve with for loops, and some are easier to solve with while loops.

[00:06:33]
I would say I recommend just going with whichever one feels the most natural to you, and as you start to work on more complex things, you may find cases where you're like, you know what, this makes a lot of sense to use recursion for. I'm going to try recursion for this particular example. Now I've already talked about how forgetting the base case is a very common issue for causing an infinite loop, but you can also cause an infinite loop by not actually moving towards that base case.

[00:06:57]
So in this example down here you can see we call our countdown of n, and we're just passing in that same value of n. We're not subtracting one from it or adding one from it or anything like that. You can see here we're always making sure we get closer to that base case by subtracting one, but here we never get closer to that because we're calling it with the exact same parameter, which will be another infinite loop that we would cause.

[00:07:17]
Now for this one, since recursion is so important, I just have a real quick exercise I want us to go through. Essentially, I want you to create a recursive function that finds the maximum value inside this nested array. So you can see we have arrays that have arrays nested in them and arrays nested in them. So essentially you should recursively loop through this set of arrays to find whatever the maximum value is and return that.

[00:07:39]
And a key thing is you can use a function called Array.isArray, pass it in any object, and it'll tell you, is this an array true or it'll tell you false if it is not an array. It's an easy way for you to check if you have an array or not. So hopefully we had some time to go through this particular exercise. If we look at the quick solution for this one, it's a little bit more complex than some of the other stuff we've looked at, but essentially we want to create a findMax function.

[00:08:03]
That's our recursive function that we continually call through. We define a maximum value. We set that to negative infinity, just essentially a really small number, and then we're going to loop through our array. I'm using that constant item of loop style, so the for of loop. Inside this loop we have a simple if check. If the value we're looping through is an array, well then we know we need to loop through it again.

[00:08:24]
We need to recursively try to find the maximum value. So we call findMax by passing in that array that we know we have, and that'll hopefully give us a new individual maximum for that individual array. So here's our new maximum, and there's a fancy function in JavaScript called Math.max which will just return the larger of two numbers. So whether it's our current maximum or the maximum of this smaller sub-array.

[00:08:46]
Then if for example, none of this is true, we don't have an array, we just have an individual value, we can just use that individual value to get essentially the number and this is our base case because you'll notice in this else statement we're not actually calling the findMax function anymore. So you need to make sure somewhere inside your code there's a branch or a case that does not recursively call the function to make sure you avoid that infinite loop.

[00:00:00]
Finally, at the end of all that, we just return that maximum value back down to the user, and this will properly return us the value of 7.