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.
https://youtu.be/d5jTxBNK6OU
This video is a great one too for linear homogenous relations. Very clear and easy to understand.