Every recursive function needs to have something called a base case or a stop point.
Remember my example at the beginning where I showed you how to recursively check out all the folders
in one of our projects.
We have to tell the program, hey, if the subfolder we're going to no longer has any more folder's
stop, if this stop wasn't there, the function would just keep running.
So recursive functions have two paths.
One is the recursive case that is called a function again and run it, and then the base case that is
stop calling the function, there's nothing more to search.
So how can we add this feature of telling the function, hey, quit it, you're being ridiculous right
now, you need to stop?
Well, we can do something like this.
We can create a counter and we'll say this counter is zero.
And we can add a conditional statement will say that if counter is.
Greater than three.
In that case, just return done.
Otherwise, we'll call Inception, but we also want to increment the counter by one.
So if I click run here, well, I have to call the function first, let's say Inception.
If I call this function right now.
What do you think will happen?
Pause a video.
Think about it, because I'm about to click run and three to one.
I get undefined, is that what you expected?
Just to show you something, if I comment this code out and we just do this inception where we just
keep calling it ception inception and perhaps do a console dialogue here saying hello.
I get maximum call stack size exceeded.
OK, we know by looking at this function, this version of the function, that it's never going to get
to console Dahlborg because as soon as it hits the first line of the function, it's going to go back
and say, oh, I'm calling this, and then it's going to go here is just going to bounce back and forth,
back and forth, never getting to console a lot.
But if we go back to what we have before, well, our function clearly has ended.
It hasn't done stack overflow.
And at one point it's ended because we increment the counter.
So let me console dialogue here, our counter.
And make sure that this works, if I click run, I get zero one, two, three, four.
When it gets to four, counter is greater than three.
So we're returning done.
But why is there no done here?
And this is a great illustration of how recursion works, I'm going to copy this code.
And go back to our browser over here.
Let me refresh this page to make sure that.
We have a clear global variable and I'm going to copy and paste Inception this time around, I'm going
to add the debugger keyboard so that we can debug our code and go step by step through it.
Let's run Inception.
And see what happens.
All right, we're back to our debugger.
We see that we have the call stack here, Inception has just been called by me.
And I also opened up this little tab called Scope for our case, we want to just open up the script
scope.
It shows us what variables we have available to us in this case, we have counter, which is zero.
So I'm going to click step over.
And it's going to say, hey, we have counter is equal to zero, is that greater than three?
No, I'm going to skip over incremented counter and run Inception.
We see that that's happened.
Counter has now been incremented because we've gone through this line and now we go to Inception, we're
going to run the function again and you'll notice that the call stack when I click this is going to
increase.
And we're going to go one more time, Connery's, not one nope, don't return anything yet.
Increment a counter you'll see of goes to two and we're going to run Inception again.
And we keep going once more.
Passing through counter becomes three, adding inception to the stack and then one more time.
Three is not greater than three, so we go one more time calling Inception, adding it to the stack,
we now have these many stacks counters at four and then we step over here.
Counter is now four, which is greater than three, we're finally going to enter the if condition that's
going to return done for us.
Let's see what happens here.
I'm going to click next.
And I click next again.
Look at that, we have a local variable now that has return value done.
We've now returned, done.
And we're no longer going to call Inception.
The call stack is now going to start popping off these functions because it's going to say, oh, we
have a return, key word, I'm going to stop whatever I'm doing at the bottom here and return from this
function.
So this inception function is going to get return done.
But notice what happens next.
Oh, I get return value undefined as we popped off the top item from Inception from the call stack and
if I keep popping things from the call stack.
The return value is undefined, and that's why we get.
Now, why is that?
Well, if we go back to our function, what you just saw was us essentially doing this.
We called Inception once.
Three times.
And then four times.
And within here, when we finally got here, we said, oh, return done so this inception function turns
into done.
And then we go to this function.
Now, the problem with this, and I know this can get confusing, is that once we've returned, once
we've popped off the stack and we're now at this part of inception, but this interception never returns
anything.
When a function doesn't return anything, it just returns undefined.
So we need to keep telling it to return this done and and bubble it up towards the very end.
And this is something that you have to keep in mind with recursion.
There's usually a base case, and you always want to make sure you return so that the value that you
want gets bubbled up all the way to the top.
In our case, all we need to do is say return inception.
This way, this inception knows to return whatever its result was which was done, and this inception
knows to result, to return, whatever this result was, which again is done and so on and so forth
until we get Don back.
Let's run this again.
Or and I have to call the function.
Let's do that again, Inception.
And we're done very, very nice if I go back here.
And go back to the council, I encourage you to try this out this time, adding the return keyword to
Inception and running through the debugger to see what happens.
But what I just showed you is all you need to build recursive functions, you have three rules.
One is to identify the base case.
Two is to identify the recursive case.
So we've identified the base case went to stop the recursive case, that is when Connor is less than
three.
And then finally, our third step is to get closer and closer.
And return when needed, and that usually.
You have to returns.
For the base case and the recursive case, because you want to return something at the end of the function,
so let's comment this out.
We have an idea of how recursion works.
The function simply gets closer and closer and closer to the base case.
And once it gets to the base case, it finally returns and pops functions off the stack.
But that's enough talking for me.
I think it's time for us to do some coding exercises to get really familiar with this topic.
I'll see in the next one by.