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.