OK, now let's take a look at function recursion, so what would happen if you had a function and that
function called itself?
That's what's called function recursion.
So let's take a look at a quick example.
So we have a function here called Go Forever, and all it does is called Go Forever.
And then somewhere else, you have to kick it off, the function can't kick itself off, so somewhere
else you can't go forever, it starts to go forever function, and then it just runs forever.
So if you really do this, of course, you have to find a way to make it end.
So let's take a look at some examples of how this works.
OK, so let's try something really simple, so we'll create a function and start calling and go forever.
We'll call it go for a while
and let's take a parameter or just call data.
And then here we're going to subtract one from value.
And I'm going to say, if value equals zero return, if you don't return, we're going to go for a while
and send in the value.
So this is going to run a certain number of times depending on what the initial value is.
So let's take a look at that some years ago for a while and what Sen. Ted.
And then here, before we start decorating it, blog out what the value is.
So let's go ahead and run this.
I'll just click one whole world in here puts ten, nine, eight, seven, six, five, four, three,
two, one.
And then it doesn't turn out zero because it it ends at that point.
So what's going on here?
So let's go ahead and say to break in our hello before we even call the first time and let's run it.
So we're here, we're ready to run.
We're going to pass in the value of ten, so you step forward to step in and our values ten, so we
vote that out.
So now that's in the log.
Right there.
We're going to subtract one from Dalu.
And now you can see over here and the locals that the value is nine.
And then we did check.
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
right back here again.
Here's the value and it's nine and we're going to go.
Well, get out.
Strike one, it's not zero.
Now, here's a part of the debugger that you haven't seen before.
You I haven't shown you anyway, and it's called the call stack.
And what's going on here in the call stack is we started at hello.
And then we went to go for a while and now we go for a while again.
And originally we started at the unclick.
That's in the HTML.
So it's just saying what's called what.
So Unclick called hello.
Hello Kulka for a while, go for a while called.
Go for a while again.
And if I click on these you can see that the value at each one is shown.
So the value at this go for a while is nine.
At this one it's eight.
So let's go, keep stepping in for a little bit as another go for a while.
As another go for a while.
And so on.
So it's going to keep running until the point where value becomes zero.
She was right about you not to.
OK, now zero is going to the return.
So if I click on these go for a wild, little bigger.
This one that I use zero, this one is one, and if I keep going back, it's going to keep going back
to this original that is.
Now what's going to happen here is we're returning and each one of these off the call stack pops off.
It's a stack return.
So you could see that it's showing us the value of three, if you look at the COL stack here, it's
going to keep getting shorter.
Until we get to the original one, which was the first one that we called, and then we go back to hello.
OK, let's do something practical with this.
This back and what we do is we'll get rid of this.
Back to almost where we were and there's a lot of algorithms that use recursion in a really simple one
is called a binary search.
And with a binary search, it says you have a list of say, let's list equals an array and a binary
search.
The array has to be already sorted in order.
So I'm going to put some numbers in here to kind of six comma nine comma 12 comma 17 comma.
Twenty two.
Twenty eight comma.
Thirty three comma.
Thirty nine comma.
Forty one comma forty five.
Forty eight.
And trying to get a bunch of numbers in here.
So bear with me for a minute.
OK, so we've got a list that looks like there's maybe 15 numbers in there or something.
And what we want to do is find the number in the list and just essentially say we found it all the time
in computer programs.
You're searching for something and bringing it back when you find it.
And often it'll be an object.
So in this case, it's just a number.
So let's go ahead and do this.
So what how this works is we're going to create a function and we'll just call search and we're going
to pass in a list.
And then in the list, what we're going to do is look at the very center item and we're going to see
if it is the very center item.
So we're going to say let middle equals list and then we're going to to go that length divided by two.
And we wanted to have a integer number.
We don't want to have, like, you know, three point five.
So what we want to do is use a math function called math math DOT four, which is going to say take
it down to the nearest whole number below that to the floor.
I think there's a ceiling function, too, that will take it up or around function and those sorts of
things.
So if the list is 15 in length, it's going to be turned seven.
So now we have a middle.
We're just going to say, hey, is is the middle is that is that what we're looking for?
If it is, we're going to return it.
So we say if
list.
So middle
equals and we have to pass them over looking for a search.
No says no.
We're looking for.
So if it is the search number, we're going to return the search now.
And before we do this, before we even try this, what we should do is say, hey, if the list is now
empty, just returned, I don't know.
We'll return then another number, so if left, that wing equals zero return.
Not a no.
All right, so it's not in the middle, so since this is a sorted list, it's got to be there to the
left and the left to the right.
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
searching for 66.
It's got to be on that side list.
So we're going to do is RECURSE and we're going to call search again and pass it.
The other portion of the list, the portion of the list where we know the number is the word Oraibi.
So then we're going to say if
search search known is less than list some middle.
Then we're going to call search with search now in that part of the list.
So if a search search numb and then we're going to use the slice to get the list that we want to lift
that slice.
Let's take a look at the documentation for Slice.
So here's the documentation for Slice, it returns a portion of an array into the new array object,
so you say the start in the end, we know the starts can be zero because that's the beginning of the
right, the end.
It's one before the end.
So we want to the middle position to be the end.
So we'll say zero microsurgeon here, zero comma middle.
And that's going to it's not going to include middle.
So you can see here in the documentation, the substrate includes characters up to, but not including
the character indicated by the end.
Thanks for doing a string, but we're not.
So we're going to call that.
And we want to do is we don't want to just call.
We want to return it, because when we find this, we're returning it.
So the returning man or and I don't know, I missed the return here or are we going to return the search
now?
So whenever we find it, it's going to get returned to we want to return it here.
OK, otherwise, health return, search, search, no less, that flies and we want to go middle plus
one
and we don't have to specify the second parameter, it's just going to go to that.
All right, and then up here, we just need to search for it so we can say
consed search equals prompt.
What number are you looking for?
So we search for it and I say run the search and store the return value of.
Found value equals search a search value in the list and then at the end will just say cancel that log.
Found some value, and if we end up with an end, we didn't find it.
All right, let's kind of run this.
And the Tea Party guys, let's get rid of that break, because that's where we want it anyway.
All right.
So we'll say run hello, world will search for 20 to find some doing something a little bit wrong here,
we're going to have to figure that out.
Oh, I know what the problem is already.
We're getting a string, so we may as well just fix that.
We need a number.
We're getting a straight.
So we're going to just go in here and say, no, that pass and
search.
So let's hit that fixes the problem.
Run Type 22 again.
And breaking, I don't really want.
And we found it, so I searched for something else.
33.
Thirty three.
But search for something else, something that we know doesn't exist.
And that returns to Dan.
All right, let's take a just a couple minutes and kind of step through this to get an idea what he's
doing.
So I'm going to back in Chrome.
I'm going to set a break.
And it will sit right here.
Here, here.
Well, run and search for nine.
OK, so we got our found value.
I'm sorry, we have a search value, it's a string.
That's why I do this part, to make it into a number.
So step in and we can see over here.
Let's close the call stack.
We have our list, we have our search now, Middle's undefiled.
All right, so let's get a view from middle C, middle is nine and if not the number nine, position
nine.
So whatever the ninth index is.
So we'll say if there's nothing left in the list.
If the middle is the search, none, so listen middle.
So with that, nine is forty one.
So it's not going to be the search.
Not getting that lucky yet, so the search no less than this.
It is so we want to do is take a slice of that array and pass it back in through recursion.
And now you can see our list got a lot shorter.
It's two, three.
Thirty nine.
So we'll step again is our middle is now for these are less separate?
No, it's going to be 17, so it's going to go on.
And is it less it's less so we're going again now we have two, six, nine, 12.
So our middle.
Is going to be two.
So in our list.
Zero one two is the nine, so it finds it.
And it's going to return that so everything just returns out and we end up with our found value of not.
So that's an introduction to recursion, along with a standard algorithm to do a binary search.