Hi everyone! In this video I'm gonna Give you an introduction to Recursion So in computer science, recursion is a way of solving a problem, by having a function calling itself To see how that works exactly let's take a look at a few examples here First of all, let's think about factorials, and let's just quickly review factorials here. If you're given a positive integer n, and n! is equal to n times n minus 1 times n minus 2 times n minus 3 down to 3 times 2 times 1 So I'm just gonna give you a few examples here Four factorial is equal to four times three times two times one which is equal to twenty four and two factiorial is equal to two times one which is two and one factorial is one and what about zero factorial? It's actually defined to be one and you might say why is that? But you know This (inaudible) is just how it is defined, and let's just say here, we're trying to write a function called let's say fact, which takes a positive integer or zero as its argument and return this n factorial. Now let's say we wanna write this function using Recursion How can we do that? To solve this problem or to write this function recursively we need to actually examine this equation and a little bit more detail. Okay so I brought that equation over here and like we saw earlier we have n factorial being equal to n times n minus one times n minus two and so on times three times two times one I want you to see this equation, I want you to look at this part following the first n you might notice that this part is equivalent to n minus one factorial and that might be more obvious if I write this separately here as n minus one factorial equals n minus one times n minus times and so on times three times two times one. So this whole thing is equivalent to this part so you might say "well we can rewrite n factorial as n times n minus one factorial", and that's good this new equation is mostly correct but it's not a complete definition of factorials. Let's see why Let's say if you plug(?) in two to n right here It works just fine because you'll get two factorial being equal to two times two minus one factorial which is one factorial and one factorial is one so two times one factorial is two and that's correct What if you plug in one here? It's still good because you'll get one factorial being equal to one times one minus one factorial which is zero factorial and zero factorial is one as we saw earlier so that's one and this is correct. But as soon as you plug in zero here, it breaks. Let's see how that works zero factorial is equal to zero here, right here times zero minus one factorial which is minus one factorial, and minus one factorial is not defined. So this defenition works only for n that is greater than or equal to one, but it doesn't work for zero so actually for this definition to be complete for factorials, we need to write n factorial as two separate cases so here we're gonna write n factorial is equal to n times n minus one factorial if n is greater than or equal to one and if that's not the case, or if n is equal to zero, n factorial is equal to one and this is actually a complete definition of all factorials for all positive integers and zero. So let's just quickly see how we can use this new definition of factorials to find the factorial of any positive integer Let's say three. So if you ask yourself What's three factorial? There's two ways of answering that question. The first one would be to use the old definition and then the second way would be to use this new definition. And let's use this new definition here because we're gonna use this new definition later to write a function using recursion as well So using this definition, we can ask ourselves, what's three factorial? Well three is greater or equal to one, so by definition this is equal