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