1
00:00:00,950 --> 00:00:03,240
okay welcome back everybody

2
00:00:03,240 --> 00:00:06,670
to the next episode of FB 100 max

3
00:00:06,670 --> 00:00:10,700
and today we're going to talk about
recursive functions

4
00:00:10,700 --> 00:00:13,900
well what this recursion well I have a
year

5
00:00:13,900 --> 00:00:20,130
a stack of trace and my favorite fruits
by now you all know that I love bananas

6
00:00:20,130 --> 00:00:23,769
am and I need to eat this

7
00:00:23,769 --> 00:00:29,070
I am a whole bunch up but not and if we
going to do this recursively so it

8
00:00:29,070 --> 00:00:32,910
going to eat the first banana and then
old but

9
00:00:32,910 --> 00:00:36,500
before I do that I need to eat the next
banana

10
00:00:36,500 --> 00:00:39,950
0 so I can have to put this wrong

11
00:00:39,950 --> 00:00:43,440
on top of this tray and then I have to
eat

12
00:00:43,440 --> 00:00:49,390
the next banana I goodness I'm eating a
lot i bandanas and look at that stack

13
00:00:49,390 --> 00:00:52,520
growing their next but now on

14
00:00:52,520 --> 00:00:56,710
and finally I have my lost banana

15
00:00:56,710 --> 00:01:01,350
and I can put it on the stack and look
at is a beautiful stack

16
00:01:01,350 --> 00:01:05,049
of bananas see if you can

17
00:01:05,049 --> 00:01:09,430
see them ever a problem s that what we
have done here

18
00:01:09,430 --> 00:01:12,600
is we have created a quite a large

19
00:01:12,600 --> 00:01:17,810
stack a ban on us and if we would have a
big bunch have been honest that stack

20
00:01:17,810 --> 00:01:20,900
would overflow so better way

21
00:01:20,900 --> 00:01:24,240
to eat the bananas is to not

22
00:01:24,240 --> 00:01:28,350
start where the next banana until you've
finished

23
00:01:28,350 --> 00:01:31,829
the first run and in that case

24
00:01:31,829 --> 00:01:34,869
you only need want array

25
00:01:34,869 --> 00:01:38,500
to an finish all your but not us

26
00:01:38,500 --> 00:01:42,520
an and that is called bilkul elimination

27
00:01:42,520 --> 00:01:46,299
until go elimination is

28
00:01:46,299 --> 00:01:50,520
and a very important concept when you're
using recursion

29
00:01:50,520 --> 00:01:55,140
to define control structures and and an
imperative languages

30
00:01:55,140 --> 00:01:58,570
typically you don't have to a local and
the nation

31
00:01:58,570 --> 00:02:03,070
and therefore you have specialized
control structures but and has gone

32
00:02:03,070 --> 00:02:06,100
an we can define

33
00:02:06,100 --> 00:02:08,320
we can an

34
00:02:08,320 --> 00:02:12,510
safely define our control structures
using recursive functions

35
00:02:12,510 --> 00:02:16,620
an because we will never have this giant
stack

36
00:02:16,620 --> 00:02:21,620
of eat and ban on great let's look at
some got

37
00:02:21,620 --> 00:02:26,190
enough I i think i have had enough
bananas for the rest of the year

38
00:02:26,190 --> 00:02:29,860
and and the reason haskell

39
00:02:29,860 --> 00:02:32,990
forecastle of three cars in is dead

40
00:02:32,990 --> 00:02:36,610
often a very natural way an

41
00:02:36,610 --> 00:02:40,220
to define functions for example and

42
00:02:40,220 --> 00:02:43,900
here's a way to define

43
00:02:43,900 --> 00:02:48,290
and effect Aria functions are here
saigon we have seen this one before so

44
00:02:48,290 --> 00:02:49,500
we take the list

45
00:02:49,500 --> 00:02:52,630
values between 12 and and then

46
00:02:52,630 --> 00:02:59,210
we and multiply them all together if
we're going to evaluate

47
00:02:59,210 --> 00:03:03,620
this pictorial for we in unfolded
definition i watch

48
00:03:03,620 --> 00:03:10,620
product 124 and want the last month in
forest products I wanted 34

49
00:03:10,670 --> 00:03:13,680
an and the product lost

50
00:03:13,680 --> 00:03:16,830
just gonna yeah and multiplying all the
numbers

51
00:03:16,830 --> 00:03:20,080
so there you see the product Wong to

52
00:03:20,080 --> 00:03:23,260
34 is want times to times 3

53
00:03:23,260 --> 00:03:26,300
times for which is 24

54
00:03:26,300 --> 00:03:30,410
here's a way to define

