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.