0:56

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.

Â 1:50

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.

Â 3:02

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.

Â 5:21

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.

Â 5:50

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.

Â 6:29

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.

Â 7:56

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.

Â 8:37

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.

Â 10:32

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.

Â