Last time, we learned how insertion sort of works and we discovered it's an order and squared algorithm. This time, we'll step away from sorting for awhile and talk about something called recursion. There is a recursion reading included with the lecture resources for this lecture. Here's the big idea. There are some problems for which we can formulate an elegant solution by writing a function that calls itself. If you've written functions that call themselves up to this point in the course, you've probably done it by a mistake. When we implement recursion to solve a problem, we're doing it on purpose. There are some constraints. The first is, we need to be able to solve the problem by having the function call itself with a smaller version of the problem. We can't have the function call itself with a bigger version of the problem because then it will never stop. It will just keep growing. We need it to get smaller each time the function calls itself, which leads us to the next constraint. There has to be some termination condition which is sometimes called the base case for the recursion. There has to be a place where the recursion stops where we don't have to call the function again with a smaller version, where we can just solve the problem all at once and return that answer. Let's go see how we can solve the factorial problem recursively. For our first example, we'll look at how we can calculate factorial using recursion. So the factorial of a particular number is defined as, that number times every number less than that, down two and including one. So we only calculate factorial for positive numbers and will see how we can actually calculate factorial using recursion. I have a function prototype for my factorial function and we will pass in the n for which we want to calculate factorial. I've also implemented a function that calculates factorial by looping just to show you that we get the same answer but we won't go over that function in this lecture because we're focusing on factorial, but it is in the code that I have provided to you. We initialize n to zero and while n is greater than or equal to zero, so the user will enter a number and will calculate its factorial and the user will eventually quit by entering some negative number. If n is greater than or equal to zero, so when they quit they'll enter a negative number and we don't want to try to calculate factorial of that number but if they've entered a number that's valid for us calculating factorial, we call our recursive function and then I call the other one just to show you we're getting the correct answer. So let's go look at this recursive function, and here it is. The first thing we check within this function is if we've reached the base case or termination condition. Now, I said we multiply all the way down to one but the mathematicians actually have defined zero factorial as one as well. So we'll go all the way down to zero. We'll go with the mathematicians. So our base case is, when we're trying to calculate the factorial of zero. When we're trying to calculate the factorial of zero, we just return one because that's what the mathematicians tell us zero factorial is. If we are above zero, then we're not at the base case yet. So we go into our else clause and we return n, the current number, times factorial of n minus 1. So let's use five as an example. Five factorial is 5 times 4 times 3 times 2 times, times 1 if we include zero factorial. But another way to think of that is five factorial is also 5 times 4 factorial and that's what gives us the recursive solution here. Remember, we're solving instances of the problem that are smaller than this one and certainly calculating four factorial is smaller than calculating five factorial. This line of code is, if n is 5, this line of code is 5 times 4 factorial. Let's actually watch this in action. I'm going to run it to show you that if I enter five for five factorial, it's 120 and if you do that calculation 5 times 4 times 3 times 2 times 1, and you can multiply by 1 again if you want, it's actually a 120. I'll enter a negative number to quit. Let's use the debugger to watch what's really happening here. I'll set a breakpoint at our base case or termination condition return and I'll set a break point here, if we're going to recurse again. This time instead of running with control F5, I'll run with the F5 because I want to use the debugger and I'll enter five again so we can watch that example run. We've hit this breakpoint right here. As you can see on the lower left, n is five because we passed in five and over here on the right our call stack shows that initially, the operating system called the main and then from within main, we called factorial and this is the call that we're on right now. It doesn't actually show what value we passed in as n, but we know from looking over here to the left that that value is five. So we're going to recurse again. I will press F5 and we've broken again. You can see this time n is four and you can see on the call stack that we have another call to factorial this time n was four. I'm going to do F5 several more times. The next time we break up above, we've actually reached the base case or termination condition because n is zero, so we're just going to return one. Notice over here that we have a bunch of calls to the same function time after time. We called it with n equal 5, and then n equal 4, and then n equal 3, and then n equal 2, and then n equal 1, and now we've called it with n equal 0. Now, if I F5 again, you can see that we return from all of those function calls, returning the final answer and that final answer is a 120. So when we returned from calling factorial with zero, we had one on the right hand side here and in that particular case, n was 1. So we had 1 times 1 that we've returned to the function call that had n equal to 2. So this is one and then we multiply 2 times that 1, so now we have 2 and we return that and multiply by 3 to get 6. We've returned that and multiply it by 4 to get 24 and return one more time and multiply 5 times 24 to get a 120. To recap, in this lecture, we learned what recursion is and we learned about the two constraints we have on recursion. We also saw how we could solve the factorial problem, recursively.
