1
00:00:00,000 --> 00:00:01,844
[MUSIC PLAYING]

2
00:00:01,844 --> 00:00:05,540


3
00:00:05,540 --> 00:00:08,210
DOUG LLOYD: If you saw
our video on recursion,

4
00:00:08,210 --> 00:00:10,790
the process might have
seemed a little bit magical.

5
00:00:10,790 --> 00:00:14,060
How does a function know to
wait for another function

6
00:00:14,060 --> 00:00:19,000
and pass its data to some other thing
that's running at the same time?

7
00:00:19,000 --> 00:00:20,750
It can seem a little
magical at the outset

8
00:00:20,750 --> 00:00:26,120
if you don't understand exactly how
functions are called and operate in C.

9
00:00:26,120 --> 00:00:29,540
And the way they operate is using
something called the call stack.

10
00:00:29,540 --> 00:00:31,680
And the way the call
stack works is as follows.

11
00:00:31,680 --> 00:00:36,050
If you call a function, basically
what happens is a big chunk of memory

12
00:00:36,050 --> 00:00:39,167
is set aside somewhere in the system
for that function to do its work.

13
00:00:39,167 --> 00:00:41,750
So for example, if you call a
function and the first thing you

14
00:00:41,750 --> 00:00:45,170
do is declare a couple of
variables, what's going to happen

15
00:00:45,170 --> 00:00:48,230
is a stack frame or a function
frame will be created,

16
00:00:48,230 --> 00:00:51,535
a big chunk of memory, and those
variables will be given space.

17
00:00:51,535 --> 00:00:54,380
So if it's three integers, you'll
get three, four-byte chunks,

18
00:00:54,380 --> 00:00:56,930
just like the size of an
integer, as well as some space

19
00:00:56,930 --> 00:01:01,021
to do some calculations and whatever
else the function might need.

20
00:01:01,021 --> 00:01:03,270
And that's where the function
will do all of its work.

21
00:01:03,270 --> 00:01:06,900
Now, it's possible that more
than one function's frame might

22
00:01:06,900 --> 00:01:09,220
exist in memory at any given time.

23
00:01:09,220 --> 00:01:11,520
So for example, let's
say the function main

24
00:01:11,520 --> 00:01:13,500
calls another function called move.

25
00:01:13,500 --> 00:01:17,520
And then the function move calls
another function called direction.

26
00:01:17,520 --> 00:01:21,690
At that point, all three of
those functions have open frames.

27
00:01:21,690 --> 00:01:25,380
But in general, only one of
those frames will ever be active.

28
00:01:25,380 --> 00:01:28,080
Only one of those functions is
ever running at a given time,

29
00:01:28,080 --> 00:01:31,900
even though all three of them have space
set aside and are sort of hanging out,

30
00:01:31,900 --> 00:01:34,230
waiting to do something.

31
00:01:34,230 --> 00:01:37,640
Now, the way these frames are
arranged is in what's called a stack.

32
00:01:37,640 --> 00:01:39,390
And the frame for the
most recently called

33
00:01:39,390 --> 00:01:41,790
function is always the one
at the top of the stack,

34
00:01:41,790 --> 00:01:44,050
and that is called the active frame.

35
00:01:44,050 --> 00:01:47,520
So again, if main called move
and move called direction,

36
00:01:47,520 --> 00:01:51,000
you can think about this like a stack
as follows, where main is at the bottom,

37
00:01:51,000 --> 00:01:55,390
move is above it, direction is on the
top, and direction is the active frame.

38
00:01:55,390 --> 00:01:58,200
That is the only function that
is doing anything at the moment,

39
00:01:58,200 --> 00:02:02,220
whereas move and main are just sort
of waiting to become the active frame.

40
00:02:02,220 --> 00:02:05,970
They're waiting to become the frame
that is at the top of the stack.

41
00:02:05,970 --> 00:02:09,060
When you call a new
function, a new frame

42
00:02:09,060 --> 00:02:11,547
is what's called pushed
onto the top of the stack.

43
00:02:11,547 --> 00:02:13,380
So if you call a new
function, that function

44
00:02:13,380 --> 00:02:16,590
immediately gets space and memory,
and is put on top of the call stack.

45
00:02:16,590 --> 00:02:18,420
And it becomes the active frame.

46
00:02:18,420 --> 00:02:21,960
And whatever was the active frame,
if there was one, is on pause.

47
00:02:21,960 --> 00:02:23,260
It's just sitting there.

48
00:02:23,260 --> 00:02:26,922
It's a holding pattern, waiting
to become the active frame again.

49
00:02:26,922 --> 00:02:29,880
When a function finishes its work,
such as by returning, most commonly,

50
00:02:29,880 --> 00:02:32,546
or perhaps reaching the end of
the line if it's a void function,

51
00:02:32,546 --> 00:02:36,210
it doesn't have a return
value, that frame is

52
00:02:36,210 --> 00:02:38,520
what's called popped off of the stack.