55
00:03:30,410 --> 00:03:33,520
factorial using recursion I may have
seen

56
00:03:33,520 --> 00:03:37,800
am how did he find recursive functions
over lists and

57
00:03:37,800 --> 00:03:40,850
by taking the list checking whether to
take the

58
00:03:40,850 --> 00:03:45,020
and the last or whether it's the am had
followed by detail

59
00:03:45,020 --> 00:03:48,540
and in some sense this kind of recursive
function the

60
00:03:48,540 --> 00:03:51,880
rigors and function over numbers is
nothing different

61
00:03:51,880 --> 00:03:56,620
so if we have two cases we have the fact
whether in number is 0

62
00:03:56,620 --> 00:03:59,840
or in this case whether the number is an

63
00:03:59,840 --> 00:04:03,360
and in that case the recursion will be
on

64
00:04:03,360 --> 00:04:07,490
and mine is wrong and and

65
00:04:07,490 --> 00:04:10,740
in previous version of Haskell there
were so-called

66
00:04:10,740 --> 00:04:14,340
and bless gay patterns where you can
ride effect /url 0

67
00:04:14,340 --> 00:04:17,680
and the for burials and plus wrong but
am

68
00:04:17,680 --> 00:04:21,609
and bliss k patterns have been
deprecated so now I am

69
00:04:21,609 --> 00:04:25,189
will have derided an and this for but

70
00:04:25,189 --> 00:04:30,229
apart from that minor detail what you
can see is that it's

71
00:04:30,229 --> 00:04:33,719
very very similar do the way and

72
00:04:33,719 --> 00:04:36,909
you define recursion over lists

73
00:04:36,909 --> 00:04:39,960
two cases here are

74
00:04:39,960 --> 00:04:43,949
and an and if it's the right Swan an
otherwise

75
00:04:43,949 --> 00:04:47,530
you just take the factorial and mine is
wrong times

76
00:04:47,530 --> 00:04:52,020
and and if we evaluate

77
00:04:52,020 --> 00:04:56,430
this form of vectorial you'll see that
stack

78
00:04:56,430 --> 00:05:01,050
of bananas and appearing because you
know you see that there's an hour

79
00:05:01,050 --> 00:05:04,759
there's the factorial an going to the
rides

80
00:05:04,759 --> 00:05:08,039
until we have executed everything

81
00:05:08,039 --> 00:05:12,279
and an me multiply going back

82
00:05:12,279 --> 00:05:15,509
popping off the stack to get back to six

83
00:05:15,509 --> 00:05:18,810
are at

84
00:05:18,810 --> 00:05:21,870
the recursive definition

85
00:05:21,870 --> 00:05:25,069
that we have given of course well

86
00:05:25,069 --> 00:05:30,810
not terminated RN a fancy way to say
that it will diverge

87
00:05:30,810 --> 00:05:33,860
an four numbers less than zero

88
00:05:33,860 --> 00:05:37,930
and if we look here let's go back

89
00:05:37,930 --> 00:05:42,110
a few slides and if and

90
00:05:42,110 --> 00:05:45,539
is less than 0 then we just

91
00:05:45,539 --> 00:05:51,039
yeah then this case doesn't apply so we
multiply and where its de facto realtor

92
00:05:51,039 --> 00:05:52,099
and minus ROM

93
00:05:52,099 --> 00:05:56,229
which is even more or less than zero and
so on and so on so this will never

94
00:05:56,229 --> 00:05:57,099
terminated

95
00:05:57,099 --> 00:06:04,099
and well 'cause a stackoverflow so

96
00:06:05,110 --> 00:06:09,060
some functions and like Victoria can be
defined

97
00:06:09,060 --> 00:06:12,529
either recursively or defiant in terms

98
00:06:12,529 --> 00:06:15,740
of an other functions and

99
00:06:15,740 --> 00:06:19,379
whether you define something using
recursion

100
00:06:19,379 --> 00:06:22,879
or in terms of other functions or you d

101
00:06:22,879 --> 00:06:25,990
take you know you you take this regard
him pattern

102
00:06:25,990 --> 00:06:28,710
and abstracted as a higher r2 function
and

103
00:06:28,710 --> 00:06:32,570
then use it to the final function that's
all a matter of taste

104
00:06:32,570 --> 00:06:35,920
and the and you decide as a developer

105
00:06:35,920 --> 00:06:38,960
wats is the most readable

106
00:06:38,960 --> 00:06:42,510
for other developers alright and

107
00:06:42,510 --> 00:06:48,020
so there's no your strong answer when
are not to use recursion

