[MUSIC] 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 see, it looks like eight strings, and we can run it for 4. 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. 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. 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. 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. All right, let's take a look at some quick notes that I put together on recurrences. So a recurrence is a set of equations that describe the value of a function recursively in terms of itself. typically, you have a set of equations that describe the base case for the occurrence. Maybe gives you the value for 0, or the value for 1 in this case. 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. 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. 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. 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. 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. 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. 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. 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. Here's a table, these are kind of the common recurrences that we'll see in this class. And in fact, they'll probably stand you in good stead through almost all of your career in computer science. For example, here's the recurrence that we derived for binary numbers. F of n is equal to 2 times f of n minus 1. Here n was the length of the binary number. 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. 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. So let's finish things off and I'll show you a piece of Python code that let's you experiment with this. 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. 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. But the key thing again is it captures the growth of the function. So, that's kind of a quick introduction recurrences you might just play around with this code, and it will give you more of a hands on feel on how recurrences behave. Thanks.
