I think I'm on fairly strong ground when I say that we haven't yet, in Computerphile, done recursion.
This can get extremely hard.
It is difficult to get your head around recursion, sometimes.
In one way you can take a very mathematical view about it
and close your eyes,
and if you're a pure mathematician
who thinks, as we computer scientists would say,
exclusively "top down" about things,
you can say, "Oh, it's just a formal definition, you know."
Here's an example of something you can do recursively.
Factorial of n is equal to n times factorial of n minus 1.
And if you're used to mathematical thinking, well, that's absolutely alright.
Of course, they will then go on, thank heavens, and say:
"Ah, but you've got to stop that. You're just going round and round"
"chasing your own tail."
"Because, what about factorial n minus 1, then?"
Well, factorial n-1
is the same as
n minus 1 times factorial n minus 2.
And the mathematician will say,
Oh yes, all you're doing is re-labeling the n.
Because, you know, what was n now becomes n-1, and so on.
And yes, that's quite right.
But certainly at the bottom of all this, you've got to have a way of
dropping out and terminating this
endless succession
of things defined in terms of themselves.
Your way out of all this
is that when you hit factorial 1,
that is defined to be 1.
So let's take, um, an actual real example of this
and one which we will later develop
with a program.
What we're saying -- I'll abbreviate it now
as "fact" rather than "factorial".
Factorial 4
from this definition
is
4 times whatever factorial of
[quietly] 4 minus 1?
3 is.
But factorial 3
is [laughing] 3 times
whatever factorial 2 is.
Factorial 2 is 2 times whatever factorial 1 is.
Ah! But factorial 1 is 1.
So there we are, then.
Factorial 4 is 4 times 3 times 2 times 1
is
is 24.
Factorial, if you wanted to work 'em out
on a computer --
You can do it one of two ways.
You can do it recursively --
and this really, as we will see, in its implementation, will need a stack;
oh yes, it will.
Or, you can do it iteratively.
What does it mean to do it recursively?
I will look at it very briefly here,
but then I will do this for you on the stack.
So, here's our recursive definition of factorial.
In fact, I've put in a comment here, saying "This is the recursive version."
What I'm saying here is --
there again, those of you familiar with
any of the C-like languages,
any of the C-like languages, you know, Java, C++, whatever --
you'll find this very familiar.
The incoming parameter,
or "argument" as it's sometimes called,
is labeled "n".
The name of the function is "factorial".
And the answer delivered back by factorial
will be an integer answer.
So, every time you call it,
it expects an incoming parameter,
or argument, as it's sometimes called;
and it will deliver you back an answer
that's also another integer.
Factorial is only defined for integers, not for real numbers,
not for any other sort of thing.
Only for integers, and only for positive integers.
It won't even work for negative ones.
Okay.
Now, this is almost like writing mathematics.
It's almost like writing
this definition I had up here, look.
You say, If the incoming argument is 1,
then my answer is 1.
The factorial of 1 is 1.
So I return, to the outside world that wants to know --
I return the answer 1.
Factorial 1 is 1.
Otherwise, I return back to the outside world
that wants to know --
I say, The factorial of anything else
is n times the factorial of the number 1 less than it.
What the secret is here,
is the factorial of the next number below,
you feed in as the so-called "actual parameter";
the thing that is 1 less than the n you've got at the moment.
So, if we can move 4,
I return back 4 times factorial 3.
What's n-1? If n is 4, it's factorial 3.
Ah!
Oh, gosh!
What this means is,
I can't return the answer
until I've worked out what factorial 3 is.
So I dive back into this same piece of code,
only this time --
it's still calling it "n",
but n has now changed into 3.
So the first thing you have to get happy about
is there isn't just one n.
There's lots of them.
They're all called "n", but they're all different;
and they all have to be managed and kept separate.
That's the first thing: There is not just one n.
Recursion wouldn't work if there were.
And that way of keeping them separate
just naturally falls out,
no process for guessing,
it's a stack.
You need a stack to do this properly.
Here's my main program. Here's its environment; here's its data.
What I'm going to do from here, the main program,
is to say,
I want factorial 4.
In order for it to work correctly
and have its own local variables,
which of course includes
all of these different
instances of n, in this case,
you put on what's called another stack frame,
another whole area of the stack.
And you say,
That one
is going to deliver back
the answer to factorial 4.
But factorial 4 then says,
Can't work the answer out
until I know what factorial 3 is.
So, remember,
this smaller white one
is gonna work out factorial 3.
It also
does the usual trick,
Oh, I don't know what factorial 3 is.
It's 3 times factorial 2.
So I've got to know what factorial 2 is.
So here is the frame
on the stack
that will work out factorial 2.
Finally, with a great sense of relief,
factorial 2 says,
All I know is that
I'm 2 times factorial 1.
There's factorial 1.
At last.
Factorial 1 says,
I know what I am;
I am the answer 1.
The factorial 2 frame
is waiting there
on what you might call
a "pending multiply".
It's saying,
I am 2 times whatever factorial 1 is.
Factorial 1 says, Here you go,
into the pending multiply,
the answer's 1.
And then the same thing happens.
Oh! So the answer to factorial 2, is 2.
Where does that need to be delivered back to?
It needs to be delivered back into the frame below,
which is positively gasping
because it wants to do
3 times whatever factorial 2 is.
It's 3 times 2.
Now, where is it that's waiting for that?
3 times 2 is 6.
So, somewhere down here
is a pending multiply in this frame,
saying that factorial 4
is 4 times whatever factorial 3 was.
But we've just found out that
factorial 3 ends up cascading down, delivering 6.
4 times 6 is 24.
Final pending multiply was done,
and it gets delivered back
into the main program
and in the main program that I've got here --
we'll put this out, of course, with a web link to it --
all I do with the value when I get it back,
is, I just print it out, or say
The answer to factorial 4 is 24.
That's back in the main program's area
at the bottom of the stack.
What you have to remember is that, in these pending multiplies that we had,
each one of them is holding onto
a different value of n
as the left-hand operand
in its pending mulitply.
This is saying, 4 times something; the one above it said, 3 times something;
2 times something; and so on.
And the answers cascaded back down
and dropped out at the bottom correctly.
We'd like to thank Audible.com for sponsoring this computerphile video.
They've got loads of books online.
So, if you want to check one out,
go over to
audible.com/computerphile
and you can download one for free
if you sign up there.
Today, I'd like to recommend
Console Wars
brand new book out by Blake Harris
and it chronicles
the console wars of the '90s
between Nintendo and Sega
when Sega did something really radical to take on
the massive company that was, or corporation that was, Nintendo.
Just shows how the players change as time goes on.
It's a really, really interesting story.
Uh, so check that out.
Remember, audible dot com slash computerphile
Sign up there to try out a free book.
Thanks once again to them
for supporting this video
and other computerphile videos.
And right up at the very top,
the top of stack is often called
the stack top pointer; SP for short.
It's not an IBM one; it's developed by a company called Motorola.