Call Stack Walkthrough

[00:00:00]
>> Bianca: And the way I like to teach recursion is through something called the Call Stack Game. And here are the rules of the Call Stack Game. So the first thing is whenever a function is called, you push it onto the stack, then you execute the function body. The function body is like the thing that lives between these two parentheses, an ES5, an ES6, then it gets a little crazy when people don't have the parentheses anymore and then sometimes it's,

[00:00:27]
>> Bianca: No these aren't parentheses, I'm sorry. The brackets, and then sometimes it's parentheses, craziness. But anyway you know what I mean when I say function body. It's this part. And then you execute the function body until another function is called, for example, this is a function being called inside of a function body.

[00:00:47]
If that happens, then you wanna pause the current execution wherever you are, and go back to step one. And you push that function onto the call stack, and you execute the new function body. And then you do that until another function, then you keep repeating it, or until you hit a return statement.

[00:01:05]
If a return statement is hit, you're going to pop the current function off the stack and you will resume executing where you left off if you left off somewhere else. So that's the call stack game. We're going to do it in action, because maybe it's not as
>> Bianca: So here we have, I can put our rules too.

[00:01:29]
I'll put our rules for us so that we have a reference. So we have our reference on the left. And then on the right, we're gonna have our stack. Okay, here's our function so as we are executing this, are we hitting any of the rules for the call stack game?

[00:02:03]
>> Bianca: We're actually not because we never get to a function execution. Se we have to call this function first. So when we call this function we push the function. Whoops. We push the function on to the call stack which I wanna put over here. Here, let me make this JavaScript for you.

[00:02:25]
Is this big enough? Okay. So we pushed on to the call stack and then we execute the function body until we hit another function and then we keep doing it. So and then we're gonna keep track of where we left off, I like to use these squigglies, and then we keep doing it.

[00:02:48]
And then we call it here, gonna put my squigglies.
>> Bianca: That is not a squiggly. Put my squigglies and we're gonna keep doing that. And our Call Stack Game, the reason that we play this game is this how your code executes. This is how it's actually executing in the order in which it's executing.

[00:03:08]
You might see that we're in an infinite loop here so we keep calling and calling and calling. We're not returning. So this is going to go forever. And it's never even getting to any of these second calls. So we're kind of stuck in this first frame here, and it's never gonna make it down here.

[00:03:26]
And so that's really important, lesson one of recursion and just looping in general, is you have to return somewhere. So let's return.
>> Speaker 2: [INAUDIBLE] an infinite loop then, and browser will just say I'm out of memory.
>> Bianca: Yeah, yeah, so when you hear the stack overflow, here's our stack.

[00:03:45]
If we keep going it will run out of memory and it overflows and it crashes. That's a stack overflow. The next thing we might do to make this better. We need to throw a return somewhere. Why not? We'll just return here. Let's see what happens. Let's play the Call Stack Game again.

[00:04:00]
So we call this function. We're going to put it on our stack. Great. And then we return. Call me. So first this is actually an important point. So first we have to call the function. And. Then it's gonna keep calling it forever. So even though we have a return here, it 's still not quite solving our problem.

[00:04:33]
So what we need to do is find a way, for recursion we really want to be able to loop multiple times, meet some base case, and return up. Once we get through our questions here. Once we get to one person, we wanna be able to return up and count all of that together, but let's look at another example.

[00:04:56]
See what this is doing.
>> Bianca: So we're gonna keep doing our Call Stack Game, so we have a tracker here, it's a little bit different. All right, so we need to call it again. And then we're gonna pop that function body here.
>> Bianca: Let's put our global scope to keep track.

[00:05:23]
So we're gonna increment this. This is now one. Is tracker three, equal to three? No, so we're not there. We're gonna keep calling. So we're gonna call, so we hit a function location. We are going to,
>> Bianca: And I'm gonna mark this because this is kind of like a global scope.

[00:05:44]
This is our call stack. Okay. So then, we're going to increment tracker again. Now it's two. This doesn't help us, gonna go call it again. Increment tracker, it is now three. We're gonna hit this conditional, and we're gonna return this value loops. So again, we hit the return statement.

[00:06:14]
What do we do? We have to pop this off the stack. When we need to continue where we left off, which was here. I should have put this. So, this function invocation returns loops.
>> Bianca: However, This function has an implicit return. When we reach the end of the body, the function has an implicit return.

[00:06:43]
It's going to return undefined. So that's an important thing to note is that now this is going to return undefined. So if we had wanted loops to be pushed back through the call stack.
>> Bianca: How might we do that?
>> Bianca: Let's go back to how we had it.

[00:07:16]
>> Bianca: Okay, so we return loops. Here. So this one was loops, which is probably what you wanna do, right? You wanna keep your data. Now let me pop this off. So what might we wanna do so that we don't lose, we don't jump to an implicit return? What's the other option?