53
00:02:38,520 --> 00:02:42,400
And then the frame that was in second
place, since this frame is now gone,

54
00:02:42,400 --> 00:02:43,650
that becomes the active frame.

55
00:02:43,650 --> 00:02:44,890
It resumes where it left off.

56
00:02:44,890 --> 00:02:46,550
If you would hit pause
on that function, it's

57
00:02:46,550 --> 00:02:48,570
going to pick up immediately
where it left off.

58
00:02:48,570 --> 00:02:52,920
This is actually why recursion works
because all these frames are running,

59
00:02:52,920 --> 00:02:55,050
but only one of them is
moving at a given time.

60
00:02:55,050 --> 00:02:57,840
The rest of them are all
running, but they're on pause.

61
00:02:57,840 --> 00:03:01,380
They're just waiting to become
the new top of the stack again.

62
00:03:01,380 --> 00:03:05,430
If we call another function, the
active frame goes on pause again.

63
00:03:05,430 --> 00:03:09,090
The function that just called is
put on top and so on and so on

64
00:03:09,090 --> 00:03:12,340
until all of the function
frames are finished.

65
00:03:12,340 --> 00:03:14,340
So let's take a look at
a visualization of this,

66
00:03:14,340 --> 00:03:17,490
an example using the factorial
function to see if we can

67
00:03:17,490 --> 00:03:20,020
help make this a little bit clearer.

68
00:03:20,020 --> 00:03:23,280
So this is the entirety of a
factorial file, for example.

69
00:03:23,280 --> 00:03:26,400
And inside of that factorial
file, I have two functions, fact,

70
00:03:26,400 --> 00:03:29,340
which is going to be a recursive
[? implementation ?] of factorial,

71
00:03:29,340 --> 00:03:34,180
and main, which basically just call
or prints out the value of factorial,

72
00:03:34,180 --> 00:03:35,670
in this case, of 5.

73
00:03:35,670 --> 00:03:38,250
So we start at the beginning of main.

74
00:03:38,250 --> 00:03:41,550
And the first thing main does
is it calls another function.

75
00:03:41,550 --> 00:03:43,350
It calls printf().

76
00:03:43,350 --> 00:03:47,370
As soon as it does
that, main is on pause.

77
00:03:47,370 --> 00:03:52,230
It's hanging out right here and it is
waiting for printf() to do its work.

78
00:03:52,230 --> 00:03:53,650
What does printf() have to do?

79
00:03:53,650 --> 00:03:56,784
It just has to print out a number,
but it has to print out factorial of 5

80
00:03:56,784 --> 00:03:58,200
or it doesn't know factorial of 5.

81
00:03:58,200 --> 00:04:00,330
It has to make a function call.

82
00:04:00,330 --> 00:04:03,870
So printf() then goes on pause
and waits for factorial of 5,

83
00:04:03,870 --> 00:04:07,130
which now becomes the new active frame.

84
00:04:07,130 --> 00:04:09,240
So in the factorial of 5
frame, what's happening?

85
00:04:09,240 --> 00:04:11,610
We're passing in the value
5 to the fact function.

86
00:04:11,610 --> 00:04:14,510
And then it's going to
check, well, is n equal to 1?

87
00:04:14,510 --> 00:04:15,220
No.

88
00:04:15,220 --> 00:04:20,244
So then it's going to return
n times fact n minus 1.

89
00:04:20,244 --> 00:04:25,010
OK, so now the factorial 5 frame is
basically calling a new function,

90
00:04:25,010 --> 00:04:29,500
passing in another call to factorial,
passing in 4 as the parameter instead.

91
00:04:29,500 --> 00:04:33,970
So the factorial of 5 frame now goes
on pause and a frame for factorial of 4

92
00:04:33,970 --> 00:04:35,179
becomes the new active frame.

93
00:04:35,179 --> 00:04:37,094
And it's going to go
through the same process.

94
00:04:37,094 --> 00:04:37,960
Is 4 equal to 1?

95
00:04:37,960 --> 00:04:38,680
No.

96
00:04:38,680 --> 00:04:41,440
So instead, it's going to
return n times, in this case,

97
00:04:41,440 --> 00:04:45,010
or four times factorial of
3, another function call.

98
00:04:45,010 --> 00:04:47,430
So factorial of 4 frame goes on pause.

99
00:04:47,430 --> 00:04:50,170
Factorial of 3's frame
becomes the new active frame.

100
00:04:50,170 --> 00:04:55,030
And repeat this process again for a
factorial of 3, for a factorial of 2,

101
00:04:55,030 --> 00:04:57,520
and then we get to factorial of 1.

102
00:04:57,520 --> 00:05:01,540
So at the very beginning, right
when factorial of 1 is called,

103
00:05:01,540 --> 00:05:06,250
there are seven function
frames in the call stack.

104
00:05:06,250 --> 00:05:11,470
Factorial of 2, 3, 4, 5 printf() and
main are all on pause at the lines that

