1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: In order to understand
recursion, you must

3
00:00:10,190 --> 00:00:13,820
first understand recursion.

4
00:00:13,820 --> 00:00:17,280
Having recursion in program design means
that you have self-referential

5
00:00:17,280 --> 00:00:18,570
definitions.

6
00:00:18,570 --> 00:00:21,520
Recursive data structures, for instance,
are data structures that

7
00:00:21,520 --> 00:00:23,990
include themselves in
their definitions.

8
00:00:23,990 --> 00:00:27,160
But today, we're going to focus
on recursive functions.

9
00:00:27,160 --> 00:00:31,160
>> Recall that functions take inputs,
arguments, and return a value as their

10
00:00:31,160 --> 00:00:34,480
output represented by
this diagram here.

11
00:00:34,480 --> 00:00:38,060
We'll think of the box as the body of
the function, containing the set of

12
00:00:38,060 --> 00:00:42,340
instructions that interpret the
input and provide an output.

13
00:00:42,340 --> 00:00:45,660
Taking a closer look inside the body of
the function could reveal calls to

14
00:00:45,660 --> 00:00:47,430
other functions as well.

15
00:00:47,430 --> 00:00:51,300
Take this simple function, foo, that
takes a single string as input and

16
00:00:51,300 --> 00:00:54,630
prints how many letters
that string has.

17
00:00:54,630 --> 00:00:58,490
The function strlen, for string length,
is called, whose output is

18
00:00:58,490 --> 00:01:01,890
required for the call to printf.

19
00:01:01,890 --> 00:01:05,770
>> Now, what makes a recursive function
special is that it calls itself.

20
00:01:05,770 --> 00:01:09,610
We can represent this recursive
call with this orange arrow

21
00:01:09,610 --> 00:01:11,360
looping back to itself.

22
00:01:11,360 --> 00:01:15,630
But executing itself again will only
make another recursive call, and

23
00:01:15,630 --> 00:01:17,150
another and another.

24
00:01:17,150 --> 00:01:19,100
But recursive functions
can't be infinite.

25
00:01:19,100 --> 00:01:23,490
They have to end somehow, or your
program will run forever.

26
00:01:23,490 --> 00:01:27,680
>> So we need to find a way to break
out of the recursive calls.

27
00:01:27,680 --> 00:01:29,900
We call this the base case.

28
00:01:29,900 --> 00:01:33,570
When the base case condition is met,
the function returns without making

29
00:01:33,570 --> 00:01:34,950
another recursive call.

30
00:01:34,950 --> 00:01:39,610
Take this function, hi, a void function
that takes an int n as input.

31
00:01:39,610 --> 00:01:41,260
The base case comes first.

32
00:01:41,260 --> 00:01:46,220
If n is less than zero, print bye and
return For all other cases, the

33
00:01:46,220 --> 00:01:49,400
function will print hi and execute
the recursive call.

34
00:01:49,400 --> 00:01:53,600
Another call to the function hi with
a decremented input value.

35
00:01:53,600 --> 00:01:56,790
>> Now, even though we print hi, the
function won't terminate until we

36
00:01:56,790 --> 00:02:00,370
return its return type,
in this case void.

37
00:02:00,370 --> 00:02:04,830
So for every n other than the base case,
this function hi will return hi

38
00:02:04,830 --> 00:02:06,890
of n minus 1.

39
00:02:06,890 --> 00:02:10,050
Since this function is void though, we
won't explicitly type return here.

40
00:02:10,050 --> 00:02:12,000
We'll just execute the function.

41
00:02:12,000 --> 00:02:16,960
So calling hi(3) will print hi and
execute hi(2) which executes hi(1) one

42
00:02:16,960 --> 00:02:20,560
which executes hi(0), where the
base case condition is met.

43
00:02:20,560 --> 00:02:24,100
So hi(0) prints bye and returns.

44
00:02:24,100 --> 00:02:24,990
>> OK.

45
00:02:24,990 --> 00:02:28,690
So now that we understand the basics of
recursive functions, that they need

