‫So in this video we're going to use recursion to solve for a factorial.
‫So this four with an exclamation point is four factorial.
‫So if you've never seen a factorial before, four factorial is four times three times two times one.
‫So I'm going to move this up here and we're going to look at why a factorial is a great thing to solve
‫with recursion.
‫So if you take these three numbers here three times, two times one, that would be three factorial.
‫So that means that four factorial is equal to four times three factorial and three factorial is equal
‫to three times two factorial, and two factorial is equal to two times one factorial.
‫But something different happens when we do one factorial.
‫One factorial is one.
‫So this is our base case.
‫So there are two requirements for recursion.
‫First, the process that we're doing each time that we call the function needs to be the same.
‫And you can see that we're doing the same thing over and over here.
‫And the second requirement was that each time we need to be making the problem smaller.
‫So I'm going to take these numbers and shrink them down into the corner and just bring in all of the
‫code for factorial.
‫It is just these lines.
‫So we pass it an integer.
‫N in this case that's going to be four.
‫We're going to check to see if N is equal to one.
‫So this will be this one here.
‫And when we return, one that's going to be this one here.
‫And if N is not equal to one, we'll return in times factorial of N minus one.
‫And this is where the function calls itself.
‫So in this case in is equal to four and then in minus one is equal to three.
‫So now let's move this up into the corner and walk through this.
‫So we start out with factorial of PN, which in this case is four.
‫So the first thing we're going to do is check to see if MN is equal to one.
‫And in this case, in is equal to four.
‫So the conditional in this if statement will be false.
‫And then we move down to here and then we're going to say return in times factorial of MN minus one.
‫So that's going to be four and three.
‫So now we have a new instance of the factorial function added to the call stack.
‫And in this instance, the first line will run is this line is in equal to one.
‫Well, now it's equal to three.
‫So we're going to come down to this line.
‫So now in this case in is three in minus one is two.
‫So we'll do this check again if an is equal to one and is equal to two.
‫So this is going to be false and we're going to come down to here.
‫So now N is equal to two and n minus one is equal to one.
‫Now, for this instance of factorial in is equal to one.
‫So we're going to return one like this, and that's going to be this one here.
‫So now let's take a closer look at just these lines and we'll spread these out a little bit.
‫When we say return one on the bottom here.
‫Where is it returning it?
‫It's being returned to this instance of factorial, because factorial of one is going to be equal to
‫one.
‫So it's going to return it up here.
‫And this return statement is returning to this instance of factorial and this return statement is returning
‫to this one and so on up the line.
‫So now let's take out the arrows and walk through this step by step.
‫Factorial one is equal to one, two times one equals two and factorial two.
‫That's equal to two.
‫That's where you return.
‫This two, three times two equals six and factorial three is equal to six.
‫That's what this is getting passed up to four times six equals 24.
‫And we return this to the original function call.
‫So now let's look at this same thing a couple of different ways.
‫Let's use the example of a gift box.
‫But instead of looking for a ball like we did a couple of videos ago, we're looking for the number
‫one.
‫This gift box does not contain a one.
‫It contains a four.
‫So that means that this gift box contains another gift box.
‫This one doesn't contain a one either.
‫So that means it contains another gift box in this case is going to be two.
‫And this gift box contains yet another gift box.
‫But you can see that this gift box is different.
‫This is going to be the gift box that contains the one.
‫This is the base case.
‫This is the equivalent of finding the ball.
‫So it's going to return the one back up to this instance of the function factorial this function right
‫here, and two times one is two that gets returned up here.
‫That's going to be this function of factorial two and then three times two is six, six gets passed
‫up.
‫That's going to be this function, four times six is 24.
‫So now let's look at this a third way.
‫I'm going to bring up the call stack.
‫We talked about a call stack in the last video.
‫We're going to run factorial four and that's going to add an instance of the factorial function to the
‫call stack and then will say return four times factorial three.
‫That adds another item to the call stack.
‫This is another instance of the function factorial.
‫So in the last video we were seeing function one, function two, function three.
‫In this case, both of these functions are named factorial, and then we'll do this again and add factorial
‫of two to the call stack and then factorial of one to the call stack and factorial one is going to return
‫one.
‫And once it does that, it's done running and it gets popped from the call stack and now we can return
‫three times factorial to we pop that from the call stack and so on, and then finally factorial four.
‫We return 24 and pop that from the call stack as well.
‫So now let's flip over and take a look at this NVS code.
‫So what I've done here is I've created a breakpoint and I've already started running this.
‫I came up here on the dropdown and I selected Debug C and C++ file.
‫I've already done this step and I am skipping a couple of steps here, but we covered this in the last
‫video and you can see that Main is already on the call stack.
‫So I'm going to come up here and this button step into when I click on this, it's going to run this
‫line here and it will add an instance of factorial to the call stack.
‫So I'm going to click on this and you can see that Factorial has been added to the call stack.
‫And so that is factorial being run with a value of four and it's going to check to see is in equal to
‫one.
‫It is not.
‫And that would come down here and this will add another instance of factorial.
‫So we'll click on this and you can see that we have another instance of factorial.
‫I'm just clicked through this a couple more times.
‫This is with two.
‫So N is not equal to one.
‫And we come down here and then we'll add our final instance of factorial when I click this again, when
‫it runs this and we have four instances of factorial.
‫So this is what we just saw in the animation of the call stack.
‫And now for this instance of factorial that we just added in is equal to one and we return one.
‫So when I click on this, it's going to jump down here.
‫And when I click on this again, that top instance of factorial is going to be popped from the call
‫stack.
‫So I'll click on this.
‫And now we only have three instances of factorial on the call stack.
‫So in the last video we had separate instances of functions on the call stack, but they all had different
‫names.
‫They were different functions with recursion.
‫We're putting functions with the same name.
‫The same function is being called over and over and added to the call stack.
‫So now I'm going to come over and click on this button and you can see it says Continue.
‫When I click on this, it'll just play this to the end instead of doing this line by line.
‫So I'm going to click on this and you can see up here we get our value of 24 returned and with that
‫it looks like we have a working recursive function for factorial.