1
00:00:01,710 --> 00:00:08,100
OK, now let's take a look at function recursion, so what would happen if you had a function and that

2
00:00:08,100 --> 00:00:10,010
function called itself?

3
00:00:10,740 --> 00:00:12,810
That's what's called function recursion.

4
00:00:14,090 --> 00:00:16,040
So let's take a look at a quick example.

5
00:00:17,710 --> 00:00:23,350
So we have a function here called Go Forever, and all it does is called Go Forever.

6
00:00:24,430 --> 00:00:29,110
And then somewhere else, you have to kick it off, the function can't kick itself off, so somewhere

7
00:00:29,110 --> 00:00:34,760
else you can't go forever, it starts to go forever function, and then it just runs forever.

8
00:00:35,980 --> 00:00:38,860
So if you really do this, of course, you have to find a way to make it end.

9
00:00:39,040 --> 00:00:41,700
So let's take a look at some examples of how this works.

10
00:00:43,610 --> 00:00:50,540
OK, so let's try something really simple, so we'll create a function and start calling and go forever.

11
00:00:50,660 --> 00:00:54,440
We'll call it go for a while

12
00:00:57,920 --> 00:01:02,260
and let's take a parameter or just call data.

13
00:01:06,230 --> 00:01:09,950
And then here we're going to subtract one from value.

14
00:01:13,020 --> 00:01:27,930
And I'm going to say, if value equals zero return, if you don't return, we're going to go for a while

15
00:01:28,500 --> 00:01:29,600
and send in the value.

16
00:01:32,220 --> 00:01:35,790
So this is going to run a certain number of times depending on what the initial value is.

17
00:01:36,960 --> 00:01:44,940
So let's take a look at that some years ago for a while and what Sen. Ted.

18
00:01:46,830 --> 00:01:50,380
And then here, before we start decorating it, blog out what the value is.

19
00:01:56,100 --> 00:01:57,510
So let's go ahead and run this.

20
00:02:00,100 --> 00:02:05,170
I'll just click one whole world in here puts ten, nine, eight, seven, six, five, four, three,

21
00:02:05,170 --> 00:02:05,770
two, one.

22
00:02:05,950 --> 00:02:08,990
And then it doesn't turn out zero because it it ends at that point.

23
00:02:10,000 --> 00:02:11,620
So what's going on here?

24
00:02:14,540 --> 00:02:20,110
So let's go ahead and say to break in our hello before we even call the first time and let's run it.

25
00:02:22,510 --> 00:02:23,980
So we're here, we're ready to run.

26
00:02:24,360 --> 00:02:32,170
We're going to pass in the value of ten, so you step forward to step in and our values ten, so we

27
00:02:32,190 --> 00:02:32,950
vote that out.

28
00:02:33,160 --> 00:02:34,600
So now that's in the log.

29
00:02:35,530 --> 00:02:36,190
Right there.

30
00:02:37,280 --> 00:02:38,890
We're going to subtract one from Dalu.

31
00:02:41,230 --> 00:02:44,800
And now you can see over here and the locals that the value is nine.

32
00:02:46,940 --> 00:02:48,110
And then we did check.

33
00:02:49,330 --> 00:02:55,210
And then we're going to go for a while again, I'm going to hit f 11 to step in and then we're just

34
00:02:55,210 --> 00:02:56,090
right back here again.

35
00:02:56,320 --> 00:03:01,720
Here's the value and it's nine and we're going to go.

36
00:03:02,700 --> 00:03:03,420
Well, get out.

37
00:03:03,620 --> 00:03:05,440
Strike one, it's not zero.

38
00:03:06,210 --> 00:03:09,510
Now, here's a part of the debugger that you haven't seen before.

39
00:03:09,550 --> 00:03:14,100
You I haven't shown you anyway, and it's called the call stack.

40
00:03:15,030 --> 00:03:19,020
And what's going on here in the call stack is we started at hello.

41
00:03:19,890 --> 00:03:23,090
And then we went to go for a while and now we go for a while again.

42
00:03:23,100 --> 00:03:25,650
And originally we started at the unclick.

43
00:03:26,130 --> 00:03:27,300
That's in the HTML.

44
00:03:27,840 --> 00:03:29,780
So it's just saying what's called what.

45
00:03:30,540 --> 00:03:32,700
So Unclick called hello.

46
00:03:32,700 --> 00:03:35,460
Hello Kulka for a while, go for a while called.

47
00:03:35,460 --> 00:03:36,510
Go for a while again.

48
00:03:37,140 --> 00:03:41,550
And if I click on these you can see that the value at each one is shown.

49
00:03:41,550 --> 00:03:44,130
So the value at this go for a while is nine.

50
00:03:44,730 --> 00:03:45,860
At this one it's eight.

