Path Finding: Recursive Case

[00:00:00]
>> All right, so, let's start the recursive case. Now remember, the recursive case is completely separated from the base case, you don't even need to think about what happens in the base case at this point. Now remember, I also said there's three steps to recursion inside the recurse case, right?

[00:00:15]
There is the pre, there is the recurse, and there is the post, right? So, the reason why pre and post become super important is because we're pathing. We need to go a direction and keep track of our path. And that also means our post is really important, cuz remember, when you're recursing, you don't know what happens below your point, right?

[00:00:41]
So let's just say we start, I'm just going to draw this more simple, let's just say we get to here, right? We're three steps in, well, we started here and we started recursing in CSS order, right? That means we went to here. So before we went, we actually pushed into the array, hey, we're at start, then we started recursing.

[00:01:02]
So we first try going up, then at up, we can recurse. So we can say, okay, I'm just gonna call this, we'll just call that X naught, so then we get to X naught. And we say, hey, let's do CSS ordering. We go up, we hit a wall, we can't go there, we go here, and we go, okay, we can go here, we'll call this x1, and then we can push in x1.

[00:01:21]
And you can see that we build this case in recursion. And as we unwind our stack, we'll actually pop things back off, that's why a pre and a post are so important during recursion. We do have a question.
>> What is CSS ordering?
>> [LAUGH] CSS ordering, it's a joke.

[00:01:39]
[LAUGH] When you specify margin in CSS, margin is top, right, bottom, left, it's a joke, [LAUGH] maybe it's not that good. This reminded me of what my wife always tells me that I'm not funny. This hurts a little bit, but yeah, that's how I remember things, so I just pick an ordering.

[00:01:59]
And so often, I'll just pick CSS ordering as whenever I'm drawing something to do it in the order in which, right? Isn't that CSS? Doesn't CSS start at top? Top, right, bottom, left.
>> Yeah, it does.
>> Okay.
>> Chad says, it was a good joke, so.
>> Thanks, see, that's why you guys get me, we get each other.

[00:02:15]
All right, so there we go. So we're gonna take advantage of these things, and we're gonna build the path, right? And one thing I didn't explain in here is when we tried to check the wall, notice that we did our base case and left but we did not pop X0 off the array yet.

[00:02:31]
Cuz we have to check all of our recursion steps, and then we can pop it off. So if we meet a dead end, we'll get to the dead end, check all of our directions, realize we can't go, then pop that last tile off our stack. Then check all of our directions, we've finished checking our directions, then pop it off, then pop it off, then pop it off, so we're building our path as we walk.

[00:02:53]
All right, so let's start with the precondition. Precondition, we don't have a path, do we? So again, let's just keep on adding, what's wrong with that? So we're gonna have a path, and let's have a point array. So every time we successfully visit a spot, we will add that in the precondition and remove it in the post condition.

[00:03:12]
That makes sense? Because we don't know how much further we're gonna recurse if we're gonna meet a dead end, what's gonna happen, just something's gonna happen. But at this point, we add, we're recursing, if we come back out, we pop, so we kinda maintain this nice state. So one beautiful part about recursion and a stack is that it kinda maintain shape, right?

[00:03:37]
In sort of weird sense, it can maintain shape. So we can go like this, path.push(curr), right? Awesome, and then for our ending our post, we can just pop, right? So there we go, we push into our position, we recurse, we pop, awesome. We're pretty much done, we've just built the path, now all we need to do was recurse.

[00:04:03]
And so I'm gonna give you guys a sweet leetcode tip, it's something that I've learned from a friend. I only know by his Internet Monica, actually, technically known by his non Internet Monica, but it'll be Scooby-Doo. You can go like this, dir =, and then you can put in four directions.

[00:04:18]
And so I could go say, -1, 0, 1, whoopsies, and take those, and we can go that, that, where is it? Where are you? And 0, there we go. Those are our four directions we want to go, right? We want to go, this is left, right, down, up.

[00:04:42]
I just selected the random ordering, that's what we got. So those are the differential directions, right? They're what we have to change to get to go that way. All right, so we can use that, and then we can go down to our recursive step. I'm gonna have to use a for loop, cuz we can't use sweet sweet for each is plus the create stuff.

[00:05:05]
All right, it bothers me, i is to be less than dir.length, ++ i. And now, all we need to do is recurse our four directions we want to go. So, let's call ourself again walk, with the maze, with the wall. And then right here, we need to have our new current.

[00:05:23]
What is our new current? Well, our new current needs to look like this, [x, y] = dir[i], right? So that's gonna be our new current, and so let's go curr.x + x, curr.y + y, right? We just did our differential, we're gonna go left, we're gonna go right, we're gonna go up, we're gonna go down.

[00:05:46]
It's a pretty simple, pretty nice little thing. A lot of times, you'll see people like hand put in all the different calculations, all that. It can get pretty cumbersome, for me, this makes it a lot easier to understand, and I only have to specify it once right up here, which makes it pretty easy.

[00:06:00]
Then you don't get all these pluses and minus ones all over the place, and then you're like, which one did I do? Makes it a lot easier. All right, what do we have left? We have our end point, we have our seen, and we have our path. Awesome, now remember I did return a true if we found the end.

