[MUSIC] Well, welcome to class. You've been thinking about how recursion works. For some students this is really a challenge to understand how your recursive Python program is actually evaluated. In this lecture, we're going to use a tool that you should be familiar with this mode to walk through a few examples that illustrate how a recursive program is evaluated. Let's get to it. Okay, let's look at a couple of examples of recursive functions and see if we can understand how they're evaluated inside Python. So the first example we're going to look at this function collatz and I've written this function to help us understand the behavior of the collatz conjecture. The conjecture says that we start with any positive integer n and we perform the following task to it, we'll arrive at 1. And what is that task? It says take the number, if it's even, divide by 2. If the number is odd, multiply by 3 and add 1 and so the conjecture is we'll always arrive at 1 at some point. Our function collatz designed to count the number of times we have to apply this iteration. The code is fairly straight forward if the number is 1 we just return back the number of iterations which we initialized to 0. If the number is even we just divide by 2 and increment the number of iterations. If the number is odd we multiply by 3 add 1 and increment the number of iterations. By the way this parameter you will see here that's actually provided to our recursive function is called an accumulator. So, when some kinds of recursive programs were actually accumulating in answers we compute. So, let's do an example here. Let's compute collats of 5, 0. So, let's do it in our head first just to see if we can kind of figure what the answer should be. So, 5 is odd so we multiply by 3 and add 1 that gives us 16, that's one iteration. 16 is even we divide by 2 that's 8, that's the second iteration. 8 is even we divide by 2 we get 4, that's the third iteration. 4 is even we divide by 2 we get 2, that's the fourth iteration. 2 is even, we divide by 2 we get 1, that's the fifth iteration. So we should return back 5 when we run the function. So let's do that and sure enough, we came up with 5. Now that may have been a little complicated and maybe you didn't have a great mental model in your mind for what happened. But we have a tool that will help us understand how this recursive function is evaluated. Vis mode, so next let's go back and just run this in Vis mode and see if we can kind of follow what I just talked about inside Vis mode. Okay, let's do the same example now but we're going to use a tool that we have at our disposal for understanding how Python evaluates functions. That's Vis mode, so you should have seen Vis mode on introduction interactive programming in Python. The way you fire it up is you click on this wrench icon and we just hit run. And what we've done now is we've run this Python program, we, we built up a trace of this execution that we can navigate through to understand how this code was executed. So, right now we're at the end of the program we show that the state venn diagram says that we're basically finished. You can see our output 5 here if we want to go to the front of our trace we click here. And now we can navigate forward to the trace by simply clicking this bottom which simply moves forward one statement at a time in the trace of the program. So the first thing is we define the function collatz and now what we're going to do is evaluate collatz of 5, 0. So to def, we move forward and what we've done is we've called collatz with number 5 and count being 0. So let's keep tracing it. Number is not even it's actually odd so we jump down here and now we're going to need to compute collatz of 16, 1. So we'll keep stepping forward now we see we have collatz of 16, 1. 16 is even so we need now to compute collatz of 8, 2 and in fact you can go all the way to the base case at line 14 by just putting a break point in and now clicking forward. And what you can see is we actually have the sequence of calls to collatz that are all taking place at the same time. In fact, this is called a call stack because these calls are placed in a stack. The top of the stack is down here 5, 1 this is the current call that we're evaluating. When we get the values back from this we're going to use those values in the other previous calls to collatz. So inside Python, all those calls that are currently waiting to be evaluated are actually stored in a stack just from the stacks in queue. So, the critical thing here is when we get to this base case there's no more recursion to take place. We can actually return back the value, in this case the value is 1. So, if we move forward 1 statement we see that return back 5, now if you go forward 1 more statement. What we see is, now we've taken value 5 and returned it back to the previous call, which was for 2, 4. We do that, return back that value to the previous call, 4, 3. Turn that back, we go back to the call 8, 2. We take that back, we go back to 16, 1. Finally we go back, to the call 5, 0 that got us all started. And then finally, we print out 5. So we've seen as when we're evaluating recursive functions, there's typically a sequence of recursive calls that are waiting to be evaluated. And Python automatically measures that for you kind of keeps tracking your work waiting for you to do some extra evaluation of the function maybe recursively or another function. So it does that book keeping for you. So using this mode will help you kind of keep track of what's going on behind the scenes as you're evaluating recursive functions. All right, let's look at a second example of a recursive function. Now, our first example was fairly mathematical. Our second example is of practical importance. It's a method for sorting a list of numbers it's called quicksort. It has the property that there are n numbers in the list its running time is almost always in log(n). Quicksort has a very simple and elegant description using recursion and the way it works as follows. You say, if the list is empty we'll just turn back the empty list, empty list is sorted. If the list is not empty take the first element in the list and we're going to call that the pivot. And the critical step here is we're going to cut this list of numbers into three separate lists. One list is going to be all the numbers that were less than the pivot. The next list is going to be the list of all the numbers that are equal to the pivot. And the last one is all the numbers which are greater than the pivot. So notice that the list comprehensions in statements 33, 34, and 35 do that by doing three linear sweeps along the list. So it takes all that work to execute lines 33, 34 and 35. Now, how do we actually take advantage of recursion? Well its pretty straight forward. We're going to use return back the following take that list of lesser numbers and we quicksort. Get a sort a list of numbers that was the result. We concatenate then to all the numbers equal to the pivot. And finally we quicksort all the numbers that are greater than the pivot which is a sorted list which concatenate that on the end. The result is the original list of numbers in sorted of order. So in fact if you run it here we can see the list 4, 5, 3, 1 it comes out is 1, 3, 4, 5. Now, if you don't understand recursion that seems a little magical. So let's go through to finish off the lecture and use Vis mode to understand how Python actually evaluated this recursive function. All right, let's look at this example inside Vis mode. So I'm going to fire it up and hit run. And we see the sorted list 1, 3, 4, 5 and let's go to the beginning of our trace, and step through it. Now, to avoid having to go statement by statement I'm going to put a break point in at line 36. So we're just going to step forward to every time line 36 is executed during the trace. So if I go forward, what we can see is the first call to quicksort takes me to list 4, 5, 3, 1 and the nice thing we see is that the pivot is fourth the first on the list. The list lesser corresponds to 3 and 1 notice that it's not in a certain order it just keeps the order that we had inside the list. The pivots are just 4 and then the things that are greater are 5. So, now we go through and we execute the slide and we're going to need to go through and perform quicksort on lesser. So let's step forward and if we do that, what we see here is we're now calling quicksort on the list 3, 1, the pivot is 3 we see lesser corresponds to the list containing 1. The pivot has 3, and greater is empty so we now need to go through and do quicksort on lesser. So if we step forward, we can see, yes we're computing quicksort on the list that contains 1 which we do that it's going to give this back. The list that contains 1 so we're turning back the list from quicksort of the list with 1. So we pass that back to the previous recursive called stack and we do that, what we see is the answer that comes out is that we've taken quicksort of 1. We concatenated to 3 we get the list 1, 3 so that's what quicksort is of the list 3, 1. Now if we pass that back to the previous call to quicksort the 1 above it in the stack so hit forward and what we see here is that we've now got the sorted part for lesser. But we still need to go and actually sort the graders so we're now going to sort graders. So we're saying numbers, numbers 5, we step forward, we see that sort of list. Consist of 5, so we pass that back to the previous call, so we actually had 2 recursive calls we had to make. We had to quicksort of the list 3, 1, we had to do a quicksort of the list 5, we've done both of those, we pass that back up. And now we can go through and take those two sort of lists put the list pivots in between and what comes out is the new sorted lists for 4, 5, 3, 1 and so that actually is the final answer. If that was a little too fast for you, here is a simple suggestion simply play around with the different numbers in this list. And step through the evaluation of quicksort in the manner that I just showed. Don't try to step through statement by statement just put a break point here at line 36 on the return. And see if you can predict in your mind how the various calls to quicksort pile up over here in the stack. That's really a good indication whether you understand how your recursive programming is being evaluated or not. I think if you do that you'll gain some intuition to how recursion works. [SOUND]
