All right, recursion. I'm so excited to be here. Not the least because it is Unit 10. I'm sure we're all excited about that. But I really like recursion. Part of that is because I was into compiler writing, or did my research in compiler writing. And recursion does require understanding a just a little bit about how the computers stack works. You don't really have [INAUDIBLE] it's an excuse to understand part of it. That said, there is folklore out there that recursion is horrible and hard and nasty. And it really doesn't have to be. I will just share with you the most important thing to know up front. That is that recursion and loops can do the same things. Anything you can write with recursion, you write with loops. The only reason we'd use recursion is when it makes our lives easier. You may have heard bad things about it because some Persnickety computer science teachers, most likely professors, probably try to make people use recursion in ways it wasn't really well done just to test them. But we're not going to do that. And CS awesome is really good about really easing students into recursion. So that's we're going to have today. I have lots of teacher tips for you, though. They start off on ten point one point one, what is recursion, by basically wanting you to understand one thing. Recursion is when a method calls itself. Recursion is when a method calls itself. Recursion is when a method calls itself. And this is a particularly amusing code you would never ever write because it does something called infinite recursion. But it's a great sort of simple example. It's like we have a method called neverEnd. And then, all we do is call neverEnd. And it'll just go ding, ding, ding, ding, ding, okay? Infinitely, again. So this is not useful code, but it gets the basic point across. And that is really all they want right now. Now, I know that's what all they want. But let me tell you, as a teacher, just to be clear, I added that second print statement. In this particular example, that statement would never be printed. Because you would call neverEnd from me, it would say this is a method that never ends and it would call neverEnd. It would go back up, come in, this is a method that never ends, call neverEnd, and go back up, okay? So it's okay if that seems confusing now. I just want to point out that that is true about this, that's where the infinite part of the recursion is. It's like having infinite loop, right? There is some code that will never get executed. In this case, that second print statement. All right, but again, right now, only thing they need to know is a recursive method is one that calls itself. And it sounds crazy, like what the heck would you want that for? But we'll get there? So there's a couple of questions that really just get kids to look at that. It's like let's look at the one on the left. Do you see any calls to mystery inside the mystery code? Nope, so it's not recursive. On the right, mystery2, let's look at the code in there. I don't need to understand what it does, we'll get to that. But you can see that we call mystery2. And they don't even need to point this out at this point, but for you, the teacher, we're calling it with with a value of x that's changing. And that's going to help us make sure we're not doing infinite recursion. Again, we'll get to that. So there it is, mystery2. Then, we have some why do we use recursion? And again, they're saying what I just told you. It's used to solve problems when the structure of the problem matches recursion, which means it repeats, okay? This is actually, though, fairly hard to understand without some examples. They give an example here, no image. Feel free to use this. But they say look, what if you want to know how much space all your files use are in the library folder? Well, you do that, but you can't just look at the files in the library folder if there are folders inside there. You have to look at each one of those folders. This, I could imagine doing is a loop, in this very abstract kind of way. But it also just basically says look, if we say to find out how much memory is used in one folder, you have to add up all the memory used by the folders inside it. And if each of those folders have folders, then you have to add up the ones inside there until eventually you get to places that don't have subfolders. The other example they give, and you'll find a lot of these on the web, some decent YouTube videos explaining how to make these. And I don't even know how to pronounce this correctly, Sierpinski's triangle. It's not my favorite example to use because it's not super easy to do with code. But you can see this idea of a single triangle, you break it up into four smaller ones, and then take each one of those and break them up into four smaller ones, etc., etc. Actually, it's only three because you don't actually break up that middle triangle. Anyway, there you are. But you can use it to many other things. Traverse strings, arrays, array list objects, like a loops. And again, pointing out here, any recursive solution could be written with loops. And we are not going to force kids to try to write recursive solutions when it doesn't make sense for doing it that way. So use recursion when it's easier, and when the structure of the problem sort of matches recursion. And I understand you might not know what that means yet, but we're going to develop some intuition into that. Although, you did do block to text, right? That idea of the tree that you go up the trunk, turn left, draw a tree. Turn right, draw a tree, and then go back down the trunk. I have no idea how to do that with loops. And I actually did some looking around to see if I could find some code that did it with loops. And wasn't able to really quickly, and decided that wasn't the best use of my time. But anyway, you kind of see it's like that idea of making an assumption, like somehow, some way, if you can just solve this slightly smaller problem, and I can take two slightly smaller problems, in the case of the tree, and put them together, and then I can get it? That's what recursive sort of structure is like. And there we are. Again, it's the up, and then if you just imagine you've already done the tree trunk there, then the stuff that's in orange, those are a left tree and a little right tree. They're just slightly smaller. And then, if you just look up the left tree to go up the trunk, then you've got a left tree and a right tree, they're just slightly smaller. That's the structure.
