In the context of computer science, recursion occurs when a function calls itself. Recursion is a powerful programming technique due to its ability to maintain state during subsequent function calls; however, problems like a stack overflow can arise if a recursive function is not implemented correctly.
(suspensful music) - Let's actually start getting into applied concepts. This is purely conceptual, mathematical, right? I think that's pretty much the only thing we do that way. Everything else should be pretty applied here. So let's talk about recursion. Pretty, excuse me, pretty essential part of web development here or just writing code in general. So recursion is when you define something in terms of itself.
So have you ever asked someone a definition of a word and they just use the same word to define itself? One, it's super annoying because they didn't tell you anything, right. So like, recursion is very not useful in English, however, it turns out to be very useful in computer science. So I think the one I had here was a computer, right. So what is a computer, right. It's something that computes things, right. Something like that, that would be a recursive definition. It's using something to define itself. Or if you look at this image right here, we have a triangle made up of other triangles, right.
This is a recursively defined triangle because the triangle is made up of smaller triangles, which is made up of smaller triangles, which is made up of smaller triangles. That is the essence of what recursion is. As applied to computer science, you define a function that calls itself. You're using a function to define itself, which seems pretty mind-bending and it is. The first time you learn recursion, it's tough. Once you get it, you start to realize it's hard, but it's simple.
I guess that's what I'm getting at. It's used everywhere. It's a very useful technique. Why it ends up being very useful is you have these recursive calls. Each level of the recursive call is able to maintain its own state, which ends up being very useful. We'll be using that later once we start getting into merge sort because that becomes very essential to us. Recursion is very very useful for some problems, however, it does carry a bit of a cost for it.
Because you make all these calls to the function, it starts adding more and more functions to the stack. We'll talk about stacks later as well. Basically, the idea is that calling a function is not necessarily free. It's pretty close to free so for the most part, we generally ignore the cost. But when you start calling a function a hundred, two hundred times, that actually does carry a cost. Especially with memory because your computer now has to keep track of 200 different memory calls. At some point, some of us are going to see stack overflows. First of all, everyone uses stack overflow.
That's how I learned to program, copy and pasting from stack overflow, which is a skill by the way. That's where the stack overflow comes from, if you recurse too far down usually by an infinite recursion. If you have a recursion that just keeps on going forever, your computer is going to say what the hell is you doing, I'm going to blow up and then it blows up. That's what a stack overflow is when you recurse too far down and eventually the computer says I have run out of ability to track new calls into memory.
It's not free. That's why recursion it's a heavy tool and not one you want to apply lightly. If you can do it iteratively, that's usually the preferred way. Iterative means that you do it with loops instead of recursion. However, you might remember earlier where I was saying that generally you want to favor readability over performance. If recursion makes something very readable to someone, which you'll see here in a little bit that it absolutely does do that for some problems.
You want to favor that and if you go later and if you figure it's a big bottleneck in your program, at that point you'd refacture to be iterative instead of recursive. Always, always, always favor readability. You're going to make yourself and others very very happy in the long run. In other words, don't be clever unless you have to be, please.
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