Recursion

[00:00:00]
>> Moral of the story, don't use reg X's. All right, I think we should probably continue on from here, reg x's are just graphs underneath the hood and traversing is the characters in which go through that. So, there you go, graphs are literally there. All right, so we're kind of getting into the next part of Recursion.

[00:00:16]
If you don't understand recursion, you can always Google it, though I did find a bug in recursion. Are you ready for this? So if you don't get the joke, if you type in recursion and you hit Enter, Google will say, did you mean recursion? And, my goodness, I can't see my mouse through the 4K, and if you click it, it'll say, do you mean recursion?

[00:00:33]
And you keep on asking it, does it forever. That's the joke, right? But if you misspell it and it says, search results for recursion, it actually doesn't do the recursion joke. Look at that, I've busted Google. Anyways, I thought that was kinda funny. I discovered it two days ago cuz I mistyped recursion.

[00:00:52]
Anyway, so that is the most visual way you can look at recursion. It's something that keeps on calling itself over and over again. In this room, how many of you are familiar with recursion? Okay we got a couple no's, couple yeses. I even had a hand back in the production staff, they said, yeah, I got it.

[00:01:09]
That was awesome. How about tweet chat, all the chats, or hot chats and masters chats, how are they? Pretty good one, if you don't know recursion, two if you know it. Cuz I'm just curious how much, I don't even know what the average understanding of it is.
>> I would say it's split.

[00:01:29]
>> Split, okay, recursion is one of these topics where you literally just it's super hard.
>> Definitely more twos than ones but-
>> Okay.
>> There are quite a few ones.
>> So we're gonna go over it either way even if everyone in here understood it, someone doesn't understand it.

[00:01:42]
Recursion was my personal hardest one.
>> [INAUDIBLE] 1.5.
>> 1.5, really? I've met very few 1.5 understanders, right? Because either you get it or you don't get, it is how I've generally kinda found it. So the simplest way is a function that calls itself, and this keeps happening until it reaches something known as a base case.

[00:02:04]
At that point the function no longer calls itself, and it's able to return out some value, or do some operation, or do something, right? And so that depends on what you're doing with recursion. In JavaScript, you'll also do things like async recursion, where you call a function that needs to do something, it comes back, then you can call a function that needs to do something, and come back.

[00:02:23]
You can think of walking a file tree with async functions, would be an example of async recursion. Very, very similar, though it's not quite recursion. Recursion is hard. It's honestly the hardest topic for me to get over. I found it to be extremely difficult. So we're gonna go over to things with recursion.

[00:02:41]
And what I'm hoping is that by the end of this, you will be you'll feel very natural with recursion. You'll feel like, okay, this actually isn't all that hard, it's actually pretty straightforward don't feel bad if you don't get it. It's just one of those things that it feels trivial when you understand, exceptionally complex when you don't.

[00:02:58]
And it's just it's hard, so we're just gonna do it. So the simplest form of recursion is this right here. You would know this as a sum, right? So if I said sum the numbers between zero or from one to 100, you'd be like Gauss and say, well, [INAUDIBLE].

[00:03:13]
And I'll say, no, sum it, and that's what we do. And so this would be an example of summing it. What's exactly happening here, we're gonna also write out everything that's happening here. But you can see, I have a function, foo, that takes in a number. The base case, of course, is when we're equal to 1.

[00:03:28]
The sum of 1 is 1, right? We know it, we could technically extend the base case for as long as we know the sums, but this is just the generally easiest way to think of it. So when the number is not one, we are going to add the number itself plus recall foo with one less than its current number.

[00:03:46]
So it'd be five to four, to three, to two, to one, and there we go. Now, we're gonna draw what's happening here because there is this whole problem. Now, one thing I really did wanna highlight, I'm gonna say this five more times, I'm positive I have it my slides like five more times, but base case is extremely important.

[00:04:02]
Always think clearly what your base case is. If you don't know your base case, recursion is extremely hard. If you know your base case and you can make it clever, recursion becomes exceptionally simple. So, good thing's to understand. So, let's go over to here and let's create this beautiful, let's just walk through exactly how it works.

[00:04:24]
So in our function, I'm just gonna jump back here for a second, we have this. So I'm just gonna write it in some pseudocode, make it really simple, and then we're gonna actually go through exactly what is happening. All right, so it's gonna look something like this. We have foo(n), which is a number.

[00:04:38]
And if n=1, then we're gonna return one, else, we're gonna return n+foo9n-1). Now for all the Q A's out there, all the feeling of QA you're like, well, what will happen if I pass in zero? We're not gonna, we're only concerned with ones or higher, okay? Don't do that, don't break this code.

[00:05:02]
So you can see right here that it's pretty simple code. So let's write out exactly what's happening. There's something that's very important to understand about recursion and really about function calling. There's three values you can kind of really help to visualize this. There is something called a return address.

[00:05:19]
Every single time a function is called, it needs to know how it got here, right? Cuz when the function is done, it needs to literally go back and hand back out its value, right? And so it needs to know where that value goes to. Another important part, of course, is the actual return value, right?

[00:05:35]
I need a value that I could return. Now in more traditional languages, they compile a lot of these things, in there's a lot of sweet optimizations, blah, blah, blah, blah, blah. But what matters is that they have to make kind of a space for it, right? And then lastly we have our arguments, right?

[00:05:49]
That makes sense, we have to pass things into the function. So every time you call a function, this is kind of roughly some memory that is put into your system, we'll see. So when I call foo5, what happens? Well, our return address is whoever called foo5, right? We don't know who it is, doesn't matter for this case, someone called us with foo5.

[00:06:12]
Our return value is, well, we don't actually know our return value at this moment, do we? No, we know that it's 5+, but we don't know what it completely is. And then lastly, we have an argument of 5, right? This all makes sense. So then again, foo5, what does it do?

