Data Structures and Algorithms in JavaScript Tracing Recursive Execution

[00:00:00]
>> Bianca Gandolfo: So WTH is this even doing? So let's just start with how the code is executing here. I'm gonna pull up my Sublime for us, we'll copy it in. So remember how I was like, hey, we're gonna need to know about this stack trace thing, remember that? Just a few hours ago, I mentioned that.

[00:00:20] This is when this comes in. What we're gonna do is we're going to execute this code and figure out what it's doing. I might have given you a hint before about specifically what this is doing. But let's just check it out. So the big secret here is this code is actually doing zero things.

[00:00:38] Does anyone know why?
>> Bianca Gandolfo: Because we haven't called it yet.
>> Speaker 2: [LAUGH]
>> Bianca Gandolfo: Come on, all right, so here we go. We just called it for the first time, and this is my line saying, this is what's happening underneath. Get it, it's underneath. And this is our code that's gonna be executing.

[00:01:04] Right, we'll have it as a reference. Are you following here? All right, so we just invoked a function called callMe. So we're gonna put this function definition onto our stack. We jump into the body of our function. My gosh, another one. And let's just number this just to keep track.

[00:01:25] Yeah, and so this is 1, all right, I'm sorry, this is 2. And this will be useful later, right? Cuz right now this one's kind of just a funny example, no, what's going on?
>> Bianca Gandolfo: So we have found ourselves in an infinite loop, I can be dramatic and keep doing this forever.

[00:01:49]
>> Bianca Gandolfo: But I think we get the point, right? Now, what this function is doing, it's calling itself, calling itself into an infinite loop. The other thing is, if you have an infinite loop, these things are never gonna happen after. So this callMe has never been invoked. This one that says anytime has never been invoked.

[00:02:08] And in fact, we're just kind of stuck in this forever. And it's definitely gonna crash your browser. So don't run this code, if you don't want that to happen, cool. However, I think I have some on my next slide. Do I, where? All right, so great, we have this infinite loop, take some away just to make some space.

[00:02:36] How do we stop it from looping? So now we have this thing, it's looping forever. It's not useful to us. What would be one way to stop it from looping?
>> Speaker 2: Give it a break condition.
>> Bianca Gandolfo: Yeah, break or return.
>> Speaker 2: Return.
>> Bianca Gandolfo: Yeah, exactly, it says no more infinite loops, awesome.

[00:03:01] Now what is our function doing? Nothing, it's just immediately returning. Well, that's not exactly what we want to do either. There's no looping happening, right? For recursion, we want some looping action, most of the time. This is just a regular function that's just returning. It's no longer recursive, that's a problem.

[00:03:22] Have a question?
>> Speaker 3: Question from the channel, what is return?
>> Bianca Gandolfo: Ooh, what is return? Return, that is a really good question. How do I explain return? Return is, there's a keyword in JavaScript that will break out of the function. It's gonna return from the function whatever the value that is to the right.

[00:03:41] So it could be a string, you could return numbers if you want. And it's how you can send data that perhaps is calculated inside of the function outside to maybe another function. Or, and maybe, yeah probably, another function is where it's gonna go, so that's return. The thing to know about return is it's gonna break out of the function.

[00:04:05] So anything that happens, after a return statement, won't run. So since we have a return here, this callMe('anytime') business never happens, which is why this isn't recursive anymore because we have this return. That kind of ruins everything. It fixes one thing, right? But it ruins everything else.
>> Bianca Gandolfo: So what should we do?

[00:04:38] I'm stumped.
>> Bianca Gandolfo: We want it to be recursive.
>> Speaker 3: Suggestion, base case, if statement.
>> Bianca Gandolfo: Yeah, yeah, absolutely, thank you Sarah K. We wanna have some conditional that will allow us to be recursive without having an unlimited loop, yeah? All right, cool, so what would that might look like?

[00:05:17] Maybe we have a tracker here, does that make sense? Let's see how this works, it's a little bit different.
>> Bianca Gandolfo: All right.
>> Bianca Gandolfo: Oops.
>> Bianca Gandolfo: All right, are we ready? So we call, callMe. We have that body of the function here, great. We increment tracker. What is tracker?

[00:05:53] Tracker is 0. Well, actually well, let's just say it's 1 is fine. And so if tracker is 3, this is gonna be false. We don't Enter here, which means we get to jump into a recursion. callMe, which means that we have to put another function on the stack, so this is gonna be our second one.

[00:06:16] Let's put it in loops, in braces. So this means this is the second function call, just to clarify. And then I'm also gonna put it here, just so we can keep track of how this is working in order. Are we all following? Great, so here's a second one.

[00:06:32] We're gonna increment tracker. Tracker is now 2. So if tracker is 3, no, that is false. We're gonna skip this one, keep going. We're gonna call again, this is gonna be the third one.
>> Bianca Gandolfo: And comment this, now this is 3, true! Now this returns loops, okay? So because we have a return statement it's not gonna continue on.

[00:06:58] We are going to pop,
>> Bianca Gandolfo: This off, cuz we're returning. That's how the pop happens, you have to return. And now since we popped out of this, this is gonna return the string loops. Does that make sense? Cool, and then since this is finished executing,
>> Bianca Gandolfo: Well, pop, this one is now finished executing.

[00:07:26] And we have a pop. Should we see it in action?
>> Bianca Gandolfo: callMe, whoo! [APPLAUSE] But what's missing?
>> Bianca Gandolfo: There was a piece of data that we highlighted.
>> Speaker 2: We didn't send it all the way back up the tree.
>> Bianca Gandolfo: Yeah, so we had return loops. And perhaps, maybe it was useful for us.

[00:07:56] In our specific implementation to return this string, but it got stuck somewhere, yeah? Actually, lets review where it got stuck. So we return here, then when we get to this. We're not actually returning the string.
>> Bianca Gandolfo: It's gonna return undefined, because the function,
>> Bianca Gandolfo: It just automatically returns undefined at the end and so it's gonna keep doing that.

[00:08:32]
>> Bianca Gandolfo: And doing that, so this returns undefined, which means this, and then this also returns undefined as well, which means this one is also gonna return undefined.
>> Bianca Gandolfo: Can I have one question from someone?
>> Speaker 3: Do we need to set the tracker back to 0, though?
>> Bianca Gandolfo: I mean, yeah probably, this tracker lives in an outside world where it's in a global context, just not a best practice, that's just for an example.

[00:09:16] But yeah, ideally you'd want to set it back to 0. And it would be a matter of, where would you do that, right? Probably when you return, right?
>> Bianca Gandolfo: Something like that, but anyways super dangerous because if you have a bunch of callMes happening, it's all gonna be affecting the same tracker.

[00:09:37] So not a good idea.
>> Speaker 3: Can you just do a return callMe anytime?
>> Bianca Gandolfo: Yeah, totally, so if you return callMe anytime, instead what's gonna happen, instead of it returning a new find, it's gonna return whatever this returns. Does that make sense? And what that returns is loops.

[00:09:59] So we pop it off.
>> Bianca Gandolfo: Again, we'll just pretend that we have that. And that's how we get to preserve our return value. This might seem silly now, but this is a really common mistake when we do recursion and we forget to return up or people just memorize it.

[00:10:23] I have to return the function, the last function. So I'm just gonna put a return there without actually understanding why it is so important that you have two return statements in your recursive function. This is why, for this style. There's a few different ways to do it, but specifically for this style, that's why you have it.