[00:07:39]
Implicit opposite is?
>> Speaker 2: Explicit.
>> Bianca: Explict. So we're gonna explicitly return some value. What is that value? The value that this function return which is loops. So how we do that is we just stick a return in there. So now we just assume that all of these are the same.

[00:08:00]
So now when this returns loops, when this function returns loops, this function now also returns loops so we can pop it off. And this is gonna be returning loops. And then we pop it off which means down here this will also return loops. So that's the way that you kind of trace the data from some base case and get it out of each recursive call.

[00:08:35]
Do you want me to go through it again or do you guys feel solid? So, can I see thumbs on how we got loops out?
>> Speaker 3: Doesn't it run forever, though? Am I missing?
>> Bianca: It doesn't run forever, because we have a return statement. Once you hit a return statement it's gonna exit the function.

[00:08:56]
So, we hit this return here. Once this conditional is met this is what we would call in recursion our base case which is where the very bottom of where we want to recurse to, and this isn't doing anything very important, this is just saying just recurse three times and then return loops.

[00:09:20]
This is what this is doing. It's not doing anything special and so you can imagine that you can figure out. And this is how we reach our base case right? So we're incrementing tracker each time we loop, we're getting closer to our base case. If we didn't do that and we never got tracker to equal three, then we would also enter into an infinite loop as well.

[00:09:42]
Have a question?
>> Speaker 4: Yeah, so if tracker reaches 3, we hit the return statement and we go back up pop stuff up the stack. Then if callMe gets called again and tracker hasn't been reset do we just then have an infinite loop and go forever, because it's never gonna be equal the 3 again if every time we go through it's gonna increment again.

[00:10:04]
>> Bianca: Mm-hm, how can we fix that?
>> Speaker 4: We could do it greater than or equal to 3.
>> Bianca: Yeah, we could do that. Or you can just reset it here.
>> Bianca: 0
>> Bianca: So then next time we'll just reset it. However, this is dangerous. This is why we don't do globals like this because you can create a race-condition.

[00:10:35]
Weird things can happen. So just be careful. In most scenarios, you're not gonna be relying on a global for any kind of loop like this. Mm-hm.
>> Speaker 5: Can you do an example where you actually use the time in the recursion, how does it work?
>> Bianca: Yeah, sure.
>> Bianca: Let's do one of these guys, this is fun.

[00:11:09]
>> Bianca: Okay.
>> Bianca: So we're gonna play our game.
>> Bianca: We're going to call our function. We're gonna put it on to the call stack. What is arg? Arg in this case is any time.
>> Bianca: We're gonna increment our tracker. This is now one. This is false.
>> Bianca: What is?

[00:11:35]
Or actually arg is this case, I'm sorry, is undefined.
>> Bianca: Right, because we're not passing anything right here. So we start as undefined. However, the second time we call it, we give it a value. But let's put our little line here.
>> Bianca: So arg, at this point is, let me put in the next line so you can see it, is anytime.

[00:12:04]
We're gonna increment tracker.
>> Bianca: Still not three. Calling it again, we're going to push it on the stack. Again this is still anytime. Increment tracker is now three, which is our base case. We're gonna reset tracker
>> Bianca: And then we're going to return loops + arg, which is gonna be loops anytime.

[00:12:40]
Hold on, let's get to the, so this is where we were. So let's just pop off properly so that we can see how it loops through. I am putting this here from where we kinda left off. So, we hit this return. Actually we didn't do this. We never get to here, cuz we get inside of here, we return.

[00:13:05]
This is what we're returning. So let's pop this off. This function is going to be evaluated to what this returns which, again, let's put this actual value.
>> Bianca: And then, so this evaluates to that so it's essentially saying do that. And we're gonna return again, so we pop this off.

[00:13:36]
>> Bianca: This returns this value. We pop this off. This function is just gonna return,
>> Bianca: Down here. So that's how you can pass an argument through. You can also start with passing one here as well. But we'll go through more examples. How do you guys feel about the Call Stack Game?

[00:14:07]
>> Bianca: Working for you?
>> Speaker 3: Can you just repeat one more time why we went from call me anytime to return call me anytime?
>> Bianca: Sure. The reason we did that was because in this case the very first time we returned, we returned a value. However, once we evaluated the next function on the stack, it didn't return anything.

[00:14:31]
It just was calling a function and so what happens automatically when you don't have an explicit return statement in the function, it just returns undefined. So the subsequent returns up the stack we're just returning undefined. And so we were losing our value that we returned initially. So that's why whatever this returns, we want to also return it.

[00:14:55]
Otherwise it will just return undefined implicitly.
>> Speaker 4: So essentially the purpose of this recursion is to continue doing the loops until a certain condition is met and then break out of it and return that value.
>> Bianca: Yep, which is what every loop does right? So recursion is just a super cool way of looping.

[00:15:15]
Hate to break it to you, that's all it really is. Makes you feel cooler.