[00:06:32]
Well, let's look at the code really quickly. Is it one? No it's not. Let's take five, let's take the argument and add it to argument minus one from the next one. So, foo4. Well, what is foo4 pointing to? It's pointing to five, right? It points five, that's where I'm gonna return when I am done.

[00:06:52]
And so now we're gonna have 4+ and our argument, of course, is 4. Now, we do it again because again, it's not one, therefore, we recurs, foo 3. Well, our return address it's 4, our return value is three plus. We still don't even know it yet, so, 3.

[00:07:15]
Foo2, our return values is 2, oops, I just gave away the game. 2+ and our argument is 2. Again, lastly, finally get to foo1. What happens at foo1? Well, we get into here, we execute is foo or is n1? Yes it is, return a 1. We finally have stopped recursing.

[00:07:36]
We've hit a base case, we no longer need to keep calling functions. Now, if instead we had throw error right here, that is where a stack trace comes in. You've seen the stack traces, you've seen error stacks, it's literally the stack of functions that have been called. You would see something like, let's pretend this is line two, you'd see something like error at foo line 2.

[00:08:01]
And then you'd see somewhere below, this would be say, three, right? Then you'd see something like foo3 foo3, right? Because each one of these ones we're aware occurs from, so that's how you can help visualize these things. And we've learned about a stack before, so this should make more sense of what is literally happening underneath the hood.

[00:08:22]
All right, so for one, it returns 1, argument was 1, it returns to 2. Sorry, I forgot to put that. So when it returns to 2, we now actually can do something. So the return value is put right here. We've now completed this, now we can return again.

[00:08:36]
That value is put right here, which is 3. Now this thing returns again, which is now 6. Sorry, I did bad math. I gonna just undo that. It's very unpleasant to the eyes to look at, 6, awesome. And then this is 10, and then five plus 10 is returned out or 15.

[00:08:54]
You can see that it goes down the stack, then up the stack. And that's really, really important to see, because it also opens up some properties to us that we need to think about. So, if we look at this code, I told you that there's two steps, right?

[00:09:09]
One, base case. And then two, recurse. Click that writing, it's beautiful. So this is obviously the recurse, this is the base case. Eventually we hit the base case, we stop recursing, we undo our function stack, as we showed right here with the return value slash the return address.

[00:09:29]
All right, but there's something very interesting about this. Notice that for a while, we kept going downwards, right? We kept going downwards, we eventually hit some sort of bottom, and then we went upwards, which means that our recurse can actually be broken into three steps. And this becomes exceedingly important in later data structures, especially when it comes to something called pathing.

[00:09:48]
You're gonna really want to understand this. Is that recursion can actually be broken down or the recurse can actually be broke down into three steps, all right? So the recurse thing can be into three steps. You have a pre, which means you can do something before you recurse.

[00:10:04]
In our case this was literally n+, right? We took n and we added it and then we did the recursion part. So this is kind of a pre thing. Now then, we recurse, which actually does the calling of the function, right? And then there's actually an availability for some sort of post operation.

[00:10:25]
Does that make sort of sense? We can do something else after recursing. So we didn't actually have to return here, right? We don't have to return, we could have said, hey, out equals this, then console logged something, and then returned out, right? Which would have actually, let's say we console logged, ley's just say we, here I'll just break the word log.

[00:10:49]
If we would have logged out in what we would have seen logged is, 12345. That makes sense because we did it post. Meaning that as we recurse we did the pre of adding, we went into foo4, we did the pre of adding, we went into foo3, and we went into foo2, we di the pre of adding, we went into foo1, we did the post of logging which is logging out one, we returned it back out 2.

[00:11:13]
2 did the post of login have 2, retuned it back up to 3, 3 did the post login, 3 turn it back on 4, 4 to the post of login 4, 4 return five, and five logging and then, boom, we're out, we're done, right? So you can see these three actual breakdowns and you may not actually use them, but they are extremely important to have in your head because they're very, very valuable when it comes to pathing.

[00:11:33]
And so I wanted to really make sure we hit home on this cuz I do feel like this is something that can be a bit confusing. You may not even realize you have that tool in your toolbox and you could be recursing. Friends don't let friends recur without the toolbox, it's just a phrase we've all said at least once in our life.

[00:11:49]
Does that feel pretty good? Everyone feels like recursion is a bit more clear, though you may not know how to use it? You can kind of hopefully see it a little bit clear. We're gonna rely a lot on recursion coming up here. And so that's why I wanted to do this, Is it's really hard to do a tree without some knowledge of recursion.

[00:12:06]
It's hard to do graph algorithms without some knowledge of recursion. You don't have to do not all algorithms on graphs require recursion, take the shortest path, you don't have to do recursion, right? You can find the shortest path in a graph with non negative weights, without using recursion ever, so it is possible, but it's hard.

[00:12:25]
Anyway, so this was the simplest way to do recursion, but it never helped me. I genuinely felt like I never was really able to grok recursion, seeing this. It feels too simple, cuz part of my lizard brain says, this is too simple, why not a For Loop, right?

[00:12:41]
I can't understand why you wouldn't use a For Loop or can't rock the need of it, I can't really see it, it just was really, really hard. So big mistake of recursion, solid base case then recurse, just remember that that please, it's so important, Holy Cow. All right ,so we're gonna walk through the problem that truly helped me understand recursion.

[00:13:01]
And this is actually a pathfinding algorithm on a graph, but don't worry we're not gonna do all that fancy stuff, we're gonna break it into something that's really digestible and really easy to understand. So is everyone ready? Very, very excited? I'm very, very excited, whoa, I can't wait.