46
00:02:28,690 --> 00:02:32,730
at least one base case as well as a
recursive call, let's move on to a

47
00:02:32,730 --> 00:02:34,120
more meaningful example.

48
00:02:34,120 --> 00:02:37,830
One that doesn't just return
void no matter what.

49
00:02:37,830 --> 00:02:41,340
>> Let's take a look at the factorial
operation used most commonly in

50
00:02:41,340 --> 00:02:43,660
probability calculations.

51
00:02:43,660 --> 00:02:48,120
Factorial of n is the product of every
positive integer less than

52
00:02:48,120 --> 00:02:49,400
and equal to n.

53
00:02:49,400 --> 00:02:56,731
So factorial five is 5 times 4 times
3 times 2 times 1 to give 120.

54
00:02:56,731 --> 00:03:01,400
Four factorial is 4 times 3 times
2 times 1 to give 24.

55
00:03:01,400 --> 00:03:04,910
And the same rule applies
to any positive integer.

56
00:03:04,910 --> 00:03:08,670
>> So how might we write a recursive
function that calculates the factorial

57
00:03:08,670 --> 00:03:09,960
of a number?

58
00:03:09,960 --> 00:03:14,700
Well, we'll need to identify both the
base case and the recursive call.

59
00:03:14,700 --> 00:03:18,250
The recursive call will be the same
for all cases except for the base

60
00:03:18,250 --> 00:03:21,420
case, which means that we'll have to
find a pattern that will give us our

61
00:03:21,420 --> 00:03:23,350
desired result.

62
00:03:23,350 --> 00:03:30,270
>> For this example, see how 5 factorial
involves multiplying 4 by 3 by 2 by 1

63
00:03:30,270 --> 00:03:33,010
And that very same multiplication
is found here, the

64
00:03:33,010 --> 00:03:35,430
definition of 4 factorial.

65
00:03:35,430 --> 00:03:39,810
So we see that 5 factorial is
just 5 times 4 factorial.

66
00:03:39,810 --> 00:03:43,360
Now does this pattern apply
to 4 factorial as well?

67
00:03:43,360 --> 00:03:44,280
Yes.

68
00:03:44,280 --> 00:03:49,120
We see that 4 factorial contains the
multiplication 3 times 2 times 1, the

69
00:03:49,120 --> 00:03:51,590
very same definition as 3 factorial.

70
00:03:51,590 --> 00:03:56,950
So 4 factorial is equal to 4 times 3
factorial, and so on and so forth our

71
00:03:56,950 --> 00:04:02,170
pattern sticks until 1 factorial, which
by definition is equal to 1.

72
00:04:02,170 --> 00:04:04,950
>> There's no other positive
integers left.

73
00:04:04,950 --> 00:04:07,870
So we have the pattern for
our recursive call.

74
00:04:07,870 --> 00:04:13,260
n factorial is equal to n times
the factorial of n minus 1.

75
00:04:13,260 --> 00:04:14,370
And our base case?

76
00:04:14,370 --> 00:04:17,370
That'll just be our definition
of 1 factorial.

77
00:04:17,370 --> 00:04:19,995
>> So now we can move on to writing
code for the function.

78
00:04:19,995 --> 00:04:24,110
For the base case, we'll have the
condition n equals equals 1, where

79
00:04:24,110 --> 00:04:25,780
we'll return 1.

80
00:04:25,780 --> 00:04:29,280
Then moving onto the recursive call,
we'll return n times the

81
00:04:29,280 --> 00:04:32,180
factorial of n minus 1.

82
00:04:32,180 --> 00:04:33,590
>> Now let's test this our.

83
00:04:33,590 --> 00:04:35,900
Let's try factorial 4.

84
00:04:35,900 --> 00:04:39,420
Per our function it's equal
to 4 times factorial(3).

85
00:04:39,420 --> 00:04:43,040
Factorial(3) is equal to
3 times factorial(2).

