We've explored a lot involving both user defined and built in functions in this section. We looked at the function prototypes, function definitions, how to write functions with different return types and different parameter lists. We also looked at how to distinguish parameters from arguments, different parameter passing schemes, and the scope of variables and how this related to functions as well as function overloading. In this lecture, we'll round out our fundamental knowledge of functions with a more advanced topic, the topic of recursion. We know that functions can call other functions. We've mostly seen how the main function calls the other functions it uses, but any function we define can call any other function we define or any built in function for that matter. A recursive function is a special function in which the function calls itself. We will discuss the need for both recursive cases and base cases in order to create and use recursion successfully. Recursion comes up often in programming, especially with more complex algorithms that process data structures with hierarchical formats. This could include processing entire file systems where there are many levels of files and folders. Recursion is also used in many other situations where an iterative solution that is one that uses repetition control statements or loops that we've discussed before, may not be obvious. Recursion often helps us to take large problems and break them down into smaller and smaller versions of themselves until we consult them. This will start making more sense when we explore some examples. Let's start with a simple example project which we will call countdown. So, we create a new project here. Empty project and we will call this CountDown, very good. Create our default file here, main.ccp and the skeleton namespace, standard, int main, good. Now, we need a function prototype we'll say countDownFrom and then pass it a number and then we will write the definition, countDownFrom int num, there we go. And let's just do this, if num is greater than or equal to zero, as long as the number is greater than or equal to zero, we print out the number and then what we do is we make a recursive call to countDownFrom but with the number -1. Now, we have to call it from main, the initial call. So, we're counting down from 10. Let's run this. And of course it says 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, interesting. No loop involved, right? So, there's no loop here, but it has very loop-like behavior. Whenever we have a recursive function, we need two primary things. At least one base case and at least one recursive case. A base case is a case or range of values in which a recursive call will not be made. If we don't have a base case, the recursive function can never stop running. It's just like with a loop if you don't have the loop continuation condition eventually be terminated, then the loop will keep on running forever. We need at least one recursive case in addition to this base case. So, obviously in order for the function to be recursive, it needs to call itself at some point. The subsequent recursive calls must move towards the base case, that's another condition we need to satisfy. So, for our code and the countdown project, the recursive case for countdown from is obvious. A recursive call in the function itself right here. The number passed into it is greater than or equal to one or to zero rather, so it has to be zero or one or two etc, but it can't go under zero. In other words it would skip over this and not make a recursive call. So, the recursive call reduces the number by one. So, when the call is made again, the number is one less meaning, one closer to the if statements condition being false. That is where the base case comes in. Even though it's not explicitly spelled out here, if the number is passed in as an argument at any point and it's less than zero, we don't print out the number and we don't make another recursive call, so the function will end. So, the base case is actually implicit here. Sometimes it's explicit. You have to spell it out with it if or NFLs or something like that, but in this case it's implied. If it falls out of range on this, this void function will just skip over and then it'll just terminate and then it'll go back up the stack or down the stack which we'll talk about. So, let's trace out how this might work using the function call stack. There's always a call stack, whether the functions are recursive or not. This helps the program keep track of where it left off. Observing the call stack, each of the rectangles that are stacked on top of one another are called activation records or stack frames. These are just two names for the same thing, just like variables which represent data, the functions which represent instructions also reside in memory. In our programs, the function calls are represented by these activation records or stack frames. As a side note, if the stack becomes too full of these activation records or stack frames, it's called a stack overflow, which is why the very popular website is named Stack Overflow. It's where you ask questions about programming and things like that. The call stack is like a regular stack of books or dishes or something like that. It is actually an example of a stack data structure which is a more advanced topic. For now, just know that each of the frames these activation records or stack frames just represent a single call of the function and that whichever frame is on top of the stack is the active frame, the active function. When we add an item to a stack we must add to its top which is called pushing the item onto the top of the stack. When we remove something from the stack, this is called popping the item off of the stack and happens at the top as well. So, all the access on a stack is at the top. In our case, the items in the call stack are again activation records. Let's see what happens as countdown from is called with a diagram. So, we originally have countdown from past with 10 to it, and then that calls countdown from with nine because of the num minus one. Further countdown nine, countdown from nine calls countdown from eight. Then we have countdown from seven, then six, then five, then four, then three, then two, then one and finally zero. After zero is reached, the condition is no longer true and the base case is reached. Then the function calls are popped off the call stack in reverse order of the order they were added. Popping the countdown from zero, one, then two, then three, then four, etcetera etc. Several calls later countdown from 10 which was the originally called function call on main, is popped off of the call stack and then main is left. In our program main is now done. So, then it is popped off of the call stack and the program terminates. Now, you might be thinking wait, I know an easier way to count down, I could just use a loop, and you would be right. In fact a loop is actually a lot better solution for this particular problem. But this example is to simply demonstrate how recursion works. Also note that while recursive functions can have loops in them as well, make sure what you really wanted wasn't a selection control statement like an if statement instead of a loop. The recursion itself takes care of this repetitive behavior, not a loop, so just be careful when you come up with your own solutions. Under most circumstances, in order for a recursive function to work, there has to be at least one parameter passed that helps the function decide whether or not to continue. But the return type can be essentially anything. So, as another quick example, let's modify our countdown application to contain a new function called some values. Again, you could use a loop, but let's do a recursive version of a method that returns the sum of all the numbers starting with the given parameter and ending at one. So, we're just going to add this new function here, some values int num and then we're going to put the definition below main right here, this is one that returns the value, right? That's the value returning function and it just happens to be recursive. And in this case, what we're doing is we're saying if the num is greater than or equal to one, then we're actually returning the number that was passed in, whatever was passed in, plus some values of num -1. So, starting with the number that was passed in it will basically create repetitive behavior using the recursion and it will keep returning this number plus this some values until this is false. When this is false, and we could put an else statement here. But a lot of developers, especially if it's the last statement on the program, if it's the only other possibility, they just forego putting the else because when we get to a return statement in any given call, it will return and it will never get to this anyway. So, it's essentially the same behavior as having an else. Now, we're going to call from main after we have this countdown from 10, I'm going to get this totalSum, sumValues, we're going to get the sum of 10 all the way down to 1. Now, we're going to say, the sum is totalSum and of course let's run this. So, oops, let's change the spelling and then run it. Sum is 55 and you could probably verify this by adding the different numbers. And actually a little bit of a trick here would be since this helps us view what's going on in countdown, in sumValues even though this is from a different function, we know that we went down, we added the numbers down from 10 to 1. If you look at each end of them, so a 10 and a 1 is an 11, 9 and a 2 is an 11, 8 and a 3 is an 11, 7 and a 4 is an 11, and 6 and a 5 is 11 and there are five pairs of 11s so we know that that's 55. So, there's a quick mental math way to do it. It's actually called the Gaussian summation formula in case you're interested, and it's something we talk about in more advanced topics in programming. Very interesting. So, we're not surprised we get the sum that we expect, you can verify that this works for other values as well if you'd like. Before we move on, I'd like to, you guessed it, issue you a challenge. I want you to create a new project called FactorialFun. For this, you will create a function that returns the factorial of a given input value. The recursive definition is a piecewise function, that is, a function with multiple parts in this case two. For our purposes, we will assume that the user will only put in non-negative values. The definition is basically just that n! = n  * the quantity (n-1)!. So, that's where the recursion is. If n is greater than 1 the base case is if n is equal to 1, then we just return a 1. An iterative approach to the solution for a specific example say n = 5 might look something like 5! = 5 * 4 * 3* 2 * 1 and then you get 120. The recursive calculation for n = 5 look something like 5! = 5 * 4!. And then the question is but what is 4!? And then we would say, 'Oh, well that's 4 *  3!." Okay, well, what's 3!? Well, that's 3 * 2!, aren't you listening? And then it's 2  * 1! and then 1! is where we end the recursive calls. We actually give an answer. We say, well, 1! is 1 and then it goes back up the stack and we still get 120. So, we get the same result but the approach to the solution is different. This one's a little trickier. So, do your best, spend some time thinking about the problem. I strongly recommend not skipping ahead right away. Give this one an honest try. Make sure to test it out maybe with the value 5 since we know what that is now or 6. So, go ahead and pause the video and solve the factorial problem with recursion. So, how did that go for you? This one was a bit challenging but we can go pretty directly from the mathematical definition. Let's create the project FactorialFun. First, we have to close this solution first, then we will go to create a new project, empty project, and 'Next'. So, we give it the name FactorialFun and then hit 'Create' and as usual we will create our nice little file here, main.cpp. We will fill in the skeleton code using namespace std, int main and then return 0. And of course we will have our factorial. So, we've got int factorial and that takes an int num and we're going to have to put a definition, int factorial(int num), got that there. We're going to eventually call it from main so we'll do that now and then we'll fill in the code, int factorial of, we'll say 6, will be a little bit more adventurous. Could be 6, could be 5, you can try it with different values. And we'll say, the factorial of 6 is fact6. Oops, that was, let's zoom out. Okay, there we go. And endl. There we go. And now we're going to fill in the factorial function based on the definition. So, the definition tells us that if the number is greater than 1, greater than 1, then we return that number times the factorial of one less than that. So, that's just calling factorial of num-1. So, we basically just took math syntax and we converted it to C++. And then the alternate piecewise definition is if it is not greater than 1, then we return 1. Okay, let's run it. See what we get. So, right here. Factorial is 720 which if you were to go through, you could find out 6 * 5  * 4  * 3  * 2 * 1, that would be the way a human would do it and actually how an iterative approach would work with the repetition control statement. So, we get the solution we expect. The best case is the case with no recursion again. So, that's the case where n = 1. If n is 1, we return 1. Otherwise, we make a recursive call that is, we return whatever value our current n is and then multiply that by factorial of n-1. At each recursive call, the value that is being returned must wait on the next recursive call at each value of n or num in our case. Until the non-recursive call that returns the value of 1, this right here is reached, then the recursion stops and each level gets the value it was waiting on. So, the call we make in main finally gets the final value and that is our solution. How cool is that? We're done with the formal lecture material in this section. Over the next few lectures, you'll be working on some projects involving functions and ramping up your skills a little bit and then there's a very challenging project near the end. It's the hardest challenge you've had, hardest project you've had in this entire course so far, it's called Tic Tac Toe, let's get going.