51
00:03:46,680 --> 00:03:51,180
So let's go, keep stepping in for a little bit as another go for a while.

52
00:03:52,140 --> 00:03:53,610
As another go for a while.

53
00:03:56,040 --> 00:03:56,880
And so on.

54
00:03:57,810 --> 00:04:02,280
So it's going to keep running until the point where value becomes zero.

55
00:04:11,100 --> 00:04:14,000
She was right about you not to.

56
00:04:20,060 --> 00:04:22,460
OK, now zero is going to the return.

57
00:04:24,080 --> 00:04:29,180
So if I click on these go for a wild, little bigger.

58
00:04:31,050 --> 00:04:36,810
This one that I use zero, this one is one, and if I keep going back, it's going to keep going back

59
00:04:36,810 --> 00:04:38,100
to this original that is.

60
00:04:38,640 --> 00:04:45,420
Now what's going to happen here is we're returning and each one of these off the call stack pops off.

61
00:04:45,420 --> 00:04:48,030
It's a stack return.

62
00:04:49,600 --> 00:04:54,550
So you could see that it's showing us the value of three, if you look at the COL stack here, it's

63
00:04:54,550 --> 00:04:55,690
going to keep getting shorter.

64
00:04:59,090 --> 00:05:05,510
Until we get to the original one, which was the first one that we called, and then we go back to hello.

65
00:05:06,770 --> 00:05:08,990
OK, let's do something practical with this.

66
00:05:11,730 --> 00:05:16,410
This back and what we do is we'll get rid of this.

67
00:05:16,820 --> 00:05:24,120
Back to almost where we were and there's a lot of algorithms that use recursion in a really simple one

68
00:05:24,120 --> 00:05:25,830
is called a binary search.

69
00:05:26,670 --> 00:05:36,870
And with a binary search, it says you have a list of say, let's list equals an array and a binary

70
00:05:36,870 --> 00:05:37,170
search.

71
00:05:37,170 --> 00:05:39,870
The array has to be already sorted in order.

72
00:05:40,920 --> 00:05:47,550
So I'm going to put some numbers in here to kind of six comma nine comma 12 comma 17 comma.

73
00:05:47,550 --> 00:05:48,180
Twenty two.

74
00:05:48,750 --> 00:05:50,910
Twenty eight comma.

75
00:05:50,910 --> 00:05:52,500
Thirty three comma.

76
00:05:52,830 --> 00:05:54,540
Thirty nine comma.

77
00:05:54,930 --> 00:05:57,360
Forty one comma forty five.

78
00:05:57,810 --> 00:05:58,640
Forty eight.

79
00:05:58,650 --> 00:06:00,620
And trying to get a bunch of numbers in here.

80
00:06:01,050 --> 00:06:02,460
So bear with me for a minute.

81
00:06:08,280 --> 00:06:12,320
OK, so we've got a list that looks like there's maybe 15 numbers in there or something.

82
00:06:13,110 --> 00:06:22,110
And what we want to do is find the number in the list and just essentially say we found it all the time

83
00:06:22,560 --> 00:06:23,640
in computer programs.

84
00:06:23,640 --> 00:06:26,640
You're searching for something and bringing it back when you find it.

85
00:06:27,210 --> 00:06:28,710
And often it'll be an object.

86
00:06:29,190 --> 00:06:30,710
So in this case, it's just a number.

87
00:06:32,160 --> 00:06:33,780
So let's go ahead and do this.

88
00:06:33,780 --> 00:06:42,510
So what how this works is we're going to create a function and we'll just call search and we're going

89
00:06:42,510 --> 00:06:43,740
to pass in a list.

90
00:06:47,490 --> 00:06:53,640
And then in the list, what we're going to do is look at the very center item and we're going to see

91
00:06:53,640 --> 00:06:55,410
if it is the very center item.

92
00:06:56,100 --> 00:07:08,880
So we're going to say let middle equals list and then we're going to to go that length divided by two.

93
00:07:09,870 --> 00:07:13,620
And we wanted to have a integer number.

94
00:07:13,620 --> 00:07:16,420
We don't want to have, like, you know, three point five.

95
00:07:17,190 --> 00:07:26,880
So what we want to do is use a math function called math math DOT four, which is going to say take

96
00:07:26,880 --> 00:07:31,860
it down to the nearest whole number below that to the floor.

97
00:07:32,610 --> 00:07:37,560
I think there's a ceiling function, too, that will take it up or around function and those sorts of

98
00:07:37,560 --> 00:07:37,860
things.

99
00:07:38,820 --> 00:07:43,020
So if the list is 15 in length, it's going to be turned seven.

100
00:07:43,950 --> 00:07:45,450
So now we have a middle.