86
00:04:43,040 --> 00:04:48,700
Factorial(2) is equal to 2 times
factorial(1), which returns 1.

87
00:04:48,700 --> 00:04:52,490
Factorial(2) now returns 2 times 1, 2.

88
00:04:52,490 --> 00:04:55,960
Factorial(3) can now return
3 times 2, 6.

89
00:04:55,960 --> 00:05:02,490
And finally, factorial(4)
returns 4 times 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> If you're encountering any difficulty
with the recursive call, pretend that

91
00:05:06,780 --> 00:05:09,660
the function works already.

92
00:05:09,660 --> 00:05:13,450
What I mean by this is that you should
trust your recursive calls to return

93
00:05:13,450 --> 00:05:15,100
the right values.

94
00:05:15,100 --> 00:05:18,960
For instance, if I know that
factorial(5) equals 5 times

95
00:05:18,960 --> 00:05:24,870
factorial(4), I'm going to trust that
factorial(4) will give me 24.

96
00:05:24,870 --> 00:05:28,510
Think of it as a variable, if you
will, as if you already defined

97
00:05:28,510 --> 00:05:30,070
factorial(4).

98
00:05:30,070 --> 00:05:33,850
So for any factorial(n), it's
the product of n and

99
00:05:33,850 --> 00:05:35,360
the previous factorial.

100
00:05:35,360 --> 00:05:38,130
And this previous factorial
is obtained by calling

101
00:05:38,130 --> 00:05:41,330
factorial of n minus 1.

102
00:05:41,330 --> 00:05:45,130
>> Now, see if you can implement a
recursive function yourself.

103
00:05:45,130 --> 00:05:50,490
Load up your terminal, or run.cs50.net,
and write a function sum

104
00:05:50,490 --> 00:05:54,770
that takes an integer n and returns the
sum of all consecutive positive

105
00:05:54,770 --> 00:05:57,490
integers from n to 1.

106
00:05:57,490 --> 00:06:01,000
I've written out the sums of some
values to help you our.

107
00:06:01,000 --> 00:06:04,030
First, figure out the
base case condition.

108
00:06:04,030 --> 00:06:06,170
Then, look at sum(5).

109
00:06:06,170 --> 00:06:09,270
Can you express it in terms
of another sum?

110
00:06:09,270 --> 00:06:11,290
Now, what about sum(4)?

111
00:06:11,290 --> 00:06:15,630
How can you express sum(4)
in terms of another sum?

112
00:06:15,630 --> 00:06:19,655
>> Once you have sum(5) and sum(4)
expressed in terms of other sums, see

113
00:06:19,655 --> 00:06:22,970
if you can identify a
pattern for sum(n).

114
00:06:22,970 --> 00:06:26,190
If not, try a few other numbers
and express their sums in

115
00:06:26,190 --> 00:06:28,410
terms of another numbers.

116
00:06:28,410 --> 00:06:31,930
By identifying patterns for discrete
numbers, you're well on your way to

117
00:06:31,930 --> 00:06:34,320
identifying the pattern for any n.

118
00:06:34,320 --> 00:06:38,040
>> Recursion's a really powerful tool,
so of course it's not limited to

119
00:06:38,040 --> 00:06:39,820
mathematical functions.

120
00:06:39,820 --> 00:06:44,040
Recursion can be used very effectively
when dealing with trees for instance.

121
00:06:44,040 --> 00:06:47,210
Check out the short on trees for a
more thorough review, but for now

122
00:06:47,210 --> 00:06:51,140
recall that binary search trees, in
particular, are made up of nodes, each

123
00:06:51,140 --> 00:06:53,820
with a value and two node pointers.

124
00:06:53,820 --> 00:06:57,270
Usually, this is represented by the
parent node having one line pointing

125
00:06:57,270 --> 00:07:01,870
to the left child node and one
to the right child node.

126
00:07:01,870 --> 00:07:04,510
The structure of a binary search
tree lends itself well

127
00:07:04,510 --> 00:07:05,940
to a recursive search.