108
00:06:48,020 --> 00:06:51,070
the code just has to be as clear as
possible

109
00:06:51,070 --> 00:06:55,490
but Wong advantage of recursion is that
you can use

110
00:06:55,490 --> 00:06:58,990
and induction to prove properties

111
00:06:58,990 --> 00:07:03,130
am of your function let's

112
00:07:03,130 --> 00:07:06,890
look at another example of defining a
recursive function

113
00:07:06,890 --> 00:07:10,890
and where we're using this product
function that we

114
00:07:10,890 --> 00:07:14,540
used in there and earlier definition

115
00:07:14,540 --> 00:07:17,800
of vectorial and let's define that

116
00:07:17,800 --> 00:07:23,310
using recursion over lists so in this
case the structures exactly the same

117
00:07:23,310 --> 00:07:23,640
their

118
00:07:23,640 --> 00:07:26,720
two cases we either have the empty last

119
00:07:26,720 --> 00:07:29,960
or we have a list of an gongs ans

120
00:07:29,960 --> 00:07:34,360
an so we look at the recursive structure
molests

121
00:07:34,360 --> 00:07:39,180
and then we define the function over
that triggers a structure

122
00:07:39,180 --> 00:07:43,060
and the same with numbers we look at the
rigors a structure of numbers

123
00:07:43,060 --> 00:07:46,890
and then we define the functions gonna
according to that structure

124
00:07:46,890 --> 00:07:50,690
in this case if we have the product of
the anti last

125
00:07:50,690 --> 00:07:54,860
well that this Wong everyone to

126
00:07:54,860 --> 00:07:59,290
take the product Ave value and on top of
the list

127
00:07:59,290 --> 00:08:02,380
ants what do we do we take the product

128
00:08:02,380 --> 00:08:06,340
of the rest of the list here and then we
multiply that by an

129
00:08:06,340 --> 00:08:09,910
writer this is a very easy way

130
00:08:09,910 --> 00:08:13,340
to define this function using recursion

131
00:08:13,340 --> 00:08:17,040
an and of course you know

132
00:08:17,040 --> 00:08:20,370
as you will see we can take dysfunction
and

133
00:08:20,370 --> 00:08:24,780
abstract the pattern into a hierarchy
function that just does the recursion

134
00:08:24,780 --> 00:08:26,200
and then we can plug in

135
00:08:26,200 --> 00:08:31,080
the the times and the one but if we

136
00:08:31,080 --> 00:08:36,000
executed this product be unfolds the
definition

137
00:08:36,000 --> 00:08:39,080
Rights Act two Gomes 34

138
00:08:39,080 --> 00:08:41,860
so every unfold that a couple of times
you get to

139
00:08:41,860 --> 00:08:45,490
dimes brother got 34 me that a couple of
times

140
00:08:45,490 --> 00:08:49,160
until we arrive here and then

141
00:08:49,160 --> 00:08:53,220
bebop to stack to get 24 alright

142
00:08:53,220 --> 00:08:57,220
so you see that the answer is exactly
the same

143
00:08:57,220 --> 00:09:00,850
as the rigors if Anna definition of
Victoria

144
00:09:00,850 --> 00:09:05,079
the only thing is that in this case the
recursion

145
00:09:05,079 --> 00:09:09,170
is hidden in this product function if we
take the product

146
00:09:09,170 --> 00:09:13,310
of the numbers 12 and really we're
defining

147
00:09:13,310 --> 00:09:17,329
the function using recursion as Ron UK
show that way you do

148
00:09:17,329 --> 00:09:20,980
when you few states to function is the
function that creates a lesser amount to

149
00:09:20,980 --> 00:09:21,410
an

150
00:09:21,410 --> 00:09:24,980
and the product function that what you
get is effectively

151
00:09:24,980 --> 00:09:30,170
their recursive definition of Victoria
yet

152
00:09:30,170 --> 00:09:34,360
as again another function an that we can
define

153
00:09:34,360 --> 00:09:37,680
recursively over lists an

154
00:09:37,680 --> 00:09:41,019
and here you see again we have this and

155
00:09:41,019 --> 00:09:45,050
recursive structure so if it's empty the
less is empty

156
00:09:45,050 --> 00:09:49,360
well the length of that empty list 0 and

157
00:09:49,360 --> 00:09:52,449
list is not anti we don't care really

158
00:09:52,449 --> 00:09:57,370
well the first element this we compute
the length of the rest in the last

159
00:09:57,370 --> 00:10:01,740
and just add to want to it super obvious

160
00:10:01,740 --> 00:10:05,310
again it follows the recursive structure

161
00:10:05,310 --> 00:10:08,480
of the list so it's kind of defined by
induction