[00:06:18]
So if we do get a true and we found the end, we need to do something here as well, right? We can't just keep recursing once we found the end. So if walk is successful, we need to return true, right? This is kind of a weird base case shift, where you can't really do it, you have to stop your recursing, we have to stop it at this point, right?

[00:06:44]
There we go, we've done it, it's great, right? Does this kind of makes sense? Do you see how we're doing each check? We're checking in all four cardinal directions, and then we have a nice, simple base case, is right here. The only thing, there's one bug in there right now.

[00:06:59]
Does anyone notice what the bug is? You should know, if someone actually noticed what the bug is, I would be floored, it's part of the precondition. So notice that we push in things we have seen right here. If we get a true when it's returned, it returns early, we get a true, which means the moment we get a true, we also stop recursing.

[00:07:20]
All recurses stop recursing, it goes right back out. Cuz it says, hey, at this point, our path array is completed, we're done. But what's the problem? Our ending tile does not get pushed in, so path.push. And got to push in the very last one cuz it doesn't get added.

[00:07:37]
So there we go, we should have a completed case. Long as I've done everything correctly, we should be able to go here and actually do it and see it. And we didn't get it because, of course, we forgot just a very, very, very simple thing, which is I didn't do this down here, right?

[00:07:54]
We didn't actually fill in the function itself, I would still consider this a first try, I feel like this is a first try still, okay? I consider that a compiler, so const seen needs to be a boolean to the array. And then we also need our path, which is gonna be our Point array, right?

[00:08:14]
We also need to kinda fill in our boolean array. So let's go for let i = 0; i has to be less than maze.length, seen.push(new Array(maze[0] length, no, fill(false), right? There we go. So we've now created our potential pathing array, and then we also have our seen matrix, and they're all falses to begin with.

[00:08:39]
We just wanna make sure they're false. Technically, this is JavaScript, we didn't have to do this, right? If you would have access something outside of your bounds, it would have been undefined. And therefore, it's technically false, and we could have just turned them to true as we saw them.

[00:08:54]
And that would have worked. So then we walk. And walk takes in maze, wall, start is our current position we wanna start at, we wanna get to the end. And then if I'm not mistaken, let's see, if I'm not mistaken, pressing all the wrong buttons, we've to have seen and path, and then we can just return out path.

[00:09:18]
So if we've successfully done this, we'll return out a completed path, if it gets to the end, then we won't. But I do have one more bug I just thought of in my head that I forgot to do. As part of the pre, we also need to go, seen[curr.y], I mean, this would have just exploded our stack, [curr.x] = true.

[00:09:31]
I forgot that one point. There we go. Luckily, we caught that before we've tried it. Or else, if we didn't catch it before we tried, we wouldn't have been able to get a first try, which would have been very, very sad. All right, so we rerun this one more time.

[00:09:45]
And now, we have another one right here on line eight, classic, Oopsy Daisy's saying, there's a boolean, and apparently, we forgot a case to return. Did I forget? Yes, if we recurse and we reached the end, and we did not find end in our current position, then yeah, it's false, I'd still consider that a compiler, I feel like we got a compiler there.

[00:10:09]
First try, of course, absolutely. So there we go. We got it, fantastic. For those that are wondering what we just solved, if we go to maze_solver in the test, here's the maze that we just got done solving. And this top point right here is our start. I believe this is our end, and we build that exact path all the way through.

[00:10:31]
So pretty fantastic, right? We were able to do that, and then this is kind of the out we expect. So we were able to solve that. Hopefully, this makes recursion either more clear or you feel more confused than ever. But I'm hoping that it makes it more clear in the sense that always think about your base case.

[00:10:49]
Honestly, is gonna save you so much headache if you can do a clear and defined reason why you should stop recursing. Often, what I'll see is in the recursive step, people will try to test for it, like is the thing I'm about to go to null. No, don't do it there, but at the base case, it makes it a lot easier.

[00:11:06]
Is the thing off the grid? No, don't do it there, put it in the base case. Move everything you can into the base case, your complexity will go massively down, and it's a lot easier to solve. So hopefully that all makes sense. A common question you get is, when do I use recursion, right?

[00:11:21]
Cuz a lot of these things seem like we can do a for loop. Obviously, the last thing we just got done doing is clear, you can't do a for loop with. Well, I mean, you can if you use the stack and you kept track of your own state and all that, but you wouldn't do that, that'd be crazy talk.

[00:11:34]
So that's my general rule of thumb, is when I can't concretely use a for loop, meaning there is no defined end, especially if there's a branching factor. You can imagine that the maze that we were just doing had a branching factor, right? You could do four possible directions at any one point on the grid, therefore, the branching factor is four.

[00:11:56]
So how do you do a for loop for that? You can't just write a for loop simply for that. And so that's my general rule of thumb, is how do I avoid using recursion? If there is a terminus, something I can see, it's a simple for loop can do it, always use a for loop, else, recursion.

[00:12:10]
If you write your recursion correctly, it becomes aggressively simple, you write it with base cases within your recurse step, it becomes aggressively complicated.