Call Stacks

Call Stacks


[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.

18 thoughts to “Call Stacks”

  1. This was great and visual explanation is one of the best I found (besides an also very good one in https://medium.freecodecamp.org/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9)

  2. Finally! I was trying to figure out this exact recursion problem without knowing what a call stack was. Then I saw 'call stack' briefly mentioned on Stack Overflow, did a Google search, found this video, watched it, and saw the light at the end of the tunnel. For a while, I thought I was just not able to grasp recursion and that it was a concept enjoyed by only the most sophisticated intellects…kind of like looking at one of those old 3-dimensional posters that contained a hidden image obscured by garble that could only be revealed if you stared at the poster with the right amount of eye blur, mind shift, or focal point. I never did find the 'knack' for looking at those posters and, before watching this video, I was certain I'd have to dismiss recursion as another one of those things I "just didn't get". This video really helped me out. Recursion might not be so strange after all. Thanks.

  3. If I had fact(1 000 000 000), would it be reasonable to iterate values in a loop instead of using recursion? If I use recursion, functions would stack up billion times and occupy a lot of memory, while loop operates inside main(). Which one occupies more space in memory recursion or iteration in a loop method? Which one is faster?

  4. Hey, I really enjoyed this video, however there is a bug at 3:20 in fact function definition, fact of 0 should be equal to 1.

  5. What if a function just call itself and does nothing. After how much time the recursive stack will be full and what is the time after which the prrogram will terminate. please help!

Leave a Reply

Your email address will not be published. Required fields are marked *