0:13

Well, welcome to class.

This week you should have already seen some examples of recursion in action.

We've walked through some example programs that should give

you kind of a first taste of how recursion works.

In this lecture, I'm going to talk about

a specific kind of recursive function, the recurrence.

So recurrence is really kind of a simple fiber recursive function

which we have the values for some base cases already given.

And we express the value of function in terms of, kind of the input parameter,

plus maybe that, same function recursively applied,

to some reduced version of the input parameter.

Recurrences will be useful because it will help us, understand both the

running time, and the size of the output produced by a recursive function.

What we'll simply do is, we'll take a recursive program,

we'll kind of trim it down to build a recurrence.

And then we can just simply, look up the solution to

that recurrence, using a table of recurrences that I'll provide you.

later, when we get a algorithmic thinking, you'll get a

chance to actually see how to solve more general recurrences.

[BLANK_AUDIO]

Let's start off by looking at a recursive function and seeing if

we can analyze the behavior of

that recursive function by building a recurrence.

So here's a function, it takes a length, and creates

a list of all the binary numbers of a particular length.

So these binary numbers are strings that involve 0 or 1.

So let's start off and just run it.

We'll give it a length here, which is 0, and it

produces exactly a list consisting of one string, the empty string.

If we increase that to one, what comes out, we have two strings.

A string consisting of 0 and 1.

Let's make something to 2.

We see four strings here let's run it for 3.

We

2:10

And we get enough strings that we actually

can't see it over here in the console easily.

So one thing we've observed is we increased

the length, the number of strings grows very quickly.

So kind of an obvious question to ask is, how

many strings do we get as a function of length?

So what I'm going to do next is I'm going to

show you how to kind of simplify those function

down in both recurrence that will kind of exactly

capture the number of strings for a given length.

All right, let's see if we can count

the number of binary strings of a particular length.

So let's first just take a quick look at how make_binary works.

So we notice if length is 0, we just return

back a list with a single string, the empty string.

If the length is greater than 0, we call make_binary on length minus 1, we save

that, and then we iterate through everything and all_but_first, two times.

First time through, we basically place a 0 at the start of the string.

The second time, we place a 1 at the start of the string.

We kind of pack that all together into a list answer that we then return.

3:14

So to kind of keep track of the number of strings that we create, what I'm

going to do is I'm just going to build a

simplified version make_binary that I'm going to call binary_length.

What does, what it does is, if the link is 0, it just returns 1.

Remember it returned back the list with a single empty string.

3:29

If it was greater than 0, what it does is it computes binary_length of the length

minus 1, and it observes that the way

make_binary works is just kind of doubles that length.

So it returns 2 times the binary_length.

3:42

So, this function actually should just return,

the number of strings of a particular length.

And in fact we can uncomment this, and, run it.

And you'll see there's a really simple obvious, pattern here.

One, two, four, eight, 16, 32, 64, and so forth,

which you should probably already know just an exponential function.

So what we've got here is we've got, kind of,

more computational proof that somehow things are growing very quickly.

So what I'm going to do now is I'm going to

go through and talk a little more formally about recurrences.

And I kind of show you that when you see

something like this, you can actually just look up

and see hey, you know, if I see recurrence

of this type, I can look up at the answers.

This is going to grow in this case exponentially.

4:49

Then you usually have one equation that relates the value of a

function in terms of its value computed recursively on some smaller value.

Okay?

How do we get a smaller value from n?

We do things like subtract 1 from it or subtract a constant from it.

Or we divide it by 2 or we divide by a constant.

5:08

We could then take that result and maybe combine it with some

other constant or some other expression in, in that's in some closed form.

We could even multiply it by something.

But the critical thing you're going to see here is we typically

describe the recursive behavior of the recurrence in a single equation.

5:24

The value of that is that the number of different kinds

of equations that can arise for most recursive programs is really small.

In fact, we're going to see in a second there's really only

kind of eight that we'll look at in this class entirely.

So, let me do one more example of

where recurrence would arise, in fact where this recurrence

arises, and then we'll go on to figuring out

how to just look up the solutions to recurrences.

5:46

Let's look at another example of a recursive function and we'll

build a recurrence to help understand the behaviour of that recursive function.

So the function is binary_search, you should

have seen this in a previous lecture it

takes an ordered_list and item and checks to see whether that item is in the list.

Now binary_search should be smart.

We shouldn't just iterate through and just test every

item, unless we should take advantage of the ordering.

