0:15

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.

Â 0:47

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.

Â 1:49

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.

Â 2:16

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.

Â 3:02

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?

Â 3:18

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,

Â 3:52

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.

Â 4:14

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.

Â 4:52

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.

Â 7:07

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?

Â 7:27

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.

Â 8:59

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?

Â 9:51

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?

Â 10:29

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?

Â 11:01

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.

Â 13:04

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.

Â 13:28

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.

Â