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