[MUSIC] In this video I'm going to introduce the concept of recursion. Recursion is an extremely powerful technique in computer science where by you define a function. That then calls itself. [LAUGH] All right? Now this may seem simple but it's actually quite complex. It's used in many interesting situations to allow you to write complex programs succinctly and concisely. Now the key here is that when you call the function again, you better be calling it with less data than you had originally. [LAUGH] Otherwise, it's never going to finish. All right. Let's take a look at how all this works. Recursion is a powerful computation technique that is best utilized when a problem, exhibits common substructures. Okay, that is to say I have a problem, which can be composed of a collection of identical, or similar, subproblems. That are each smaller than the original problem, okay? So for example, consider the problem of summing up all the numbers from n down to one. For all positive n. Okay, so I want to sum n plus n minus 1, plus n minus 2 and so on down to 1. All right, that's a simple problem, but that problem does have common substructures, right? I can think of this instead as the problem of taking n and adding it to, summing up the numbers from n minus 1 down to 1. And then when I have that problem I say, how do I sum n minus one down to 1? Well, that's n minus one plus, the sum of all the numbers of n minus two down to one. And so on. Okay, and ultimately I get down to one itself, and I know that the answer of the sum of numbers from one down to one is one, okay? So you know, I can think about finding, the sum of integers. As ha, exhibiting this common substructure, and I can solve it in this recursive way, okay? I can say that the base case here, is one, when I have one I know how to compute the result directly, and the recursive case is any number greater than one. And the sum is simply the number that you have. Plus the sum of all the numbers, from N minus one, down to one. Okay. I've restated the problem, in terms of itself. Okay. So when I, try to solve these recursive problems I generally employ a two step process. The first case is to identify this base case, all right? And, the second one. Is to identify the recursive case. All right, now the base case has to be something you can solve directly. You know how to compute the answer. I don't need to call the function again or do anything else. That doesn't mean it needs to be trivial to solve, it just needs to be solvable directly. Okay, the recursive case however, is solvable by taking a piece of the problem and then recursively solving a sub problem that's pretty much identical or similar to the original problem. Okay? And by doing that, I have now identified the base case and the recursive case, I can write the recursive function. All right, so let's talk about this a little bit more carefully. Let's say I'm trying to create, a, function called Sum up to n, all right? And so I have to identify the base case. So I first say, hey, what is the base case? All right? The base case is that the answer is 1 when. You know, n equals 1, right? Okay, fine. And the recursive case, is, n plus sum up to, n minus 1, when n is greater than 1. All right. And sort of mathematically you, you, write functions like this. I might call it, you know, s of n, is 1, when n is equal to 1. And it's n plus s, n minus 1, when n is greater than 1. All right. And so, you know, this is the, base case here. This is the inductive case or recursive case. Mathematically I'd call it inductive, in computer science I'd call it recursive, case. All right, and you can write it either way here, but I've basically told you. What to do when n is 1, what to do when n is greater than 1. And now I have solved the problem. And notice that the base case as I said, I can solve it directly, the recursive case, well, I need to use myself. To solve it. But, again, the key here is I'm going to solve it on a smaller problem. N minus 1 is smaller than n so now I have some hope that this fun, this process will actually re-terminate, that eventually I will get down to the base case and I will be able to solve the problem directly. I want to start by showing you an example of recursion outside of computer science. The Cat in the Hat is obviously recursive, okay? [LAUGH] Now you can see this is a well-loved book in my family and we use it all the time. And. The basic story is, that, the Cat in the Hat shows up uninvited. [LAUGH] Whoa, what a surprise. Right? And the Cat in the Hat makes a giant mess, that, the Cat in the Hat can't quite take care of by himself. So what does he do? He relies on recursion. Okay? The Cat in the Hat happens to have other cats inside his hat. All right? And he gets Little Cat A out. Little Cat A decides to help out, but Little Cat A is not, exactly sufficient to solve the problem so we need more recursion. And we get Little Cat B, all right Little Cat B is not sufficient, so we go on and we get Little Cat C. And we keep going and going and going until finally, we get Little Cat Z, which is too small to see, right, he fits on [LAUGH] fits on his thumb, but he's not actually there, you can't see him. And little cat Z has the Voom. And the Voom allows them to actually clean up the mess. Okay? This is recursion in action. See, I bet you didn't know that Dr. Seuss was actually a computer scientist. Well, [LAUGH] he was. All right? How does this relate? Well this is exactly how we think about recursion. I have a problem. I solve it. With myself. All right, and I keep solving it with sm, smaller and smaller instances until I get down to what I'm going to call a base case, and when I hit that base case, I know exactly how to solve the problem, right? In the case of the Cat in the Hat Comes Back, it's because I'm using the Voom. All right. How do we actually write the sum of two function in Python now? Well. Here we go, we have def sum_up_to of n. So watta we do? Well, the first thing, is we know how to solve the problem in the base case. So let's do that first. That's easy right? So if n is 1, and let's comment that, this is the base case. Well, I return one. I know how to do that. Okay, else. Everything else is more complicated. Okay, I'm not just going to return the answer directly. Now, we know that we're going to be in the recursive case. And, I actually know how to solve this, because I've already, thought it through, okay. So if I have compute, told you what the base case and the recursive case is, I just need to figure out how to program them. Well, in this case it's actually pretty easy, right? It's n plus the sum_up_to n minus 1. Okay? And this is where a lot of people get tripped up. They don't like the fact that sum of two isn't written yet, and they start bending their brain around the fact that, well, how do I do that? How can I call something that isn't written yet? I'm going to just say, stop. Don't think that way. All right. You need the following function. You need a function that computes the sum of the numbers from n minus 1 down to 1. What is that function called? Well, that's the function I'm writing right now. It's called sum_up_to. So forget about the fact that it's not done yet. When it is done, it's going to do exactly what you want, so just go ahead and call it. All right? And don't try to think about how it's going to do it. Just assume, hey, assume you're writing it correctly. If you wrote the base case and the recursive cases correctly. When you call that function, it will do the right thing and you don't have to worry about how it does it, right? And I think that's the biggest pitfall that a lot of students fall into. They say oh, I haven't written it yet, I don't know what it's going to do. I don't know how to think about it. No. You know what you were trying to make it do, so assume that it's going to do exactly that. All right? Now, let's test this and see if it actually works. So, let's print sum_up_to_1. I know what that should do. Print sum_up_to_2. I know what that should do. Print sum_up_to_10. Okay, what just happened there? Now, [COUGH] let's also try to print sum_up_to, some big number, 55. Let's run it. Okay, all right, sum_up_ to_1, gives me 1, sum_up_to_2, obviously gives me 3, sum_up_to_10, 55, sounds right to me. Okay, sum_up_to_55, 1540. Well, how can I check that? Let's check it. All right? I'm going to find another way to print the sum of those numbers. Well, let's use range. Okay and let's go range 56. That's actually summing up the numbers from 0 to 55, but I'm pretty sure that adding in a zero isn't going to change the answer. All right, so let's run that. Make sure my sum_up_to function is doing the right thing. Hey, it is. Okay, so that probably just exposed two things, right, so the first is that it's idiotic to run a sum_up_to function, I could just do sum of range, all right. Fine. I'm not using sum_up_to as some marvelous function that you should go off and say, start telling your friends that you know how to write. It's the point, is to demonstrate a very simple function, recursive function so we can introduce recursion easily, right? But, the point here is, that it actually worked. When I summed the range, I get the same answer as sum_up_to, I have the correct answer, and my function does work, even though there's this funky call to itself. In the middle of it. All right, let's try a more complicated recursive function. Let's write a function that checks if, a string is a palindrome, so it's let's call it a word. Okay, so I'm trying to figure out, is this word a palindrome. What is the base case here? Hm. Let's think about it. What do you know, what length word do you know is definitely a palindrome? Right. If the length of the word is only one, it must be a palindrome. If the length is zero, it also must be a palindrome. So, if len word. Less than two, return true. It's definitely a palindrome, other wise, what do I actually have to check here to see if it's a palindrome? Okay, we're now in the recursive case. I should have labeled this base case. And this the recursive case. Well, probably the first instinct you have is to write some loop and go through it. But I don't need to do that, okay? I can check if something is a palindrome very simply by saying are the first and last letters a palindrome? Or are the same, rather. Sorry [LAUGH]. Okay, if the first and last letters are the same, and everything in the middle is a palindrome. Then the whole word is a palindrome. First and last letters are not the same, then it's not a palindrome. Okay, so if word[0] is not equal to word[minus 1], return false, okay? Otherwise, let's check. So, let's put an else in here. Okay? Return is_palindrome of something smaller, remember now, right? I have to, make sure that I'm always reducing the size of the problem or it's never going to complete. But otherwise, return is_palindrome of the letters in the middle. Okay. I now have, a complete function is_palindrome. And I didn't have to write any loops. I didn't actually even have to think about it all that hard. Okay. So let's test it. Print is_palindrome a. Okay, print is_palindrome. AA. Print is_palindrome is print is_palindrome. Hm, what's a palindrome? I need a palindrome. Madam, I am Adam. Right? Let's try that out [COUGH]. True, true, false, true. So A is a palindrome, AA is a palindrome, is, is not a palindrome, madam I am Adam is a palindrome. Let's just put another, abcdedcba. That should be a palindrome and let's mess it up by putting an F right there. 'Kay. Make sure longer things actually work. And they do. All right, I want you to think carefully about this kids. I don't want you to just say, oh yeah, yeah, yeah I understand. He checked if it was a palindrome. I want you to look at that code, I want you to play with that code and I want you to think about that code and make sure you understand it. Recursion is an extremely powerful concept and hopefully it makes sense after watching this video. Now I have no delusions here. It's also very complicated to understand all of the nuances that are going on. Right? Which is why I want you to follow the approach that I've given you. 'Kay. I want you to take problems and I want you to very clearly think about what are the base cases and what are the recursive cases. Think about what are the instances of this problem that I know how to solve easily and directly. And there might be more than one of them even though that wasn't the case in the examples in the video. Right? Those become the base cases. Then, you look at the more complicated cases that you don't know how to solve and you say, how do I break these down into smaller pieces? And once you've done that, then you solve them using the function that you're writing itself, okay. And you don't need to worry about whether or not that function works. You should just assume it's going to work and then you take the results and you combine them in whatever way is appropriate and now you've solved the recursive cases. Okay, now the big gotcha here that students often f, fall, you know, fall into it, is that they start to think about what actually happens in that recursive call? Okay, and if you start thinking about that, it gets very complicated very quickly, and it's easy to confuse yourself. Forget [LAUGH] about it, okay. Just assume that the function works, all right. So, this is how I want you to approach writing recursive functions. I want you to think about, what are the base cases? What are the recursive cases? And then you can sit down and start to think about how to write the function. You probably should also think about The Cat in the Hat too.
