DOUG LLOYD: If you've seen the video on recursion, the whole process might have seemed a little bit magical. How does it work? How do the functions know that they need to wait and wait for another value to return from a different function call in order to get the result we want? Well, the reason this works is because of something known as the call stack. When you call a function, the system sets aside space in memory for that function to do its work. And we call these chunks of memory that are being set aside for each function call a stack frame or a function frame. And as you might expect, these stack frames live on the stack part of memory. 

More than one function stack frame can exist in memory at a given time. If main calls a function move, and move calls direction, all three functions have open frames. But they don't all have active frames. These frames are arranged in a stack. And the frame from the most recently called function is always on top of the stack. And that is always the active frame. There's only really ever one function that's active at a time. It's the one on top of the stack. 

When a function calls another function, it sort of presses pause. It sort of is on hold, waiting. And another stack frame is pushed onto the stack on top of it. And that becomes the active frame. And the frame immediately below it needs to wait until it is again the active frame before it can resume its work. When a function is complete and it's done, its frame is popped off the stack. That's the terminology. And the frame immediately below it, as I just said, becomes the new active frame. 

And if it calls another function, it's going to pause again. That new function's stack frame will be pushed onto the top of the stack. It'll do its work. It might pop back off. And the other function below it can resume again. 

So let's go through this again, looking at the idea of the factorial function that we defined in the recursion video to see exactly how the magic behind this recursive process is taking place. So this is our entire file, right? We defined two functions-- main and fact. And as we might expect, any C program is going to start at the first line of main. 

So we create a new stack frame for main. And it's going to begin running. Main calls printf. And printf is going to print out factorial of 5. Well, it doesn't know what factorial of 5 is, and so this call is already depending on another function call. So main is going to pause right there. I'm gonna leave its arrow right there, color it the same color as the stack frame on the right, to indicate that main is going to freeze here while factorial of 5 is called. 

So factorial of 5 is called. And it's going to start at the very beginning of the factorial function. It asks the question am I equal to 1? Is 5 equal to 1? Well, no. So it's going to go down to the else part, return n times factorial of n minus 1. Well, OK. 

So now, factorial of 5 is depending on another call to factorial, passing in 4 as the parameter. And so the factorial of 5 frame, that red frame, is going to freeze right there at that line I've indicated and wait for factorial of 4 to finish what it needs to do so that then it can become the active frame again. 

So factorial of 4 starts at the beginning of factorial. Is 4 equal to 1? No, so it's going to do the same thing. It's going to go down the else branch. It's going to get to that line of code. OK, I'm going to return four times. Oh, factorial of 3-- so factorial of 4 depends on factorial of 3 finishing. 

And so it needs to call factorial of 3. And that's gonna go through the same process again. It starts through, gets here. Factorial of 3 depends on factorial of 1. So factorial of 2 starts, gets here. It depends on factorial of 1. Factorial of 1 starts. 

OK. So now, we're getting somewhere interesting, right? So now, 1 is equal to 1. And so we return 1. At this point, we are returning. The function's done. It's behavior is-- there's nothing else for it to do, and so the stack frame for factorial of 1 pops off. It's finished. It returned 1. And now, factorial of 2, which was the frame immediately below it in the stack, becomes the active frame. 

And it can pick up exactly where it left off. It's been waiting for a factorial of 1 to finish its work. It has now finished. And so here we are. 

Factorial of 1 returned a value of 1. So factorial of 2 can say return 2 times 1. Its work is now done. It's returned 2 to factorial of 3, which was waiting for it. Factorial of 3 is now the top frame, the active frame in the stack. And so it says, OK, well, I'm going to return 3 times 2, which is 6. And I'm going to give that value back to factorial of 4, which has been waiting for me. I'm done. Factorial of 3 pops off the stack, and factorial of 4 is now the active frame. 

4 says, OK, I'm going to return 4 times the factorial of 3, which was six. That was of value that factorial of 3 returned. And so 4 times 6 is 24. And I'm going to pass that back to factorial of 5, which has been waiting for me. Factorial of 5 is now the active frame. It's going to return 5 times factorial of 4-- 5 times 24, or 120-- and give that value back to main, which has been waiting very patiently for a long time at the bottom of the stack. 

It's where it started. It made this call. Several frames took over at the top. It is now back on top of the stack. It's the active frame. So main got the value 120 back from factorial of 5. It's been waiting to print out that value. And then it's done. There's no more lines of code in main. So main's frame pops off the stack, and we're done. 

And that's how recursion works. That's how stack frames work. Those function calls that happened previously are just on pause, waiting for the subsequent calls to finish so they can become the active frame and finish what they need to do. 

I'm Doug Lloyd. This is CS50.