101
00:07:45,450 --> 00:07:49,310
We're just going to say, hey, is is the middle is that is that what we're looking for?

102
00:07:49,350 --> 00:07:50,640
If it is, we're going to return it.

103
00:07:51,600 --> 00:07:53,370
So we say if

104
00:07:55,890 --> 00:07:56,520
list.

105
00:07:57,840 --> 00:07:58,900
So middle

106
00:08:01,960 --> 00:08:07,840
equals and we have to pass them over looking for a search.

107
00:08:08,180 --> 00:08:10,030
No says no.

108
00:08:10,030 --> 00:08:10,810
We're looking for.

109
00:08:13,930 --> 00:08:17,300
So if it is the search number, we're going to return the search now.

110
00:08:21,940 --> 00:08:27,910
And before we do this, before we even try this, what we should do is say, hey, if the list is now

111
00:08:27,910 --> 00:08:31,260
empty, just returned, I don't know.

112
00:08:34,560 --> 00:08:47,790
We'll return then another number, so if left, that wing equals zero return.

113
00:08:49,300 --> 00:08:50,470
Not a no.

114
00:08:53,130 --> 00:08:59,130
All right, so it's not in the middle, so since this is a sorted list, it's got to be there to the

115
00:08:59,130 --> 00:09:00,480
left and the left to the right.

116
00:09:00,480 --> 00:09:06,270
If we're looking at this one and we're searching for 22, it's got to be on this side of the list for

117
00:09:06,270 --> 00:09:07,630
searching for 66.

118
00:09:07,650 --> 00:09:08,940
It's got to be on that side list.

119
00:09:09,480 --> 00:09:13,760
So we're going to do is RECURSE and we're going to call search again and pass it.

120
00:09:14,250 --> 00:09:18,210
The other portion of the list, the portion of the list where we know the number is the word Oraibi.

121
00:09:19,050 --> 00:09:21,510
So then we're going to say if

122
00:09:24,810 --> 00:09:30,990
search search known is less than list some middle.

123
00:09:36,370 --> 00:09:41,080
Then we're going to call search with search now in that part of the list.

124
00:09:42,410 --> 00:09:53,150
So if a search search numb and then we're going to use the slice to get the list that we want to lift

125
00:09:53,150 --> 00:09:54,210
that slice.

126
00:09:55,670 --> 00:09:57,770
Let's take a look at the documentation for Slice.

127
00:09:59,560 --> 00:10:05,370
So here's the documentation for Slice, it returns a portion of an array into the new array object,

128
00:10:06,010 --> 00:10:12,010
so you say the start in the end, we know the starts can be zero because that's the beginning of the

129
00:10:12,010 --> 00:10:13,390
right, the end.

130
00:10:13,390 --> 00:10:14,860
It's one before the end.

131
00:10:15,460 --> 00:10:19,390
So we want to the middle position to be the end.

132
00:10:22,690 --> 00:10:33,700
So we'll say zero microsurgeon here, zero comma middle.

133
00:10:35,440 --> 00:10:37,510
And that's going to it's not going to include middle.

134
00:10:41,360 --> 00:10:45,470
So you can see here in the documentation, the substrate includes characters up to, but not including

135
00:10:45,470 --> 00:10:46,820
the character indicated by the end.

136
00:10:47,630 --> 00:10:49,070
Thanks for doing a string, but we're not.

137
00:10:50,270 --> 00:10:51,590
So we're going to call that.

138
00:10:52,430 --> 00:10:54,050
And we want to do is we don't want to just call.

139
00:10:54,080 --> 00:10:58,940
We want to return it, because when we find this, we're returning it.

140
00:10:59,480 --> 00:11:06,770
So the returning man or and I don't know, I missed the return here or are we going to return the search

141
00:11:06,770 --> 00:11:07,090
now?

142
00:11:07,910 --> 00:11:11,720
So whenever we find it, it's going to get returned to we want to return it here.

143
00:11:15,150 --> 00:11:30,900
OK, otherwise, health return, search, search, no less, that flies and we want to go middle plus

144
00:11:30,900 --> 00:11:31,350
one

145
00:11:34,440 --> 00:11:38,350
and we don't have to specify the second parameter, it's just going to go to that.

146
00:11:43,530 --> 00:11:47,490
All right, and then up here, we just need to search for it so we can say

147
00:11:50,400 --> 00:11:55,920
consed search equals prompt.

148
00:11:58,330 --> 00:12:02,620
What number are you looking for?

149
00:12:04,780 --> 00:12:11,830
So we search for it and I say run the search and store the return value of.

150
00:12:14,980 --> 00:12:29,230
Found value equals search a search value in the list and then at the end will just say cancel that log.

151
00:12:32,910 --> 00:12:38,990
Found some value, and if we end up with an end, we didn't find it.

