Four Semesters of Computer Science in 5 Hours Recursion Example

Transcript from the "Recursion Example" Lesson

[00:00:00]
>> [MUSIC]

[00:00:04]
>> Brian Holt: If we go back here, I'm gonna click on the example up here.
>> Brian Holt: First of all this little method up here, this is basically console log for the DOM [LAUGH]. That I mean, you can essentially ignore it, but every time I'm doing that. It's just writing something down here.

[00:00:23] Let's talk about CodePen for a second. So first all, if at this point you don't have a CodePen account. I'm gonna go ahead and suggest you sign up for one. You don't have to, but one, they're super great. I love the guys over CodePen, guys and girls I should say, guys and women.

[00:00:40] And then the second part is that you can fork these, you can click this little fork thing up here and then it'll save it to your CodePen account. And you can refer back to these later, so I think that's useful for you. Okay, so let's look at just the worst application of recursion but very basic version of recursion.

[00:01:02] It's hard to say. Try and say that seven times fast. Okay. So basic recursion. If you look down here, you can see down here is just logging out 1, 2, 3, 4, 5, right?
>> Brian Holt: So, it's like what we did here. Called basicRecursion with five and one, right?

[00:01:27] Basically I wanna say, what's the current number in a recursion? And what's the max number I wanna log out here, okay? So, the first line [COUGH]
>> Brian Holt: The first line of any recursion. I'm not gonna say any recursion but I'm gonna say it's about the first line of any recursion I've written, so I'm gonna just extrapolate that to you.

[00:01:51] And say, it's gonna be like all the recursion you write. Is the first line gonna be the base case. The base case is when you stop recursing, and the reason why you write this first cuz if you don't write it, you get a stack overflow. That's why you have to have your base case and you want it like have that very well handled first, is like when do I stop?

[00:02:14] So in this particular case, I wanna stop when current is larger than max, as soon as it's larger the max, it's like okay, done get out of here. So that's what this is, okay? And then all I'm gonna do is write out what current is to the DOM, and that's it.

[00:02:29] And then after that I'm going to call itself basicRecursion, right,?BasicRecursion is calling basicRecursion. And I'm gonna call it with max because I'm gonna keep passing that max down. And then I'm gonna call (current+1) right? So, let's get this.
>> Brian Holt: So as you might imagine, so we're gonna call it first with one right?

[00:03:00] Where's that? Let's get a white here
>> Brian Holt: So we have white, there we go. So we first call with one, so that's what current's gonna be and then if you just imagine this as a call stack. So we call it with 5,1 and then it's gonna call it with 5,2, right?

[00:03:24] Then it's gonna call it with 5, 3, then it's gonna call it with 5, 4, 5, 5, and then actually, it's gonna call it with 5, 6, let me put that over here, 5, 6, right? But once it reaches that 6 is greater than 5, right? Geez, I can't draw, but you get the point.

[00:03:44] So that's one current is larger than math, and at that point starts returning, right? And then at that point, it's gonna start coming down the stack, right? So it's gonna start popping these offers, so then it's gonna do this, it's gonna do this. Right now, we're not doing anything after based recursion.

[00:03:59] But at this point, we could do something after based recursion right. So, you can do things going up and down the stack, right? And then you eventually get there, and then when it's over, right? That's the basic gist here.
>> Brian Holt: So any questions? This is a very worthless application of recursion.

[00:04:19] Something that you really should not do. This should be done with a loop, right? But that's just to demonstrate to you what it's for, or how it is. So let's look at an actual real application Fibonacci sequences, right? So, let's bring this up again. Close that.
>> Brian Holt: So, if you look down here.

[00:04:47]
>> Brian Holt: Most of us are familiar with Fibonacci sequences but I'll explain it. I promised this wasn't gonna get mathy and it got mathy again so, sorry not sorry. Okay, so Fibonacci sequences are basically the two previous terms added together, right? So 1 plus 1 is 2, 2 plus 1 is 3, 3 plus 2 is 5, 5 plus 3 is 8, right, so on and so forth and then those numbers start getting pretty large as you start getting higher and higher, right?

[00:05:12] So this one plus this one, 18th plus 19th term is the 20th term, right?
>> Brian Holt: So, let's look at actually how you would do that using recursion. So let's first discuss how we settled on using recursion in this particular case, while we have the 18th term which is defined as the 17th term plus the 16th term.

