Understanding Recursion: A JavaScript Example

sometimes in programming problems that are difficult can be made easier by breaking them into smaller parts recursion is such a technique you break a problem into a small part that is repeatable and then you repeat that small part in order to solve the larger problem in this video we're going to take a look at recursion using a JavaScript example and help to understand recursion sometimes recursion is not as simple to understand as a loop it's a similar concept you're looping through the same process but there are some unique differences that make it a little bit more difficult to understand so let's first take a look at some concepts that help us to understand recursion first a recursive function simply calls itself that's really the definition of a recursive function of is it's calling itself and then another important concept is a recursive function it has two main parts and let's take a look at what those two parts are first there needs to be a terminating condition and this is sometimes called the base case this terminating condition is what causes the function to not be called again otherwise we would continue to call that same function over and over and of course would be in an infinite loop that would give us all kinds of headaches now the other main part is the recursive case this is the portion of the function that calls itself so both of these parts are important when you're setting up a recursive function now recursion can be very effective in manipulating tree structures such as XML or the Dom or even a tree structure of an object composed of other objects and the reason this can be effective as each call gets a smaller piece of the tree structure to work on now for this video we're going to be doing a factorial problem because I think it's easier to demonstrate how recursion works with this particular problem where we're simply working with numbers now for those of you have been away from math class for a while factorial is simply the product of an integer and all of the integers below it so for example factorial 5 is equal to 5 times 4 times 3 times 2 times 1 now this can be solved with a loop obviously but it also is a great case to solve it with recursion so that's what we're going to do so let me jump to sublime and we'll set that up first and then we'll describe how it works to help with the understanding of recursion all right so first let me set up my function I'm going to assign it to a variable factorial so here's the structure of our function now what I'd like to do first is take a look at the recursive case remember that is the portion of the recursive function that calls itself now with this function we're going to pass in a number and then whatever number is passed in will return the factorial of that and so to simplify that problem this is really a matter of multiplying the number by the number that is one less than that and repeating that small piece of code multiple times so that's decomposing the problem into a small subset and then we can repeat that subset which makes it ideal for Persian so if we just look at that small subset that would be returned num times num minus 1 now obviously that's not going to give us that true result unless the number passed in is - anything about - we're just going to get the first two numbers multiplied together so the way we can repeat that using recursion is to call a function again using the second number so multiply number by no minus 1 but do a call to the function now in order to be able to call the function it's a good idea to give your function a name right now we have a function expression it's assigned to a variable factorial but it's unnamed we can create a named function expression or we could simply do a function declaration either way that would assign a name to our function and that's the best technique for calling a function from inside itself so let me put the name just FAC it could be exactly the same as the variable but I want to use a different term for purpose we'll see later when I'm illustrating how this works so now we have a name associated with our function we can call it again with a smaller number so what's going to happen here when this function is called it's going to return number x but then it's immediately going to call a function again and so that's going to come up and call itself so be number times num minus 1 then it's going to immediately call again and so it will go through that and it will continue to go through that forever unless we include a terminating condition so let's add that up here now that condition should be if num is equal to one that's when we want this to end now how can we terminate this well when num is equal to one we can simply return one because that's what should be returned to anyway we can simply return one and without calling the function again that's going to put an end to our recursive calls here we're returning a number and then calling the function again here we will just return the number and that will put an end to it alright now let me just add a few lines so we can see what the final result is and we'll just pass in a five a factorial of 5 we'll use work with a simple number here and I'll just log that to the console so we can see what the result is let me save that and let's jump out and refresh our page and then show the console and there we see the number it returns is 120 which is the factorial of 5 1 times 2 is 2 2 times 3 is 6 6 times 4 is 24 then 24 times 5 is 125 the sublime again and let's decompose this a bit and see what's happening as this function executes so the first time through number equals 5 it returns num but before it can return the final results it invokes another function and the function that it invokes happens to be the same function we're in and this time it passes in a 4 so that case it returns a 4 but before it's able to return the final result it invokes a function again this time with the 3/3 before it's able to return the final result of focus again to a 2 and then to a1 and when it says it's equal to 1 it simply returns 1 because another function is not invoked at that time it is able to unwind the stack and return the final results so each time a new function is invoked it's added to the stack and so we have multiple things in the stack once it stops invoking another function then it's able to unwind that stack and return the final results by multiplying all those numbers together all right let's look at what I just described illustrated textually so first time it's called this is what we get 5 times and then invoking fact with a 4 and so now we have this and then this so 5 times 4 times 3 times invoking the function again with it two and then invoking it with the 1 and that returns a 1 at that point we get this and this is where it begins unwinding the stack it multiplies 1 by 2 gets a 2 multiply 3 by 2 gets a 6 4 by 6 gives a 24 5 by 24 and we get the final results and that's what gets returned and placed in the variable so that's what's happening in our function that's how recursion is working now let's try one more way of illustrating this to make sure it's understood so I'm going to put a break statement and open up the debugger and we'll follow this through in the debugger so let me access the console I'm going to I'm going to go to the source here that's the line I want to pause on within the debugger now let's go ahead and refresh our page and it stops right there now I'm going to bring this part of the debugger up so we can see what's going on over here and the call stack is the part I want you to pay attention to as well as what the number variable is equal to each time this function is called right now it's equal to five this is the first time it's called and we've had it pause at this line here so num is equal to five and that's showing down here in the scope as well we've called it once so it's showing once in the call stack let's step through the code execution smart so I've caused it to move to the next call now we're seeing a call stack we have this function called twice so initially the function was called anonymously which is right here that's where the call happened the function is assigned to this variable factorial was invoked and then from there it is begun to call itself using the name we assign to the function FAC so we're seeing that show up twice now in our call stack also notice that the second time through num is equal to four and that's showing in the local variable here as well so let's keep moving through this there's three times it's going to be called four times before it begins unwinding the stack so right now num is equal to two next time num will be equal to one and it's simply going to return 1 it will not call itself again let's see how that works so now num is equal to 1 it returned it and so now we're down here at the bottom of this function so we're waiting for the return value which it needs to return to this variable final so in order to get that return value we need to unwind the stack so let's see how that's done and notice how the return value increments as we do that right now two times one it's working on the return value so two times one is equal to two and then six because we multiplied the three n notice num is equal to three then 24 and then 120 and now we're ready to return the value so we unwind the final and we can just resume the execution and we should get 120 at the console so that's another way to see how recursion is working I hope you found that helpful I hope that help demystify recursion a bit for you if you found this tutorial helpful I'd appreciate you liking the video you can also click the video link in the middle if you'd like to view another video from our YouTube channel to subscribe to our YouTube channel click the circle link on the left we have a new video each week and to visit our website where we have courses and other resources on JavaScript you can click the link on the right thanks for watching

Channel: All Things JavaScript, LLC

Views: 24,627

Rating: 4.9607143 out of 5

Keywords: JavaScript, javascript questions, javascript tutorial, getting started with javascript, learning javascript, javascript fundamentals, javascript instruction, javascript training, all things javascript, javascript for beginners, beginning javascript, recursion, factorial, function expression

Id: py7ZWFjrwEs

Length: 14min 58sec (898 seconds)

Published: Thu Mar 30 2017