128
00:07:05,940 --> 00:07:09,730
The recursive call either passes in the
left or the right node, but more

129
00:07:09,730 --> 00:07:10,950
of that in the tree short.

130
00:07:10,950 --> 00:07:15,690
>> Say you want to perform an operation on
every single node in a binary tree.

131
00:07:15,690 --> 00:07:17,410
How might you go about that?

132
00:07:17,410 --> 00:07:20,600
Well, you could write a recursive
function that performs the operation

133
00:07:20,600 --> 00:07:24,450
on the parent node and makes a recursive
call to the same function,

134
00:07:24,450 --> 00:07:27,630
passing in the left and
right child nodes.

135
00:07:27,630 --> 00:07:31,650
For example, this function, foo, that
changes the value of a given node and

136
00:07:31,650 --> 00:07:33,830
all of its children to 1.

137
00:07:33,830 --> 00:07:37,400
The base case of a null node causes
the function to return, indicating

138
00:07:37,400 --> 00:07:41,290
that there aren't any nodes
left in that sub-tree.

139
00:07:41,290 --> 00:07:42,620
>> Let's walk through it.

140
00:07:42,620 --> 00:07:44,340
The first parent is 13.

141
00:07:44,340 --> 00:07:47,930
We change the value to 1, and then call
our function on the left as well

142
00:07:47,930 --> 00:07:49,600
as the right.

143
00:07:49,600 --> 00:07:53,910
The function, foo, is called on the left
sub-tree first, so the left node

144
00:07:53,910 --> 00:07:57,730
will be reassigned to 1 and foo will
be called on that node's children,

145
00:07:57,730 --> 00:08:01,900
first the left and then the right,
and so on and so forth.

146
00:08:01,900 --> 00:08:05,630
And tell them that branches don't have
any more children so the same process

147
00:08:05,630 --> 00:08:09,700
will continue for the right children
until the whole tree's nodes are

148
00:08:09,700 --> 00:08:11,430
reassigned to 1.

149
00:08:11,430 --> 00:08:15,390
>> As you can see, you aren't limited
to just one recursive call.

150
00:08:15,390 --> 00:08:17,930
Just as many as will get the job done.

151
00:08:17,930 --> 00:08:21,200
What if you had a tree where each
node had three children,

152
00:08:21,200 --> 00:08:23,100
Left, middle, and right?

153
00:08:23,100 --> 00:08:24,886
How would you edit foo?

154
00:08:24,886 --> 00:08:25,860
Well, simple.

155
00:08:25,860 --> 00:08:30,250
Just add another recursive call and
pass in the middle node pointer.

156
00:08:30,250 --> 00:08:34,549
>> Recursion is very powerful and not to
mention elegant, but it can be a

157
00:08:34,549 --> 00:08:38,010
difficult concept at first, so be
patient and take your time.

158
00:08:38,010 --> 00:08:39,370
Start with the base case.

159
00:08:39,370 --> 00:08:42,650
It's usually the easiest to identify,
and then you can work

160
00:08:42,650 --> 00:08:43,830
backwards from there.

161
00:08:43,830 --> 00:08:46,190
You know you need to reach your
base case, so that might

162
00:08:46,190 --> 00:08:47,760
give you a few hints.

163
00:08:47,760 --> 00:08:53,120
Try to express one specific case in
terms of other cases, or in sub-sets.

164
00:08:53,120 --> 00:08:54,700
>> Thanks for watching this short.

165
00:08:54,700 --> 00:08:58,920
At the very least, now you can
understand jokes like this.

166
00:08:58,920 --> 00:09:01,250
My name is Zamyla, and this is cs50.

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> Take this function, hi, a
void function that takes

169
00:09:07,170 --> 00:09:09,212
an int, n, as input.

170
00:09:09,212 --> 00:09:11,020
The base case comes first.

171
00:09:11,020 --> 00:09:14,240
If n is less than 0, print
"bye" and return.

172
00:09:14,240 --> 00:09:15,490