152
00:12:40,970 --> 00:12:42,230
All right, let's kind of run this.

153
00:12:45,020 --> 00:12:51,920
And the Tea Party guys, let's get rid of that break, because that's where we want it anyway.

154
00:12:54,220 --> 00:12:54,610
All right.

155
00:12:56,930 --> 00:13:05,170
So we'll say run hello, world will search for 20 to find some doing something a little bit wrong here,

156
00:13:05,180 --> 00:13:06,410
we're going to have to figure that out.

157
00:13:06,950 --> 00:13:08,240
Oh, I know what the problem is already.

158
00:13:08,780 --> 00:13:12,830
We're getting a string, so we may as well just fix that.

159
00:13:14,480 --> 00:13:15,390
We need a number.

160
00:13:15,410 --> 00:13:16,190
We're getting a straight.

161
00:13:17,820 --> 00:13:23,580
So we're going to just go in here and say, no, that pass and

162
00:13:27,360 --> 00:13:27,930
search.

163
00:13:29,410 --> 00:13:31,050
So let's hit that fixes the problem.

164
00:13:35,180 --> 00:13:37,960
Run Type 22 again.

165
00:13:40,690 --> 00:13:43,560
And breaking, I don't really want.

166
00:13:45,230 --> 00:13:47,920
And we found it, so I searched for something else.

167
00:13:51,100 --> 00:13:51,760
33.

168
00:13:54,740 --> 00:13:55,370
Thirty three.

169
00:13:57,230 --> 00:14:00,040
But search for something else, something that we know doesn't exist.

170
00:14:02,280 --> 00:14:03,390
And that returns to Dan.

171
00:14:04,620 --> 00:14:08,760
All right, let's take a just a couple minutes and kind of step through this to get an idea what he's

172
00:14:08,760 --> 00:14:09,120
doing.

173
00:14:10,000 --> 00:14:13,050
So I'm going to back in Chrome.

174
00:14:13,620 --> 00:14:14,640
I'm going to set a break.

175
00:14:17,980 --> 00:14:19,330
And it will sit right here.

176
00:14:19,750 --> 00:14:21,130
Here, here.

177
00:14:22,810 --> 00:14:25,960
Well, run and search for nine.

178
00:14:28,710 --> 00:14:30,760
OK, so we got our found value.

179
00:14:31,170 --> 00:14:33,390
I'm sorry, we have a search value, it's a string.

180
00:14:33,390 --> 00:14:36,350
That's why I do this part, to make it into a number.

181
00:14:37,410 --> 00:14:40,750
So step in and we can see over here.

182
00:14:40,800 --> 00:14:42,060
Let's close the call stack.

183
00:14:43,170 --> 00:14:46,920
We have our list, we have our search now, Middle's undefiled.

184
00:14:48,570 --> 00:14:55,800
All right, so let's get a view from middle C, middle is nine and if not the number nine, position

185
00:14:55,800 --> 00:14:56,090
nine.

186
00:14:56,100 --> 00:14:58,260
So whatever the ninth index is.

187
00:14:59,550 --> 00:15:03,450
So we'll say if there's nothing left in the list.

188
00:15:05,650 --> 00:15:10,090
If the middle is the search, none, so listen middle.

189
00:15:11,220 --> 00:15:13,200
So with that, nine is forty one.

190
00:15:14,920 --> 00:15:16,390
So it's not going to be the search.

191
00:15:18,900 --> 00:15:22,360
Not getting that lucky yet, so the search no less than this.

192
00:15:22,380 --> 00:15:29,960
It is so we want to do is take a slice of that array and pass it back in through recursion.

193
00:15:30,900 --> 00:15:32,860
And now you can see our list got a lot shorter.

194
00:15:33,690 --> 00:15:34,890
It's two, three.

195
00:15:34,890 --> 00:15:35,520
Thirty nine.

196
00:15:37,710 --> 00:15:45,090
So we'll step again is our middle is now for these are less separate?

197
00:15:45,240 --> 00:15:49,950
No, it's going to be 17, so it's going to go on.

198
00:15:51,810 --> 00:15:57,990
And is it less it's less so we're going again now we have two, six, nine, 12.

199
00:15:59,190 --> 00:16:00,270
So our middle.

200
00:16:01,640 --> 00:16:03,170
Is going to be two.

201
00:16:04,980 --> 00:16:06,360
So in our list.

202
00:16:07,850 --> 00:16:11,150
Zero one two is the nine, so it finds it.

203
00:16:13,580 --> 00:16:20,830
And it's going to return that so everything just returns out and we end up with our found value of not.

204
00:16:23,350 --> 00:16:28,630
So that's an introduction to recursion, along with a standard algorithm to do a binary search.