In this lecture, we'll learn about something called recursion. So what is recursion? It's a technique that we use to solve a problem, by solving smaller versions of the same problem. The other characteristic of problems that are well-suited to be solved using recursion, is we need to have a base case, or a termination condition to stop the recursion. In other words, a version of the problem that's small enough that we know the answer, without trying to solve even smaller versions of the problem. How do we do recursion in C#? Well, we have a method call itself with a smaller version of the problem that we're trying to solve. And we also have the method recognize the base case, so it can stop recursing, and return the answer back up. So we can finally build the final solution out of the solutions to the smaller versions of the problem. Why do we care about recursion? Well, recursion is really useful when we traverse trees. So we'll see ourselves using recursion both in our implementation of the tree class, and as we learn about traversing and searching trees. I'm using Visual Studio for this lecture because I can use the debugger in a console app to show you what's happening with the call stack. I can't do that with MonoDevelop, because the MonoDevelop that ships as part of Unity, the debugger doesn't work in the console apps. So just for this lecture, I'm using Visual Studio. So let's look at our factorial method that works recursively. Here it is, it's a very short method. What we do, is we pass in an n, the number for which we want to calculate the factorial. And if n is equal to 0, then we're going to return 1 because the mathematicians have told us that 0 factorial is 1. And if it's not, then we're going to return n times factorial of n minus 1. So, if in fact we're calculating 5 factorial, and we call this method with 5, then we will return 5 times 4 factorial. And then it will be 4 times 3 factorial and so on, until we get all the way down to n equals 0, and that's our base case, or our termination condition. So let's watch how this works. I'm going to set a break point here. And up here in the main method, we're going to just provide an n, and then it will calculate to the factorial for us. So, I'm going to run the code using F5, not Control-F5, so I'm using the debugger. And I'm going to enter 5 factorial. So as you can see, we hit this break point and n is 5 here. And down here in the call stack, we have just added this call to the factorial method. Now, I'm going to F5 again, and as you can see, n is now 4. And our call stack includes the first call to the factorial method, and the second call. And I'm going to F5 so n is 3, and F5 and n is 2, and F5 and n is 1, and F5 and n is 0. So here you can see n is 0. And here in the call stack, you can see all these calls to factorial. So an interesting tidbit, is if in fact we end up with infinite recursion, we will just keep calling this method again, and again, and again, never reaching the base case. And so, eventually, our call stack will get filled up, and the stack will overflow. And that's why the StackOverflow website is named StackOverflow, because you go there when you have programming problems. And overflowing the call stack with infinite recursion would be a programming problem. Okay so now we have reached our base case. So I'm going to step instead of F5, I'm going to step, And as you can see I'm going to return 1. So if I F10 here, I get to the end of the method, and I've just removed one of those calls from the call stack. I just returned 1, and returned back here, so n is 1. And I've just returned 1 from the call to factorial with n of 0. So as you can see, once I come out of all of those recursive calls, I get the answer, 120, which is, in fact, 5 factorial. So I'll exit out of here by entering a negative 1. So the big ideas here in this recursive method are, I can keep breaking the problem into smaller versions of the problem to try to solve it, as long as there is a base case, or a termination condition that I get to to stop the recursion. To recap, in this lecture we saw how we can do factorial calculation using recursion, and we also learned that recursion will be useful as we work with trees. And you didn't necessarily learn that, I just told you that. But trust me, it's true. And we'll see that it's true in a few lectures.
