Original subtitles

[MUSIC PLAYING]

DOUG LLOYD: If you saw our video on recursion,

the process might have seemed a little bit magical.

How does a function know to wait for another function

and pass its data to some other thing that's running at the same time?

It can seem a little magical at the outset

if you don't understand exactly how functions are called and operate in C.

And the way they operate is using something called the call stack.

And the way the call stack works is as follows.

If you call a function, basically what happens is a big chunk of memory

is set aside somewhere in the system for that function to do its work.

So for example, if you call a function and the first thing you

do is declare a couple of variables, what's going to happen

is a stack frame or a function frame will be created,

a big chunk of memory, and those variables will be given space.

So if it's three integers, you'll get three, four-byte chunks,

just like the size of an integer, as well as some space

to do some calculations and whatever else the function might need.

And that's where the function will do all of its work.

Now, it's possible that more than one function's frame might

exist in memory at any given time.

So for example, let's say the function main

calls another function called move.

And then the function move calls another function called direction.

At that point, all three of those functions have open frames.

But in general, only one of those frames will ever be active.

Only one of those functions is ever running at a given time,

even though all three of them have space set aside and are sort of hanging out,

waiting to do something.

Now, the way these frames are arranged is in what's called a stack.

And the frame for the most recently called

function is always the one at the top of the stack,

and that is called the active frame.

So again, if main called move and move called direction,

you can think about this like a stack as follows, where main is at the bottom,

move is above it, direction is on the top, and direction is the active frame.

That is the only function that is doing anything at the moment,

whereas move and main are just sort of waiting to become the active frame.

They're waiting to become the frame that is at the top of the stack.

When you call a new function, a new frame

is what's called pushed onto the top of the stack.

So if you call a new function, that function

immediately gets space and memory, and is put on top of the call stack.

And it becomes the active frame.

And whatever was the active frame, if there was one, is on pause.

It's just sitting there.

It's a holding pattern, waiting to become the active frame again.

When a function finishes its work, such as by returning, most commonly,

or perhaps reaching the end of the line if it's a void function,

it doesn't have a return value, that frame is

what's called popped off of the stack.

And then the frame that was in second place, since this frame is now gone,

that becomes the active frame.

It resumes where it left off.

If you would hit pause on that function, it's

going to pick up immediately where it left off.

This is actually why recursion works because all these frames are running,

but only one of them is moving at a given time.

The rest of them are all running, but they're on pause.

They're just waiting to become the new top of the stack again.

If we call another function, the active frame goes on pause again.

The function that just called is put on top and so on and so on

until all of the function frames are finished.

So let's take a look at a visualization of this,

an example using the factorial function to see if we can

help make this a little bit clearer.

So this is the entirety of a factorial file, for example.

And inside of that factorial file, I have two functions, fact,

which is going to be a recursive [? implementation ?] of factorial,

and main, which basically just call or prints out the value of factorial,

in this case, of 5.

So we start at the beginning of main.

And the first thing main does is it calls another function.

It calls printf().

As soon as it does that, main is on pause.

It's hanging out right here and it is waiting for printf() to do its work.

What does printf() have to do?

It just has to print out a number, but it has to print out factorial of 5

or it doesn't know factorial of 5.

It has to make a function call.

So printf() then goes on pause and waits for factorial of 5,

which now becomes the new active frame.

So in the factorial of 5 frame, what's happening?

We're passing in the value 5 to the fact function.

And then it's going to check, well, is n equal to 1?

No.

So then it's going to return n times fact n minus 1.

OK, so now the factorial 5 frame is basically calling a new function,

passing in another call to factorial, passing in 4 as the parameter instead.

So the factorial of 5 frame now goes on pause and a frame for factorial of 4

becomes the new active frame.

And it's going to go through the same process.

Is 4 equal to 1?

No.

So instead, it's going to return n times, in this case,

or four times factorial of 3, another function call.

So factorial of 4 frame goes on pause.

Factorial of 3's frame becomes the new active frame.

And repeat this process again for a factorial of 3, for a factorial of 2,

and then we get to factorial of 1.

So at the very beginning, right when factorial of 1 is called,

there are seven function frames in the call stack.

Factorial of 2, 3, 4, 5 printf() and main are all on pause at the lines that

you see there.

There's just hanging out, waiting to become the new active frame again.

But they're not moving from those arrowed indicators.

So factorial of 1's frame begins.

It asks the question, is n equal to 1?

Well, this case, the answer is yes.

It's going to return 1.

Now, remember what happens when a function returns a value,

that frame is done.

It goes away.

And that means that it gets popped back off of the call stack

and then the frame that is below it will become the new active frame.

So factorial of 1 returns a 1.

At this point, its frame is destroyed and factorial of 2

can now get unpaused.

Now, factorial of 2 is that dark blue line on the left

there and it was waiting on the return value of factorial of 1.

Well, factorial of 1 said, I returned a 1 to you.

So factorial of 2 is going to return 2 times 1, or 2.

It is now also returning and so when it returns, it gets popped off the stack.

Its function frame is destroyed and factorial of 3

becomes the new active frame.

Factorial of 3 was waiting on factorial of 2, which returned a 2.

So it's going to return 3 times 2, or 6, returns the value.

Its function frame is popped off of the stack.

It is destroyed.

Factorial of 4 becomes the new active frame.

Factorial of 4 was waiting on factorial of 3.

It got its answer back of 6.

So it's going to return 4 times 6, or 24.

And it's going to return that value to factorial of 5, which has been waiting

for factorial of 4 to finish its work.

It returns 5 times 24, which is 120.

When that frame is destroyed, now we resume at printf().

printf() has that dark red line on the bottom there.

It was waiting on factorial of 5, which just returned a 120.

So what printf() does is it prints out 120 and then its job is done.

It doesn't have anything else to do.

It's not waiting on another function call and so it finishes executing.

It doesn't return anything, but it doesn't have anything else to do.

So its function frame is destroyed.

It gets popped off of the stack.

And then all we have to do is see where main left off.

Well, that was all main had.

And so main's function frame will then pop off the stack as well

and this program will have completed its job by printing out 120.

Hopefully that illustration of the call stack

helped to show exactly how recursion works

and how these functions are waiting and interacting with each other

to allow the recursive process to occur.

I'm Doug Lloyd.

This is CS50.