What I want to do in this video is introduce you
to what I think is one of the neatest ideas in computer
science, and that is recursion.
So the way that we've defined this factorial function
in the last few videos is actually
an iterative definition.
We are iterating through different values
for this variable i, and then we're
essentially taking those values, adding one, then multiplying
those times our original product.
And when we keep iterating through all of that,
our eventual product has all of the values
from 1 through the number multiplied by each other,
and they're all sitting in this variable product.
What I'm going to do here is rewrite this program.
And what's cool about functions--
I'm going to rewrite this function.
What's cool about functions are this function,
we just say, look, it returns a factorial of a number.
We don't care how this is actually written.
And so anything that's using this function call,
no matter how I implement it, as long as I implement it
correctly, it shouldn't worry about it.
So as long as I implement the guts of this function right,
even if I do it in a very different way,
it shouldn't affect the behavior of any of the functions
that call it.
So let's go ahead and try to define this function
recursively.
And I think you're going to find this slightly fascinating.
So I'm going to do it a little bit different.
We're going to put some conditionals in here as well.
So I'm going to say-- so it's almost-- in some ways,
recursion is really deep and complicated,
and on some levels, it's way simpler than anything else.
So let me just put all of this stuff down there.
So I'm going to say, look, if the number-- you always
want to think about a base case.
What's a situation where kind of the nugget or the smallest
values we can put into for a number that'll
give us a decent response?
So we'll say, look, if number is--
let's say if it's less than or equal to 1,
so if it's less than or equal to 1, let's just return.
Well, then it's factorial.
Let's just return 1, especially if we
want to have the same behavior as the old function.
The old function, regardless of whether we
put a 1 there, a 0 there, or actually,
even if we put a negative 1 or negative 2 there,
it always gave us the factorial being equal to 1.
So that's exactly what we're doing over here.
We're returning 1 if the number is less than 1.
And this also defines our base case.
I can even label it here.
So let me label-- this is our base case.
And you'll see what I mean for a second by base case.
And what I'm about to do now, this
is the really exciting part about recursion.
If the number is not less than or equal to 1,
so I could write l if-- well, maybe
I'll just write l, actually.
So if the number is not less than or equal to 1,
I'm going to return something different.
And what I'm going to return is that number
times the factorial-- times the factorial of one
less than that number.
Now, the reason why this is fascinating and cool
and all the rest is I just defined something
using that something.
So I just defined a function called factorial,
and I defined it using the definition of the function
factorial.
It is referring to itself.
This is what recursive functions do.
But if you think about it-- and I'll diagram it out
in more detail in the next video,
so hopefully it makes a little bit more sense--
it should kind of work.
Because if you put a 1 or a 0 in for a number,
it'll just return 1.
What happens if the number is 2?
Well, if the number is 2, it'll say, look,
the number is not less than our 1, so I'll go over here.
So it says it'll return 2 times factorial of 2 minus 1,
or factorial of 1.
And then it'll call factorial again, and factorial of 1
is just 1, so it'll return 2 times 1.
So that'll work out for 2.
Try it for 3.
If you do a factorial of 3, it'll
go down to this clause over here,
because 3 is not less than or equal to 1,
and it'll return 3 times the factorial of 3 minus 1,
which is 2, the factorial of 2.
Well, we know it already returns the right answer
for the factorial of 2, so it'll return 3 times 2, which
is 6, which is a factorial of 3.
So hopefully you're getting the gist of it.
Factorial of 4 is going to work for the exact same reason.
It's going to boil down to 4 times the factorial of 3.
We know that it works for the factorial of 3.
And just to prove to you that I'm not
doing some type of crazy voodoo, and that this will actually
work, let's try to run the program.
Let's try to run the program right here.
This is some stuff that I was doing beforehand.
Let me just get rid of that.
So let's just run the program.
So all I've done is I've redefined
the factorial function, but I've redefined it recursively.
I won't have to change the comments.
So let me save it, and let's interpret this program.
Let's execute it and see if it does what we need it to do.
All right.
So they're prompting us for something.
Let's take the factorial of 5-- 120.
And so once again, our factorial program,
no matter what we put in there, it gives us the right answer.
But what's really cool is it's now doing it recursively.
When I do factorial of 6, say, OK, factorial of 6.
Is 6 less than or equal to 1?
Well, no it's not, so it goes to this else
clause right over here.
So then it says return 6 times the factorial of 5.
Then it says, OK, let me remember
6 times the factorial of 5.
Let's figure out what the factorial of 5 is.
Well, factorial of 5 is going to be 5 times the factorial of 4.
And then that factorial of 4 is 4 times the factorial of 3,
all the way down to the factorial of 1, which is 1.
And so it'll actually return 6 times 5 times 4 times 3 times
2 times 1.