In the last video, we drew some pretty 
pictures of triangles and squares. 
In this video we're going to, look at 
some pretty pictures too. 
We're actually what we're going to do is 
we're going to look at some of the math 
or, or very simple function. 
It's not math. 
It's a very simple function. 
Behind a pretty picture. 
There's this thing called the [INAUDIBLE] 
conjecture, and it's about a sequence of 
numbers that work like this; if the 
current number is even, then the next 
number is n over two, if the current 
number is odd, then the next number is 3n 
plus one. 
And what I've done here is, using the 
recipe for generative recursion, I've 
designed a ISL function for hailstones. 
That's what this sequence is historically 
called. 
Which basically says, look, when we get 
to one, we stop. 
So if n is 1, we produce the list 1. 
Otherwise, we cons n onto the next call, 
which is if n is even, we call ourselves 
recursively with n over 2. 
And if n is not even, in other words, if 
n is odd, we call ourselves recursively 
with plus 1 and n times 3, which is 
exactly this rule up here. 
So there's hailstones, and the reason 
it's called hailstones is that if you 
compute the sequence for very, for a 
number of values, I'll just do it for 10 
now... 
Now if you compute the sequence for a 
number of different starting values and 
then you measure the length of the 
sequence and you plot that, you get a 
picture kind of like that. 
Let's talk about something else for a 
second. 
Look at Hailstones. 
Hailstones is a recursive function that 
calls itself with either n divided by 2 
or n times 3 plus 1. 
Let's compare Hailstones to the 
Sierpinski's Triangle function. 
As tried, the Sierpinski Triangle 
function Is a recursive function that 
calls itself recursively, with s over 2. 
Now if you think back a bit, when you 
first saw recursive functions, I think 
you probably got a bit concerned. 
Hey is this ever going to stop? 
This function is calling itself. 
Why will it stop? 
And then I convinced you not to worry 
about that. 
Because we've talked about the notion of 
a well-formed self-referential type 
comment, it had a base case and a 
self-reference case and having resistance 
of the base case meant that recursive 
functions operating on this kind of data 
would always stop. 
And the reason they would always stop is 
that if it wasn't the base case, they 
were going to take a subpiece of the 
current data. 
And by taking subpieces of the current 
data, in the case of lists, by taking the 
rest of the list each time, they would 
eventually reach the base case, again, in 
the case of lists emptied. 
And so that's why we were happy with 
those recursive functions and we knew 
they would stop. 
What about these recursive functions? 
They're not operating on a well formed 
self referential data definition. 
So that previous proof that they would 
stop doesn't apply anymore. 
What we need for these functions is a 
three part termination argument. 
Let me show you what I mean. 
I'm still in termination starter. 
And the problem here is to do a three 
part termination for s-try. 
Okay? 
Now what I'm going to do actually is I'm 
going to pick this up. 
And take it over to fractals view one I 
want to put the termination argument 
right there. 
We'll paste it in right here to fractals 
v one and. 
I'll get rid of just the description of 
it. 
I'll pull just that part. 
So now, this is going to be the 
three-part termination argument. 
The first part of a termination argument 
is the base case: When does the function 
stop? 
You can usually pick these right out of 
Of the definition of the function. 
It stops there. 
The next part of the argument is the 
reduction step. 
What is the argument to the function in 
the recursive call? 
What is the thing which the template 
calls the next problem? 
Well, again, that's usually pretty easy 
to pick out of the function definition. 
In this case, it's S over two. 
And then there's the argument that 
repeated application of the reduction 
step will eventually reach the base case. 
What that means is that if I start with a 
legal s [INAUDIBLE] and I keep doing the 
reduction step over and over again, I 
will get to the cutoff. 
And in this case that's fairly straight 
forward, as long as the cutoff is greater 
than 0, and S starts greater than or 
equal to 0. 
Repeated division by 2 will eventually be 
less than the cutoff. 
I promised we wouldn't do much math in 
this course. 
I'm still keeping my promise but I'm 
getting a little bit close to it. 
But, I think that even people who don't 
love math will agree that if you keep 
dividing a number by two over and over 
and over again, that number is eventually 
going to get right up to an approaching 
zero. 
And so, as long as the cut off is bigger 
than zero you'll eventually get to be 
less than the cutoff. 
The point of the three part termination 
argument isn't to talk about how fast 
you're going to get there, it's just to 
prove that you will eventually get there. 
So with these three part termination 
argument, which you should always include 
when you use generative recursion, we now 
know that stri will stop. 
Let's do another one. 
And this one is so simple that you might 
find it too simple, but I want to do it 
because as soon as I do this one, then 
I'm going to do a trickier one. 
I'm going to go back to fractals v1, and 
I'm going to do the three part 
termination argument for the carpet. 
Okay? 
And in fact, what I want to do, Is let 
you do the three part termination 
argument for the carpet, okay? 
So there is the carpet. 
You want the base case, the reduction 
step, and the argument that repeated 
application of reduction step will 
eventually reach the base case. 
This is going to be almost exactly like 
the one we just did. 
I'm aware of that but please do it 
anyway. 
Okay, now here is my answer to the three 
part termination argument for the carpet. 
Base case is, again, is s less than 
cutoff. 
The reduction step is divide s by three, 
and the argument again is as long as 
cutoff is greater than zero, and s Starts 
greater than or equal to zero, repeated 
division by 3, will eventually reach base 
case. 
Great, there we go. 
That's two three-part termination 
arguments. 
Seems pretty easy, right? 
Let's go back over here to termination 
starter, and do the three-part 
termination argument for hailstones. 
What I'll do is I'll bring it up to right 
next to hailstones function. 
What's the three part termination 
argument for hailstones? 
Well let's see the base case is that n is 
one, and the reduction step is, what's 
the reduction step? 
Well it's right here, in this case I 
can't quite pull it directly out of the 
code, but it's if N is even, then N over 
2. 
If N, if N is odd, then Plus one times n 
three. 
That's the reduction step so now we need 
to argue that the repeated application of 
reduction step will eventually reach the 
base case. 
Well. 
You know, this first line looks pretty 
good, n keeps getting smaller. 
And if I'm going to argue that n reaches 
1, n getting smaller all the time is good 
news. 
But on this next line, n gets bigger. 
It multiplies by 3 and adds 1. 
Hm, this could be hard. 
And in fact, this is hard. 
It's extremely hard. 
It's so extremely hard that the 
mathematicians haven't been able to prove 
it yet. 
And they've been trying for years. 
And that's despite the fact that no one 
has ever been able to find a 
counterexample. 
No one's ever been able to find a number 
n such that if you do the hailstones 
sequence on it. 
You don't reach one. 
Every number n that they've tried, always 
reaches one. 
But no one has approved that every number 
n will always reach one. 
The reason I'm showing you this trick 
problem is to show you the importance of 
termination arguments. 
The 2 termination arguments we did over 
here in fractals were so simple, that you 
might have thought termination arguments 
are always simple. 
And they're not always simple. 
They're both essential because when you 
have generative recursion, we don't know 
whether these functions are going to stop 
without a termination argument. 
So they're essential. 
And while they're sometimes quite simple, 
like they are in the triangle in the 
carpet, even simple functions like hail 
stones can sometimes have termination 
arguments that are so hard that they're 
not possible. 
Now this is a bit of an extreme case. 
In the functions that you are going to 
write, you are unlikely to encounter 
termination arguments that are impossible 
to prove. 
I'm just showing you this example as a 
way of helping you see that the 
termination argument can be hard and is 
worth doing. 
Usually termination arguments are 
going to be quite possible, and they're 
often going to be a little bit harder 
than the ones in fractals. 
And we'll see some of those in the 
remainder of this material on gendered 
recursion.