okay welcome back everybody
to the next episode of FB 100 max
and today we're going to talk about recursive functions
well what this recursion well I have a year
a stack of trace and my favorite fruits by now you all know that I love bananas
am and I need to eat this
I am a whole bunch up but not and if we going to do this recursively so it
going to eat the first banana and then old but
before I do that I need to eat the next banana
0 so I can have to put this wrong
on top of this tray and then I have to eat
the next banana I goodness I'm eating a lot i bandanas and look at that stack
growing their next but now on
and finally I have my lost banana
and I can put it on the stack and look at is a beautiful stack
of bananas see if you can
see them ever a problem s that what we have done here
is we have created a quite a large
stack a ban on us and if we would have a big bunch have been honest that stack
would overflow so better way
to eat the bananas is to not
start where the next banana until you've finished
the first run and in that case
you only need want array
to an finish all your but not us
an and that is called bilkul elimination
until go elimination is
and a very important concept when you're using recursion
to define control structures and and an imperative languages
typically you don't have to a local and the nation
and therefore you have specialized control structures but and has gone
an we can define
we can an
safely define our control structures using recursive functions
an because we will never have this giant stack
of eat and ban on great let's look at some got
enough I i think i have had enough bananas for the rest of the year
and and the reason haskell
forecastle of three cars in is dead
often a very natural way an
to define functions for example and
here's a way to define
and effect Aria functions are here saigon we have seen this one before so
we take the list
values between 12 and and then
we and multiply them all together if we're going to evaluate
this pictorial for we in unfolded definition i watch
product 124 and want the last month in forest products I wanted 34
an and the product lost
just gonna yeah and multiplying all the numbers
so there you see the product Wong to
34 is want times to times 3
times for which is 24
here's a way to define
factorial using recursion I may have seen
am how did he find recursive functions over lists and
by taking the list checking whether to take the
and the last or whether it's the am had followed by detail
and in some sense this kind of recursive function the
rigors and function over numbers is nothing different
so if we have two cases we have the fact whether in number is 0
or in this case whether the number is an
and in that case the recursion will be on
and mine is wrong and and
in previous version of Haskell there were so-called
and bless gay patterns where you can ride effect /url 0
and the for burials and plus wrong but am
and bliss k patterns have been deprecated so now I am
will have derided an and this for but
apart from that minor detail what you can see is that it's
very very similar do the way and
you define recursion over lists
two cases here are
and an and if it's the right Swan an otherwise
you just take the factorial and mine is wrong times
and and if we evaluate
this form of vectorial you'll see that stack
of bananas and appearing because you know you see that there's an hour
there's the factorial an going to the rides
until we have executed everything
and an me multiply going back
popping off the stack to get back to six
are at
the recursive definition
that we have given of course well
not terminated RN a fancy way to say that it will diverge
an four numbers less than zero
and if we look here let's go back
a few slides and if and
is less than 0 then we just
yeah then this case doesn't apply so we multiply and where its de facto realtor
and minus ROM
which is even more or less than zero and so on and so on so this will never
terminated
and well 'cause a stackoverflow so
some functions and like Victoria can be defined
either recursively or defiant in terms
of an other functions and
whether you define something using recursion
or in terms of other functions or you d
take you know you you take this regard him pattern
and abstracted as a higher r2 function and
then use it to the final function that's all a matter of taste
and the and you decide as a developer
wats is the most readable
for other developers alright and
so there's no your strong answer when are not to use recursion
the code just has to be as clear as possible
but Wong advantage of recursion is that you can use
and induction to prove properties
am of your function let's
look at another example of defining a recursive function
and where we're using this product function that we
used in there and earlier definition
of vectorial and let's define that
using recursion over lists so in this case the structures exactly the same
their
two cases we either have the empty last
or we have a list of an gongs ans
an so we look at the recursive structure molests
and then we define the function over that triggers a structure
and the same with numbers we look at the rigors a structure of numbers
and then we define the functions gonna according to that structure
in this case if we have the product of the anti last
well that this Wong everyone to
take the product Ave value and on top of the list
ants what do we do we take the product
of the rest of the list here and then we multiply that by an
writer this is a very easy way
to define this function using recursion
an and of course you know
as you will see we can take dysfunction and
abstract the pattern into a hierarchy function that just does the recursion
and then we can plug in
the the times and the one but if we
executed this product be unfolds the definition
Rights Act two Gomes 34
so every unfold that a couple of times you get to
dimes brother got 34 me that a couple of times
until we arrive here and then
bebop to stack to get 24 alright
so you see that the answer is exactly the same
as the rigors if Anna definition of Victoria
the only thing is that in this case the recursion
is hidden in this product function if we take the product
of the numbers 12 and really we're defining
the function using recursion as Ron UK show that way you do
when you few states to function is the function that creates a lesser amount to
an
and the product function that what you get is effectively
their recursive definition of Victoria yet
as again another function an that we can define
recursively over lists an
and here you see again we have this and
recursive structure so if it's empty the less is empty
well the length of that empty list 0 and
list is not anti we don't care really
well the first element this we compute the length of the rest in the last
and just add to want to it super obvious
again it follows the recursive structure
of the list so it's kind of defined by induction
a on on the structure of the list soul and don't want the jury
on plus Langkow 23 unfold unfold and fault
until here and then we add them up
and we get to the answer that we expect three here's another function
and reverse and the list
River have them to Liz's MD lest
and everyone to reverse and ex-con six ish
we just Addax on the other side
so every actually good at like this you see
that were offending the elements
from right to left right to left
and and and the list gets reversed
so wanted three there's into 321
of course
we can also define recursive function that are not dead
don't three cars over just one argument but over several
if seen in the previous chapter the function zip
how do is define Sep 12 zip to do lists
and it would take every element of the two less and combine them into a pair
am so easiest thing here's a look at the lost
class here so if we have to non-empty lest
we take the heads of both with that in a bear
and recursion only ship the rest now when do we stop well we stop
when either of the two lists is exhausted
in which case re return the empty list
again and of course we have to point
these cases first here because there's a wild-card
pattern here that would otherwise am not work
good
a few more functions
drop takes an integer and the last
and return Celeste ever testing is doing its rigor sing over
and both
the integer and the list so in this case
when we say we want to drop to zero elements for molest
well that's the same lest if we have the empty list
we can drop whatever we want but you know we won't get
very far so we just return the empty lest and otherwise
we're eager balls over the last and over new number
and again since we don't have and plus que patterns we have to use and -1 here
on the right hand side so drop off and
and whatever gone axis as drop-off
and minus wrong and access so here we rikers
over the structure of the number and the structure
of the list
an the last exam player on the slide am
a-bands to last if I want to
a band dnt less to another list that is the other last
and then if I want to upend a list ex-cons X ish
to a less twice while I do I do I first a band axis2 wise
and then columns action on top super obvious
nigga so much and see a
in part two