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.

Â