Brian walks through a few recursion examples, including how to generate a Fibonacci sequence. He also stresses that the beginning of any recursive function should contain the base case to prevent any stack overflow errors.
(dubstep) - [Brian Holt] If we go back here, I'm gonna click on the example up here. First of all, this little method up here, this is basically console log for the DOM. You can essentially ignore it, but every time I'm doing that it's just writing something down here. Oh, let's talk about CodePen for a second. So, first of 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. Like, I love the guys over at CodePen. Guys and girls, I should say. Guys and women. 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.
It's hard to say. Try to say that seven times fast. Okay. So, basic recursion. If you look down here, you can see down here it's just logging out one, two, three, four, five, right. So, let's look at what we did here. Called basicRecursion with five and one, right. Basically, I want to say what's the current number in our recursion, and what's the max number I wanna log out here.
Okay. So, the first line. The first line of any recursion, I'm not going to say a new recursion, but I'm going to say it's about every line of any, the first line any recursion I've written. So, I'm just going to extrapolate with it to you, and say it's just going to be like all recursion you write. It's the first line that's going to be the base case, right. The base case is when you stop recursing, and the reason why you write this first 'cause if you don't write it, you get stack overflows, right.
That's why you have to have your base case, and you wanna have that very well-handled first. It's like when do I stop? Okay? So, in this particular case, I wanna stop when current is larger than max, as soon as it's larger, than max, then it's like "Okay, done, get out of here." Right. So, that's what this is. Okay? And then all I'm going to do is write out what current is to the DOM, and that's it. And then, after that, I'm going to call itself, basicRecursion, right. basicRecursion is calling basicRecursion, right.
And I'm going to call it with max, right. It's 'cause I'm going to keep passing that max down, and then I'm gonna call current plus one, right. So... Let's get this. So, as you might imagine, so we're going to call it first with one, right. Because we... Where is that? Let's get a white here.
Right, so we have white. Oh, there we go. So, we first call with one, so that's what's current is going to be. And then... If you just imagine this as a call stack, right. So we'll call it with five comma one. And then it's going to call it with five comma two. Right, then it's going to call it with five comma three. Then it's gonna call it with five comma four. Five comma five, and then actually, it's gonna call it with five comma six. I'm going to put that over here. Five comma six, right.
But once it reaches that, six is greater than five, right? Geez, I can draw, but you get the point. So, that's when current is larger than max, and at that point, it starts returning, right. And then, at that point, it's gonna start coming down the stack, right. So it's gonna start popping these off, right. So, then it's going to do this, then then it's going to do this, right. Right now, we're not doing anything after basicRecursion, but at this point, we could do something after basicRecursion, right? So, you can view things going up and down the stack. Right, and then you eventually get there, and then, it's over, right.
That's the basic gist here. So, any questions, this is a very worthless application of recursion, 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.
So, if you look down here, most of us are familiar with Fibonacci sequences, but I'll explain it. I promised this wasn't going to 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, one plus one is two, two plus one is three, three plus two is five, five plus three is eight, right. So on and so forth. And then, those numbers start getting pretty large. 'Cause you start getting higher and higher, right. So, you know, this one plus this one, 18th plus 19th term is the 20th term, right.
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. Well.. We have the 18th term, which is defined as the... 17th term plus the 16th term, right. So, Fibonaccis are recursively defined because it's defined using Fibonaccis, right. So, that's why recursion lends itself well to this problem, right.
So, yeah, Fibonacci... Takes in number, and it can be any number, right. And the first thing we thing we do is what? Base case, right? So, if it's less than or equal to two, that's just a given number, right. It's just one, right. That's the given thing in Fibonacci sequences, I promise. I guess another little side note here. You could do if.. N is triple equals zero...
Or n is triple equal one, right. Because those are really the only ones that we anticipate seeing, right. Fibonacci of negative one doesn't really make much sense. At least it doesn't to me. I don't know if it does. However, with your base cases, you want to be pretty aggressive, because 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, I don't know this one's going to do.
It's just going to infinitely recurse, right. Because you're going to be adding negative one to negative two, negative three to negative four, right. And it's just going to recurse into oblivion, right. So, that's why you wanna do things like this where it's pretty aggressive in terms of what your base case is going to be. Because you want to guard yourself against you, either yourself or others, right. 'Cause someone at some point is gonna call, you know, Fibonacci with negative one, and then you're entire program blows up.
Okay. So... if it's less than or equal to two, then you just return one, right. That's the given. Else, we're going to return Fibonacci of n minus one plus Fibonacci of n minus two. Now, like... That feels, at least to me, that looks really nice, right. It's very well-written. And it's pretty clear what it's doing, right. You're just a... If I have Fibonacci of n, To find it is Fibonacci of n minus one plus Fibonacci of n minus two, right.
That works well. Yeah, pretty exciting stuff. However, let's talk about why this is actually kind of crappy. (Brian scoffing) Well... If you have... Going back to our console down here, going down here to the numbers like 6765, right, that's a huge number. You have to think about what's actually happening underneath the hood here, right. We're actually adding one, right? Because everything else only ends up to be one, right.
We have no larger value that starts out larger than one. So that says in order to achieve this number, we added one to itself 6765 times. Which is not the most efficient way to derive the number. So that's why this solution actually kind of sucks, because we called the function 6765 times at least, right. So, while this is very elegant and works very well for this problem, it's very readable.
You're actually, probably in this particular case, if it was a bottleneck for you, you'd actually probably want to write this using loops. And the loops version of this is gross and nasty looking. Well, I mean, it's certainly not this elegant anyway. But, in any case, that's how you would solve. This is a problem that lends itself well to recursion. And see, and there's a trade also you need to make in your head. It's like, "Well, can I afford "to have the elegant code here", right. 'Cause if you call this once a day, then you know, what the hell, add your number a bunch of times and call it good.
But if this gets done with every user request, it's like "Yeah, you probably want to "use loops or iterations for that". Any questions? Okay. - [Student] What's the big O on this one? - Big O on this one would probably be... You have to go through everything at least once...
This is a default parameter. Maybe it's helpful if I just write this. 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. Whatever, how many I put.
And then on the same, right here is document dot... write. And this an ES6 template string, which if anyone has ever written Bash before, it should actually look familiar to you. But basically, it's saying substitute this here, or you could just do br... plus msg, that's also the same thing. So this is the ES5 version of that.
I think those were, yeah, they're equivalent now, so, good question. - [Student] Technically, you're returning dot writter, right? - Yeah, this is implicit return. I mean, I could do this, and it wouldn't be an implicit return. In this case, it doesn't matter 'cause I don't care what dot writter returns. But if you leave off the curly braces in an arrow function, it's an implicit return.
We stole this from CoffeeScript. Not a huge CoffeeScript fan, but this turned out okay, so thanks CoffeeScript.
Note: This course was created by Frontend Masters. It was originally released on 07/12/2016. We're pleased to host this training in our library.
- Big O
- Sort: Bubble, insertion, and merge,
- Median values
- Set, map, stack, and queue
- Array lists and linked lists
- Binary search tree
- AVL tree
- Single rotation and double rotation
- Hash table
- Functional programming
- Map, reduce, and filter