And the way it works is we check the length of the list.

If it's 1, then we just compare the item to the one element on the list.

Otherwise, we split the list into two equal pieces, and then we check

the item versus, kind of, the item in the middle of the list.

If it's less than, we search the first list.

If it's greater than, we search the second list.

6:30

So, is binary search any good?

Well, the answer is yes.

And so we could kind of build a recurrence to

try to help understand kind of how binary search works.

So let's build a function search_time that estimates the

number of comparisons that we execute during binary search.

Remember comparisons is kind of a good way

for understanding the performance of searching and sorting algorithms.

So I observe that if the length of the list

is 1, then we actually just do one comparison, right here.

6:59

And if the length of the list is greater than 1.

Well let's see, we do one comparison here and then we essentially use, well some

number of comparisons that corresponds to the

search_time on, a list of half the size.

7:13

We can actually run this.

And what we see comes out is that kind of, well, it's what we expect if we have

something where we're doubling the size of the list,

the number of comparisons is going up by one.

This number here is somehow almost the log of this number.

7:29

In general, reducing the behavior of the function here, the number of comparisons

of the simple recurrence, is going to help us in analyzing this particular property.

In fact, what we'll do next is let's go ahead and look at

some of the common recurrences that come up, and we'll see solutions to those.

[SOUND].

All right, it's time for the payoff for this lecture.

So, we've taken our recursive function, we've

built a recurrence that characterizes it's behavior.

And we'd kind of like to know, what's the solution to that recurrence.

Now, by solution I mean some closed form function that we

understand that returns approximately the same values as the recurrence returns.

8:33

The solution to this is, well, let just something that grows exponentially in n.

That's not surprising, every time we increase the length of the

binary number by 1, we double the number of binary numbers.

Here's an example, something that arose from binary search.

F of n is equal to f of n over 2 plus 1.

The solution to that is something that grows essentially at log base 2 of n.

9:00

You don't need to remember this.

You just need to know the tables like this exist.

That if you're curious about how recursive function behaves you can go

through and try to distill it's behavior down into a very simple recurrence.

And then simply look up the solution of that recurrence.

And that solution will give you insight

into the behavior of your recursive function.

9:27

All right.

To finish off lecture, we're going to look at

a fun piece of Python code that I've written,

that, implements a particular recurrence and allows us

to compute the value of that recurrence in Python.

And then we're going to be compare that to the

solution that I've given you on the solution page.

So, here, I have a dictionary with all

the various recurrences that we're going to consider here.

We have a function that, kind of looks up that

particular value in the dictionary and computes the given recurrence.

we, also, have a second dictionary that

has all the solutions from the solutions page.

So what we're going to do is we're going to simply go

through and compute both of these and compare the plots.

So we're going to change this, leave the index

at 0 to start here in the first recurrence

we're going to look at is f of n is equal to f of n minus 1 plus 1.

And that solution is just f of n is equal to n.

So if I run that, what comes out is really straightforward.

It just turns out that the solution of the recurrence

actually agrees what we computed from the recurrence, no difference.

Okay, let's look at one that's a little more interesting.

Let's go down to number 4 here.

So number 4 is what we got out of binary search.

It was f of n is equal to f of n over 2 plus 1.

And remember the close form solution we had was log of the n, base 2.

If I run that, what comes out is, here's kind of log of n, and here's the

values computed by the recurrence, so you see this kind of stair step approach here.

So one interesting thing that happens in the

recurrence is the recurrence is always returning an integer.

11:03

And so what happens if we want to compute, for example, f of n divided by 2?

If n is odd, what do we use?

In the recurrence, we always use the floor of n over 2.

Now in your program for example, in binary search, you might use the ceiling

of n over 2, or you might use the floor of n over 2.

So, the recurrence is going to be a little sloppy here and that kind of is reflected

in which you see here with this kind of stair step approximation of log of n.

But remember we're only trying to get a

very rough estimate of how our recursive function behaves.

Let's finish off with an example from this weeks mini project.

Which is we're going to look at the recurrence f of n

is equal to 2 times f of n over 2 plus n.

And the solution to that recurrence is n times log n.

So if I run that, what I can see here is, that n log n,

it's this nice function that grows just a

little bit faster than linearly, not a lot.

And here's the solution of the recurrence.

And again you can kind of see a little bit of a stair step appearance here.

And this is again due to the fact that whenever

we take n over 2 we always take the floor.