This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Recursion" Lesson
[00:00:00]
>> [MUSIC]
[00:00:04]
>> Speaker 1: Let's actually start getting into applied concepts. This is purely conceptual mathematical and 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 [COUGH] excuse me. Pretty essential part of web development here or just writing code in general.
[00:00:28] So, recursion is when you define something in terms of itself. So, if you ever asked someone a definition of a word and they just used the same word to define itself. One, it's super annoying, cuz I didn't tell you anything. So, like recursion is very not useful in English.
[00:00:43] However, it turns out to be very useful in computer science. So, I think the one I had here was computer. So, what is a computer? It's something that computes things, like 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.
[00:01:02] This is a recursively defined triangle, because a triangle's made up of smaller triangles, which is made up of smaller triangles, which is made up of smaller triangles right. That is the essence of what recursion is. As applied to computer science, it basically, you define a function that calls itself.
[00:01:20] So you're using a function to define itself, which seems pretty mind bending and it is. Like the first time you learn recursion, it's tough. But once you get it, actually you start to realize that it's hard, but it's simple. Like I guess, that's what I'm getting at and it's used everywhere.
[00:01:40] It's a very useful technique. Why it ends up being very useful is you have these recursive calls and 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 one once we start getting into like merge sort, because that becomes very essential to us.
[00:02:04] Recursion is very, very useful for some problems. However, it does carry a bit of a cost for it. Because you just make all these calls to this function, it starts adding more and more functions to the stack. We'll talk about stacks later as well. The basic idea is that calling a function is not necessarily free.
[00:02:23] It's pretty close to free. So for the most part, we generally ignore the cost. But when you start calling a function a 100, 200 times that actually does carry a cost, especially with memory. Because your computer now has to keep track of 200 different memory calls and at some point, some of us are going to see stack overflow.
[00:02:42] Like first of all, everyone use a stack overflow. That's how I learn to program as copy and paste it from stack overflow, which is a skill, by the way. [LAUGH] But that's where the stack overflow comes from is, if you recurse too far down, usually by an infinite recursion.
[00:03:00] Like if you have a recursion that just keeps on going forever, your computer's gonna say, what the hell is you're doing? I'm gonna blow up and then it blows up. So that's what a stack overflow is as is when you are cursed too far down and eventually computer says, I have run out of ability to track new calls into memory.
[00:03:17]
>> Speaker 1: So it's not free, that's why recursion is a bit of a it's a heavy tool not one that you wanna apply lightly. If you can do it iteratively, that's usually the preferred way. Iterative, it's means that you do it with loops instead of recursion. However, you might remember earlier where I was saying that generally, you wanna favor readability over performance.
[00:03:40] So 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 wanna favor that. And then if you go later and you figure out that this is a big bottleneck in your program, that's at that point you're be functioned to be iterative instead of recursive.
[00:03:57] So always, always, always favor readability. You're gonna make yourself and others very, very happy in the long run. In other words, don't be clever unless you have to be, please.