Looping with Recursion

[00:00:00]
>> Bianca: The typical recipe for recursion is to identify your base case which is, when do you want your loop to stop? So if you're doing a for loop and you say, four of r i equals i less than a rate at length. Your base case is i is less than a rate at length, when do you want that loop to stop?

[00:00:16]
Or you want it to stop when it's greater than, but you know what I mean, that's the condition of the loop and that's your base case. What is your recursive case? So the recursive case is the work that you wanna do, right? So we're not just looping for no reason, there's some work that we need to do for each loop.

[00:00:35]
So maybe we're adding some numbers, maybe we're doing some other sort of operations. So we need to identify that recursive case, and we need to make sure that each time we call our recursion, we're getting closer to our base case. Because otherwise, we never meet our base case, we're gonna loop forever.

[00:00:52]
And we get into this infinite loop and it crashes your browser. Nice thing about repl.it is that it stops the infinite loop so it doesn't actually crash your browser. And it will warn you that you have an infinite loop, which is super nice. Cuz otherwise if you're playing around with this stuff, you'll have to close and open your browser when you mess up.

[00:01:11]
And you always mess up the first time. So the other thing is you need to make sure that you're returning where it's appropriate, cuz you can lose your data, as we mentioned. And again, write a procedure that's gonna bring your input closer to your base case. And so this sounds all fine and dandy, but applying this to a real problem can be a little bit tricky.

[00:01:39]
>> Bianca: All right, so let's look at our fancy loop. Or this is just, yeah, this is our recursive loop. So let's check it out and play our game.
>> Bianca: So like I mentioned, recursion is just fancy loops, and most of the time I would suggest just using a loop.

[00:02:05]
However, as you grow with your algorithms and data structures, there's gonna be times when it's actually way harder to write a solution iteratively over recursively. So it's good to get familiar with the simple cases until you get to a point where, okay, then it's really needed, and we're applying it to something a little more advanced.

[00:02:28]
Okay, so we're gonna pass 3. All right, so we're gonna push this on to our call stack, emulating how our JavaScript actually would be executing, and we're creating our scope here. Every time we push something onto a call stack, we're creating an execution context. All the variables that live inside of that function have their own little world and you can't, like this when we call again, can't really interact.

[00:02:57]
This parent can't interact with the child, but the child can interact with the parent in terms of scope. You can reach up, but you can't reach in. So I'm getting ahead of myself. So we're passing 3 in as 3. So this will just console.log that n equals 3 for your reference.

[00:03:20]
So if our n is less than or equal to 1, our loop is complete, right? This is similar to where you say i is greater than area.length. So is it less than 1? No, okay, fine, we're gonna have to call it again and we're gonna decrement n. This is the important part.

[00:03:41]
We need to decrement, otherwise that infinite loop case is what's gonna happen. So now n is 2, it's not less than 1, okay, let's do it again. And then usually I like to, in these examples it doesn't really matter where we leave off. But sometimes there'll be more work that needs to be done after we call a recursion, so it's good to keep track of where you were.

[00:04:06]
When you have to go back and do more work. Okay, so now this is 1, is it 1, great. Now we're gonna return complete. Again, we never get down here cuz we hit this case, and once we see that return, that means we're gonna exit this function, pop it off the stack.

[00:04:25]
Whatever this returns is what this is returning, so this is gonna return complete.
>> Bianca: And let's pop it off the stack. So since there's a return statement, we will return again. The value complete, pop this guy off the stack.
>> Bianca: And then pop this guy off the stack.

[00:04:54]
>> Bianca: So that's our loop with recursion. And through this workshop in this particular section, I want you to get really familiar with translating loops into recursion and recursion into loops. That's the goal, because loops are easier to reason about, recursion is just a loop. How we do put those two things together?

[00:05:13]
That's what we're doing.