[MUSIC] So we explained a very simple idea behind recursion, how recursion can work in place of iteration. Sometimes you should prefer one to the other, but you should know how to work with either scheme. And we're going to show both schemes now in computing n factorial. So n factorial is a mathematical quantity [COUGH] how to build especially large numbers. And it's defined as 1 * 2 * 3 * 4 etc, up to n. It then gets large, this gets extremely large. So for that reason, we're going to use the long int. because if we use a shorter int, we can't actually compute it for too long. Actually long only allows it to work for up to 20. What happens past 20? You get what's called integer overflow, you get results that are incorrect. Because the number of bits of available in a long on most machines is 8 bytes, 64 bits. And so for an integer type, it only able to represent factorial up to 20. So let's look first at something we should be comfortable in. We're going to do factorial iteratively, and we're going to accumulate the answer in, The variable sitting there, long f = 1. And then you're going to see, In the iteration, It's your standard iteration. The the beginning is of i = 1, i goes up to an equal to n, auto increment i. And accumulate f by multiplying f by i. So you see, after you finish this iteration, you will have multiplied 1 * 2 * 3 etc, by n, the definition of factorial, and then you return f. That's the iteration, that should be straightforward, it should be no problem for you. Now, let's look at the iterative version. This is what's a bit novel. I'm calling it recursive_factorial, again, it's long. int n doesn't need to be long, because we can't, in fact, compute on very large numbers. And we check to see the base case. So here's our base case, n == 1. What we know about when n == 1, the definition of factorial is just 1, so we return 1. But if we don't have the base case, we can count backwards just as in our countdown program. Except here, we take recursive_factorial of a smaller value times n. So this is the generalized case, this is generally what happens in the inductive case, n and times the smaller value factorial. You need to convince yourself that this give exactly the same result. And that's what I've done here. In comparing both, I've just asked the user to say, how many? And then I first do it iteratively, and then I second do it recursively, just to show that we're going to get the same result. So I've already compiled this, so let's run it. Why don't we do it for a small number? So here's your iterative thing, factorial of 1 is 1, factorial of 2 is 2, 1 times 2 is 2, factorial of 3 is 6. And again, you get the same results recursively. Let's do a slightly larger version. Let's do up to 10. And here the numbers start getting big, and you only see, because I didn't have enough screen width, this is the recursive version. You can see the final 10 is the same as this 10. And you can see how they go up, and you can see that since you multiply by 10, that's 10 times larger than that. Just like 3 to 4 is 4 times 6 is 24, 5 times 24 is 120, 6 times 120 is 720, 7 times 720 is 5,040, etc. Okay, so that's a very standard example taken from mathematics. You get it straight out of the definition. If you saw a mathematical expression, you frequently see functions of this kind defined inductively or recursively. So there's a natural mapping, it lets you easily in algorithmically transcribe that idea into a recursive function. [MUSIC]