[00:05:39] So Fibonacci is our recursively defined because it's defined using Fibonacci's, right? So, that's why recursion lends itself well to this problem. So we have Fibonacci, takes in a number and can be any number and then the first thing we do is what? Base case, right? So if it's less than or equal to two, that's just a given number.

[00:06:05] It's just one, right? That's the given thing in Fibonacci sequences as I promised. I guess another little side note here. You could do, if n === 0, or n === 1, right? Because all those are really the ones that we anticipate seeing, right? Fibonacci of negative one doesn't really make much sense.

[00:06:33] At least it doesn't to me. I don't know what it does. However with your base case is, you wanna be pretty aggressive cuz what happens if someone does throw in there like negative one, negative two, or something like that. Your base case then gets out of whack right, and then you.

[00:06:50] I don't know what's going to this one's gonna do. It's just gonna infinitely recurse because you're gonna be adding negative one to negative two, negative three to negative four. And it's just gonna recurse into oblivion, right? So that's why you wanna do things like these, where it's pretty aggressive in terms of what your base case is gonna be.

[00:07:11] Cuz you wanna guard yourself against you, either yourself or others, right? Cuz someone at some point is gonna call Fibonacci with negative one, and then your entire program blows up.
>> Brian Holt: Okay, so if it's less than or equal to two then you just return one, right? That's the given.

[00:07:35] Else, we're going to return Fibonacci of n -1 plus n of fibonacci of n- 2. That feels like, at least to me, that looks really nice, it's very well written and it's pretty clear of what it's doing, right? You're just a top. If I have fibonacci(n), it's defined as fibonacci(n- 1) + fibonacci(n- 2), it works well.

[00:08:06] Yeah, pretty exciting stuff. However, let's talk about why this actually is kind of crappy. [LAUGH] Well, going back to our console down here. Going down here to the numbers 6765, right? That's a huge number. You have to think about what's actually happening underneath the hood here. We're actually adding one because everything else only ends up to being one.

[00:08:34] We have no larger value that starts out larger than one, so that says in order to achieve this number we added 1 to itself, 6,765 times. Which is not the most efficient way to derive a number, right? So that's why this solution actually kind of sucks because we called the function 6,765 times at least, right?

[00:09:00] So while this is very elegant, and works very well for this problem is very readable, you're actually probably in this particular case. If it was a bottleneck for you, you actually probably wanna write this using loops and the loop version of this is gross and nasty looking. Well I mean, it's certainly not this elegant anyway.

[00:09:19] But in any case, that's how you would solve this problem that lends itself well to recursion. And see, these are trade-offs that you need to make in your head is like, well can I afford to have the elegant code here, right. Because if you call this once a day then what the hell, add your number a bunch of times and call it good.

[00:09:37] But if this gets done with every user request is like, yeah, you probably want to use loops or iterations for that. Any questions?
>> Speaker 2: Okay, [COUGH] what's the big O on this one?
>> Brian Holt: Big O on this one would probably be.
>> Brian Holt: You have to go through everything at least once

[00:10:08]
>> Brian Holt: And log in, I'm gonna guess, I don't actually know. So, that's a guess but good question.
>> Speaker 3: There's another question, can you explain how WR function works?
>> Brian Holt: Sure, from shift value, okay? WR, this is some ES6 magic. Okay, so this is an arrow function. An arrow function is just another way to write a function in JavaScript.

[00:10:38] This is a default parameter. Maybe it's helpful to just write this.
>> Brian Holt: So another way to write a function, right? This is a default parameter, it says if you're not given anything for this then have a default parameter. So, a way of doing that is if I didn't get anything from message, then message equals that, right?

[00:11:07] Whatever how many I put. And then on saying right here, is document.write. This is an ES6 template string, which if anyone's ever written bash before that syntax should look familiar to you. Basically it's saying substitute this here or you could just do br plus msg. That's also the same thing.

[00:11:36] So, this is the ES5 version of that. Singles are equivalent now. So, good question.
>> Speaker 4: Technically you're returning document, right?
>> Brian Holt: Yeah, this is an implicit return. I mean I could do this and it wouldn't be an implicit return. In this case, it doesn't matter because I don't care what it returns.

[00:12:06] But if you leave off the curly braces in an arrow function, it's an implicit return.
>> Brian Holt: We stole this from CoffeeScript. Not a huge CoffeeScript fan, but this turned out okay. So thanks, CoffeeScript.