105
00:05:11,470 --> 00:05:12,070
you see there.

106
00:05:12,070 --> 00:05:16,930
There's just hanging out, waiting to
become the new active frame again.

107
00:05:16,930 --> 00:05:21,950
But they're not moving from
those arrowed indicators.

108
00:05:21,950 --> 00:05:23,680
So factorial of 1's frame begins.

109
00:05:23,680 --> 00:05:26,560
It asks the question, is n equal to 1?

110
00:05:26,560 --> 00:05:28,780
Well, this case, the answer is yes.

111
00:05:28,780 --> 00:05:30,730
It's going to return 1.

112
00:05:30,730 --> 00:05:34,720
Now, remember what happens when
a function returns a value,

113
00:05:34,720 --> 00:05:37,030
that frame is done.

114
00:05:37,030 --> 00:05:38,210
It goes away.

115
00:05:38,210 --> 00:05:41,530
And that means that it gets
popped back off of the call stack

116
00:05:41,530 --> 00:05:44,680
and then the frame that is below it
will become the new active frame.

117
00:05:44,680 --> 00:05:47,710
So factorial of 1 returns a 1.

118
00:05:47,710 --> 00:05:51,190
At this point, its frame is
destroyed and factorial of 2

119
00:05:51,190 --> 00:05:52,961
can now get unpaused.

120
00:05:52,961 --> 00:05:55,210
Now, factorial of 2 is that
dark blue line on the left

121
00:05:55,210 --> 00:05:59,170
there and it was waiting on the
return value of factorial of 1.

122
00:05:59,170 --> 00:06:01,930
Well, factorial of 1 said,
I returned a 1 to you.

123
00:06:01,930 --> 00:06:06,310
So factorial of 2 is going
to return 2 times 1, or 2.

124
00:06:06,310 --> 00:06:10,500
It is now also returning and so when it
returns, it gets popped off the stack.

125
00:06:10,500 --> 00:06:13,450
Its function frame is
destroyed and factorial of 3

126
00:06:13,450 --> 00:06:15,840
becomes the new active frame.

127
00:06:15,840 --> 00:06:20,080
Factorial of 3 was waiting on
factorial of 2, which returned a 2.

128
00:06:20,080 --> 00:06:24,544
So it's going to return 3 times
2, or 6, returns the value.

129
00:06:24,544 --> 00:06:26,460
Its function frame is
popped off of the stack.

130
00:06:26,460 --> 00:06:27,690
It is destroyed.

131
00:06:27,690 --> 00:06:30,760
Factorial of 4 becomes
the new active frame.

132
00:06:30,760 --> 00:06:33,340
Factorial of 4 was
waiting on factorial of 3.

133
00:06:33,340 --> 00:06:34,720
It got its answer back of 6.

134
00:06:34,720 --> 00:06:36,960
So it's going to return
4 times 6, or 24.

135
00:06:36,960 --> 00:06:40,570
And it's going to return that value to
factorial of 5, which has been waiting

136
00:06:40,570 --> 00:06:42,580
for factorial of 4 to finish its work.

137
00:06:42,580 --> 00:06:46,367
It returns 5 times 24, which is 120.

138
00:06:46,367 --> 00:06:48,700
When that frame is destroyed,
now we resume at printf().

139
00:06:48,700 --> 00:06:51,010
printf() has that dark red
line on the bottom there.

140
00:06:51,010 --> 00:06:55,360
It was waiting on factorial of
5, which just returned a 120.

141
00:06:55,360 --> 00:06:59,320
So what printf() does is it prints
out 120 and then its job is done.

142
00:06:59,320 --> 00:07:00,820
It doesn't have anything else to do.

143
00:07:00,820 --> 00:07:05,410
It's not waiting on another function
call and so it finishes executing.

144
00:07:05,410 --> 00:07:10,000
It doesn't return anything, but it
doesn't have anything else to do.

145
00:07:10,000 --> 00:07:11,560
So its function frame is destroyed.

146
00:07:11,560 --> 00:07:13,250
It gets popped off of the stack.

147
00:07:13,250 --> 00:07:15,610
And then all we have to do
is see where main left off.

148
00:07:15,610 --> 00:07:17,200
Well, that was all main had.

149
00:07:17,200 --> 00:07:20,140
And so main's function frame will
then pop off the stack as well

150
00:07:20,140 --> 00:07:24,146
and this program will have completed
its job by printing out 120.

151
00:07:24,146 --> 00:07:26,020
Hopefully that illustration
of the call stack

152
00:07:26,020 --> 00:07:28,480
helped to show exactly
how recursion works

153
00:07:28,480 --> 00:07:31,300
and how these functions are waiting
and interacting with each other

154
00:07:31,300 --> 00:07:35,080
to allow the recursive process to occur.

155
00:07:35,080 --> 00:07:36,190
I'm Doug Lloyd.

156
00:07:36,190 --> 00:07:37,960
This is CS50.

157
00:07:37,960 --> 00:07:39,545