162
00:10:08,480 --> 00:10:14,079
a on on the structure of the list soul
and don't want the jury

163
00:10:14,079 --> 00:10:18,480
on plus Langkow 23 unfold unfold and
fault

164
00:10:18,480 --> 00:10:21,600
until here and then we add them up

165
00:10:21,600 --> 00:10:27,610
and we get to the answer that we expect
three here's another function

166
00:10:27,610 --> 00:10:30,800
and reverse and the list

167
00:10:30,800 --> 00:10:33,870
River have them to Liz's MD lest

168
00:10:33,870 --> 00:10:38,920
and everyone to reverse and ex-con six
ish

169
00:10:38,920 --> 00:10:42,199
we just Addax on the other side

170
00:10:42,199 --> 00:10:45,890
so every actually good at like this you
see

171
00:10:45,890 --> 00:10:49,180
that were offending the elements

172
00:10:49,180 --> 00:10:53,380
from right to left right to left

173
00:10:53,380 --> 00:10:56,450
and and and the list gets reversed

174
00:10:56,450 --> 00:10:59,630
so wanted three there's into 321

175
00:10:59,630 --> 00:11:02,950
of course

176
00:11:02,950 --> 00:11:06,140
we can also define recursive function
that are not dead

177
00:11:06,140 --> 00:11:09,990
don't three cars over just one argument
but over several

178
00:11:09,990 --> 00:11:13,050
if seen in the previous chapter the
function zip

179
00:11:13,050 --> 00:11:16,980
how do is define Sep 12 zip to do lists

180
00:11:16,980 --> 00:11:21,470
and it would take every element of the
two less and combine them into a pair

181
00:11:21,470 --> 00:11:27,240
am so easiest thing here's a look at the
lost

182
00:11:27,240 --> 00:11:30,450
class here so if we have to non-empty
lest

183
00:11:30,450 --> 00:11:34,760
we take the heads of both with that in a
bear

184
00:11:34,760 --> 00:11:39,370
and recursion only ship the rest now
when do we stop well we stop

185
00:11:39,370 --> 00:11:43,070
when either of the two lists is
exhausted

186
00:11:43,070 --> 00:11:46,080
in which case re return the empty list

187
00:11:46,080 --> 00:11:49,460
again and of course we have to point

188
00:11:49,460 --> 00:11:53,340
these cases first here because there's a
wild-card

189
00:11:53,340 --> 00:11:57,360
pattern here that would otherwise am not
work

190
00:11:57,360 --> 00:12:00,370
good

191
00:12:00,370 --> 00:12:04,160
a few more functions

192
00:12:04,160 --> 00:12:07,850
drop takes an integer and the last

193
00:12:07,850 --> 00:12:13,160
and return Celeste ever testing is doing
its rigor sing over

194
00:12:13,160 --> 00:12:16,360
and both

195
00:12:16,360 --> 00:12:20,180
the integer and the list so in this case

196
00:12:20,180 --> 00:12:24,460
when we say we want to drop to zero
elements for molest

197
00:12:24,460 --> 00:12:29,320
well that's the same lest if we have the
empty list

198
00:12:29,320 --> 00:12:32,370
we can drop whatever we want but you
know we won't get

199
00:12:32,370 --> 00:12:36,250
very far so we just return the empty
lest and otherwise

200
00:12:36,250 --> 00:12:40,200
we're eager balls over the last and over
new number

201
00:12:40,200 --> 00:12:45,070
and again since we don't have and plus
que patterns we have to use and -1 here

202
00:12:45,070 --> 00:12:47,290
on the right hand side so drop off and

203
00:12:47,290 --> 00:12:51,200
and whatever gone axis as drop-off

204
00:12:51,200 --> 00:12:55,040
and minus wrong and access so here we
rikers

205
00:12:55,040 --> 00:12:58,600
over the structure of the number and the
structure

206
00:12:58,600 --> 00:13:00,860
of the list

207
00:13:00,860 --> 00:13:03,910
an the last exam player on the slide am

208
00:13:03,910 --> 00:13:07,040
a-bands to last if I want to

209
00:13:07,040 --> 00:13:11,480
a band dnt less to another list that is
the other last

210
00:13:11,480 --> 00:13:15,590
and then if I want to upend a list
ex-cons X ish

211
00:13:15,590 --> 00:13:19,990
to a less twice while I do I do I first
a band axis2 wise

212
00:13:19,990 --> 00:13:24,190
and then columns action on top super
obvious

213
00:13:24,190 --> 00:13:27,960
nigga so much and see a

214
00:13:27,960 --> 00:13:28,610
in part two