Recursion Q&A

[00:00:00]
>> Any questions from chat? Anyone have any questions? Now's your time. Great time to ask questions.
>> If on the maze front, if we had the scene we're going somewhere and then we have to go back. Does it get mad that it's going back on its own?
>> So that is a good question.

[00:00:18]
So in a sense, yes. And in a sense, no. So the question of course was we walk a certain direction the graph, but then at some point we can't keep on walking, right? So we have to undo, but then we also programmed in that you can't go back on your own self, right?

[00:00:35]
Well, let me kind of draw this a little bit more. So when we're doing the maze solving, let's just say we have these two things, right? We have x0 and x1. So we're at x0, and everything's great. So our path is to x0 right now. Our scene is now true, this one's false, right?

[00:00:57]
That's kind of the state of the world we're at right now. Well, then we check up, we can't go up, so we don't go up. It returns false right away. Then we go over, we can go over and we start recursing. So we put in x1, right? That was a terrible x, do you see how sad that x was?

[00:01:13]
Here we go. X1, perfect. We put in x1, and then we start recursing. And this becomes true, awesome. We go here, it's a wall. We go here, it's a wall. We go here, it's a wall. Then we try to go here. What happens? Scenery, right? The scenery, you're true.

[00:01:35]
We can't go there. So then what happens? Look at the code. We get done rehearsing. We pop the thing off the stack, and then we return back the function. The return address then gets popped back to the previous one that was called, which we were called from x0.

[00:01:57]
So we pop this off the stack and then the function returns to here and we check downwards. Cuz remember, going top, over, recursed in top, over, down, this way, return, down, over. And so it just repeats the same algorithm over and over again. Hopefully my arm gestures just helped you see that.

[00:02:16]
I know it was a weird, is this something between bring it on and algorithms there for a second, it was beautiful. That was like a really weird 90s reference that just came to my brain.
>> I think that this case, how did you end up in the top word, the-

[00:02:35]
>> How'd you end up in the top?
>> No, the output, the test case. If we look at the test for this, yeah. So the start is x is equal to 10 and y is equal to 0, and x is equal to 1, y is equal to pi, right?

[00:02:50]
>> Yeah.
>> So how did we end up with a dot product? Still, it'll be confusing for me.
>> How do we end up in the top function?
>> No, the output?
>> How did we get this?
>> Yes.
>> All right, so let's go. Let's go back to this the simple case cuz I think the simple case really helps kind of see it.

[00:03:08]
Is that, I'll redraw it and we'll just only talk about parving, right? And let's say, these are walls all right here, right? And then we can say, let's say our exit is right here, right? So let's go, x0, x1, x2. And our traversing algorithm goes CSS ordering. Whoo, right?

[00:03:33]
We'll go to xx order. So we land right here. All right, let's just say we start right here. This is our mace, this is as big as our maze is, right? It's that simple to the point where exits right there are starts right here, our exits right below us.

[00:03:47]
So it's only one away. So what's gonna happen is we're first gonna try to go, we're first gonna push x0 into our path array. Correct, we make it through a base cases. We set our scene to true, and now we push it into our array. And now recurse we try to go up.

[00:04:02]
That immediately returns, can't do it. We go over. Here, let me actually draw with a different color, this might actually be a little bit more useful. Let's see. Let's go with not yellow, yellow would be very hard to see, is there a good blue? What about nice blue?

[00:04:19]
I like a nice blue. Let's go, kind of bright blue, all right? . So we try to go up, we can't go anywhere, right? So then we try to go into the next one. Remember, now we're going right. We can go here, none of the base cases fail.

[00:04:36]
So what do we do? We now set in, let's go like this, go back to white for this one. We now set in. Sorry, I'm gonna try to get more specific with this one, x1, right? None of our base cases fail, we're now able to set it in.

[00:04:53]
And so we now repeat our algorithm, right? We now go up, can't go there. We now go over. We can go there, so we do it again. At this point, our scene array now becomes all trues. And now we put in x2. x2 of course attempts to go up.

[00:05:08]
It cannot go there. Tends to go this way, it cannot go there. Tends to go this way, it cannot go there, then it attempts to go this way. And it fails because of that true, right? So then we're done. Now, this whole function returns. Now returns a false.

[00:05:26]
But before it returns, it pops from the stack so then this one does the same thing. Checks down now. Checks over scene array fails, pops from the stack, returns. This one now checks down, finds the end, pushes the end into the stack and then returns completely. And so now we have now built this array as we walked, push, push, push, pop up, push?

[00:05:50]
Would you have one more question?
>> Is there any scenario where the order would make any performance difference such as going top right, bottom left?
>> There is no difference in the general case, right? If we could inspect or look at, then yeah, in some sense, we could automatically guess.

[00:06:10]
Cuz right here, if we go down, and then left, then up then right, obviously, it would effectively walk straight to the exit, right? But if we tried up first, it would go up couldn't go, then let's say it went this direction, couldn't go, and eventually get to here, tried to go back, okay?

[00:06:28]
So it tried to go up again couldn't go, this one couldn't go. Then let's say it goes this direction. I repeat the same thing can't go, can't go, can't go, can't go, up down, go down and go over, can't go, ba, ba, ba, ba, ba, ba, all the way till it gets here.

[00:06:42]
And once again to run up into here and then run up over here. It's gonna go explore that whole space. Since you don't know the graph ahead of time, you can't really see it with a direction that would make most sense. So in the general case, absolutely. In this specific case, we know exactly what would get there in the shortest possible path.

[00:06:58]
So you can't cheat the system, in other words. Got that kids, All right, that's really is your chance. Recursion, it's just really fundamental to these next parts, all right?
>> What would be the big 0 time for this then?
>> Well, the big O time, though, this is where things get kind of fun.

[00:07:23]
We can think of this as, let's just think of it in a different kind of sense. All right, we don't have to solve it for the whole thing, let's just solve it for a specific square. So, ooh, I love this blue color, don't you guys? it's beautiful, all right?

[00:07:37]
So we have this square, right, and really it has four possible entrances into the square, correct? So that means we have the potential to come up from this direction, that's one. And if this is something like say it's just a completely open square graph and we check every single time, then we could check it again from this side, from this side, and from this side.

[00:08:02]
So at most, we will check every single square four times, right? So unless if there's a required outer wall, then whatever the perimeter is minus all the inner sides, right? Besides were all that kind of complexity. What you'll see is you'll see at max, 4 checks for every square in the graph.

[00:08:19]
So if we use S as our notation, then it'd be big O(4S), drop that. It's effectively linear, right? For every point, we would just call it big O(N), right? And so that's as slow or fast as you can get. Walls, you only check once, right? You can really, I mean, I guess technically, if there was an island wall, you could get all four checks on it.

[00:08:46]
But if it's some sort of perimeter wall or walls, it's adjacent, that amount of checks go down. And so, there you go. Radical, all right. Let me go back to black on this cuz if I don't, the next time I create something, it'll be very blue. And we'll all go [SOUND].

[00:09:07]
I have a joke about a vampire there. We let it go though.