In this video, we're going to draw some 
pretty pictures. 
Or I guess they're pretty pictures of a 
certain kind. 
Some people call them math art. 
We're going to look at fractals and 
fractals are images where the image 
itself has a recursive structure. 
The fractals we're going to do are quite 
simple and, and so they're not going to 
be too elaborate or too gorgeous. 
But if you do a Google search, you can 
find a bunch of other fractals. 
And after you work on these, you can try 
some more elaborate ones of your own. 
I'm in fractals-starter.rkt. 
The problem that I'm given here is to 
design a function that consumes a number 
and produces a Sierpinski triangle of 
that size. 
And it says that function should use 
generative recursion. 
And it talks a little bit about how to 
draw a Sierpinksi triangle. 
You start with an equilateral triangle of 
a given side length, s. 
And then inside that triangle are three 
more triangles. 
And then inside of those are three more 
triangles, and so on, and so on. 
In the end you end up with something that 
looks like that. 
So even without knowing quite what 
generative recursion is yet, I think we 
can see that this clearly has a recursive 
structure. 
You draw a triangle. 
Inside it there's three more. 
Inside each of those there's three more. 
And eventually you have to stop. 
So what I'm going to do is I'm going to 
follow the generative recursion recipe 
here. 
And then talk a little bit at the end 
about why that recipe works the way it 
does. 
So, the first thing I'm going to do is do 
just a little bit of domain analysis. 
Let's see. 
If this triangle, this outer triangle has 
a side length of S, then that means each 
of these sub triangles have a side length 
of S over 2. 
And that's kind of the end of the domain 
analysis really. 
And I just have to keep making them until 
they get somehow small enough. 
So, let's see. 
Let's start following the for the HCDF 
recipe for generative recursion, which is 
like the HCDF recipe but just a little 
bit different with regard to the 
template. 
And it requires an additional step at the 
end. 
We're going to consume a number, which is 
a side length, and we're going to produce 
an image. 
And it's just produce a Sierpinski 
Triangle of size s, or of the given size. 
[SOUND] Let's do a Stub, we'll call it 
stri s and it's gotta produce some image. 
So we'll do that familiar blank image 
that we've done before, square, zero, 
solid white. 
Now let's do some check expects. 
Now we don't have the recipe for 
generative recursion mastered yet. 
But I can tell you right away, that one 
element of it is to do the base case test 
first. 
That's going to be in common with the 
kinds of recursion, functions we've 
already been designing. 
So what's the base case, in a function 
like this. 
Well, the base case in this function is 
that we're asked to produce a triangle 
that's so small that we're not going to 
recurse anymore. 
We've gotten to the smallest size 
triangle that we're going to make. 
And I don't know what that is, but 
clearly that's going be kind of an 
interesting number. 
So, you know, I'm going to give it a name 
as a constant. 
[SOUND] I'll call it cutoff. 
And, I don't know, we'll just say 2. 
2 seems pretty small. 
You might end up not being right in the 
sense that it won't look quite right, but 
since it's a constant, we'll be good to 
go. 
So what that means is if I'm asked to 
draw a Sierpinski Triangle of that size, 
of the cutoff size, 5, then there won't 
be any recursion involved at all. 
I'll just produce a triangle of the cut 
off sides, that is of outline form and is 
red. 
And here, I'm going to use a trick that I 
haven't shown you in a while. 
which is, when I'm doing check-expects 
for graphical things and I kind of want 
to make sure my check-expects are right 
in the sense that the images actually are 
looking the way I want them to look. 
A great thing to do at this point is to 
run it. 
And the task will fail but I can actually 
kind of see what the test was supposed to 
be. 
And, of course, that's very, very hard to 
see but you know, there is a triangle 
there. 
Let's do another one. 
Our domain analysis says that the next 
biggest size of triangle in some sense is 
cutoff times 2. 
Of course, it could be not exactly a 
multiple of cutoff, but just to make my 
check-expect simple, let's do that case. 
Let's say check-expect Sierpinski 
Triangle times cutoff 2. 
And what's that going to be? 
That's going to be a big triangle, of 
that size with three little triangles in 
it. 
So there's going to be some kind of, 
we're going to take that triangle, the 
big one and we're going to put three 
little triangles in it. 
And now, let's make the three little 
triangles. 
Well, each of the three little triangles 
is the same. 
So let me just make one of them using 
local. 
I'll avoid redundant computation here. 
And there's recursion going on here so 
this a good place to avoid redundant 
computation. 
I'll say let's define something which 
I'll just call sub, for the sub triangle. 
And then what's this going to be? 
Well, this is just a Sierpinski triangle 
of size cutoff, because if I take times 
cutoff 2 and divide it by 2, that's 
cutoff. 
And I know that a Sierpinski triangle of 
size cutoff is just a triangle, so this 
is really just going to be this thing 
here. 
And now, I've got one of them and I need 
to arrange the three of them. 
There's kind of two on the bottom and one 
on the top. 
And I can do that this way by staying 
above the one on the top. 
And then the side, so this is the bottom 
row. 
That's the bottom row and that's the top 
row, and if I want to be silly, I could 
do that. 
Just accentuate the way it's going to be. 
That's kind of what a Sierpinski triangle 
of size times 2 cutoff is supposed to be. 
Let's run that and see what it looks 
like. 
And here we're starting kind of to be 
able to see it's sort of maybe a little 
bit. 
You know what I could do? 
Great thing about having done this as a 
cut off, and great thing about having 
used cut off in all my check expects, I 
just temporarily make this 20. 
Which is of course going to be much too 
big for real good looking Sierpinski 
triangles, but it'll help me see what my 
tests are doing. 
Oh yeah, that looks like a base case and 
that looks like a case that's kind of a 
little bit bigger than a base case. 
Hm, that's looking pretty good. 
Let me go ahead and make this 2 again. 
Now, I've got the examples. 
Let's try to code this thing up. 
[SOUND] Well, what I'm going to do now is 
to get the template for generative 
recursion. 
And where I'm going to get the template 
for generative recursion is I'm going to 
go to the course website. 
So I go over to the Coursera website. 
I go over to the Design Recipes page and 
I follow the Generative Recursion link. 
And here is the template for generative 
recursion. 
I'm just going to copy it, and bring it 
back over to DrRacket. 
Now, I'm pasting the template. 
This, of course, is the stub. 
[BLANK_AUDIO] At this point in the 
course, we don't leave stubs around, but 
I'm leaving this stub around just because 
this is the first time we've done 
generative recursion. 
This is the template. 
I'll make two copies of it, just so we 
can talk about it. 
[SOUND] So this is the template. 
Now, let me get going. 
I've got to rename the template because 
the function that I want to design is 
called stri. 
So I rename the template. 
I rename its recursive call. 
And I've been using s for this perimeter 
because its the side length. 
So I'm going to go ahead and do that 
everywhere within this function as well. 
And now, I've got this template. 
I've got some check-expects. 
What does this template mean? 
Well, the way to read this template is 
this question, if trivial question mark 
s. 
Another way to read that question is it's 
the same thing as saying, are we in the 
base case? 
The reason we call it trivial in this 
template is this is the problem that's so 
simple that we're not going to have to do 
any recursion. 
So when is a Sierpinski triangle, so 
simple that we won't have to do any 
recursion? 
Well, it's when the size reaches cutoff. 
That's sort of what we decided is cutoff 
was the smallest one we were going to do. 
So I'm going to change trivial here to be 
less than or equal to s to cutoff. 
I could have made it less than. 
Now that's just a detail in how we do 
this particular function. 
But I'm saying less than or equal s to 
cutoff. 
And now trivial answer in the template is 
telling me hey what you need to fill in 
here is what you're going to do if 
there's not going to be any more 
recursion. 
Well, I know what I'm going to do if 
there's not anymore recursion. 
I'm just going to make a triangle of that 
size. 
Okay? 
I'm just going to say triangle s outline 
red. 
Okay? 
That's the trivial answer. 
So the trivial question is we've reached 
the trivial case if s is less than or 
equal to cutoff. 
And in that case we make a triangle of 
size s. 
Notice I'm making a triangle of size s 
here. 
I'm not making a triangle of size cutoff. 
The reason I'm doing that is this less 
than or equal to means that s might be 
smaller than cutoff. 
Okay? 
It's just, at least it's smallest cutoff 
so that's this is an s here rather than 
cutoff. 
So then, what do I do in the recursive 
case? 
Well, you know, it's kind of right here. 
Okay? 
I'm going to overlay a triangle of 
current size [SOUND] that's outline in 
red. 
With what? 
Well, here is the recursion in the 
template, so I'm going to build around 
that. 
And what my example tells me is, only do 
the recursion once. 
Don't do it three times. 
So I'll say, local, define sub. 
I'm just giving a name for the recursion. 
There's the recursion. 
And now what's this next problem thing? 
Well, next problem is the piece of the 
template that tells me, hey. 
You better not make the recursive call be 
with S. 
If you make the recursive call be with S, 
we've got a problem, because this is 
going to happen forever. 
You've gotta somehow reduce S. 
And in this case, the way we reduce S, we 
make a smaller triangle, and each time, 
we make a triangle that's half as big. 
That's what came from our domain 
analysis. 
So we make that triangle. 
I'm getting this from the examples. 
And then what do we do? 
Well, we do the thing that is in our 
check-expects. 
We do above, beside. 
Let's try it. 
Hey, the test passed. 
Let's try a bigger one. 
What I'll do is, I'll make the 
interactions area bigger, by doing a 
Command+D. 
I'll say stri of 100 and that's a bigger 
one. 
Let's see stri of 200 is even bigger. 
There you go. 
You could make them even bigger. 
Command D to get me back to the code. 
You can see the problem I'm about to give 
you, but let me talk about this for just 
a second. 
Look, what did we do? 
We were asked to draw an image that 
looked like that. 
We did a little domain analysis, we 
realized oh, first you make a triangle 
and then you make three triangles that 
are each half as big. 
And then [INAUDIBLE] each of those you do 
it again and again and again, until the 
triangle gets too small. 
That's cutoff. 
Then we followed HTDF. 
Good old-fashioned HTDF pretty much. 
We did a signature. 
We did a purpose. 
We did some examples. 
We did a stub to support the examples. 
Then there was one difference here, which 
we used this new template. 
This template for generative recursion. 
And in this template, there were three 
key pieces we had to fill in. 
The trivial predicate, which meant hey 
we've reached the end of the recursion, 
the trivial answer, which is what we do 
at the end of the recursion. 
In the terminology we used, for 
structural recursion, this was the base 
case test and this was the base case 
result. 
And then, we did the non-base case where 
we do something with the current value d, 
and we call ourselves recursively with 
some next problem. 
And that's how this ended up looking. 
It ended up looking just like this. 
So that's kind of neat, that's kind of 
fun. 
What I want you to do now is to do the 
second problem in this starter file, 
which is to design a function to produce 
a Sierpinski carpet of size S. 
And here's an example of a large 
Sierpinski carpet. 
And let me just observe one thing for you 
that will help. 
The idea is you make a square and inside 
of that square you rut eight copies of a 
recursive call. 
Those sit all around the edge, one, two, 
three, four, five, six, seven, eight. 
And right in the middle you just put a 
blank square of that size. 
So it's almost the same structure as the 
triangle. 
The key inside you need is going to be 
eight copies of the recursive call to s 
carpet and a blank square in the middle. 
Why don't you do that and we'll talk when 
you're done. 
What I'm going to do now is just quickly 
go through the design of the s carpet 
function. 
Let's see. 
We can assume a number will produce an 
image. 
[SOUND] Now, let's see. 
We start with the base case or because 
it's a general recursion function. 
Perhaps I should say the trivial case, 
which is that we're making a very small 
carpet. 
I just used the same cutoff constant as 
before. 
Maybe I could've done a different one. 
Or I'll just use the same one. 
If we reached out size, then the result 
is just a square of that size, that's an 
outline and red. 
I could also perhaps have made a constant 
for the color. 
I didn't do that. 
Now lets do one that's a bit bigger. 
Now it doesn't have to be times cutoff 3. 
I'm just making it times cut off 3 to 
keep the math simple. 
Because of course each of the inner 
squares is one third the side length of 
the outer square. 
So that keeps it a bit simpler for me. 
If I'm doing that carpet then let's see. 
It's an overlay. 
It's an overlay of a square of that full 
size, with what? 
[SOUND] With well I need some inner 
squares and I'm going to need the same 
square repeated time, so I'll do that 
local thing again. 
I'll call the one that's actually carpet. 
I'll call that one sub. 
And what is that we're going to be in 
this case? 
Well, it's going to be a carpet of size 
cutoff because times cutoff 3 divided by 
3 is cutoff. 
So that's a square of size cutoff outline 
in red. 
Remember, we're doing the cases just one 
bigger, there's just going to be one 
recursion here. 
And, we also need that blank one in the 
middle. 
That's just doesn't have any color to it, 
that's just a square-sized cutoff. 
But it's, this doesn't have to be solid. 
The key thing is, it has to be white. 
So now I've got those two. 
I've got the outer square, I've got the 
makings of the nine inner squares. 
Now, I just have to put the nine inner 
squares together above the, the side. 
Sub, sub, sub, beside sub blank. 
So now you see why I used a 3 letter name 
for a blank. 
Right. 
There's a method to my madness, beside 
blk blk blk. 
That's all of that. 
[NOISE] Run it to see if it's well 
formed. 
It is. 
I can't really see it. 
Let's do that same trick I did before of 
temporarily making cutoff much bigger. 
Running it again. 
I'm looking at my failing test. 
But seeing if the expected values look 
hm, that doesn't look very good at all. 
What happened there? 
That's not what I wanted. 
Oh, I put nothing but blank on the bottom 
row. 
Silly me. 
The bottom row has to be sub, sub, sub. 
Let's see what they look like now. 
Oh yeah that looks much better. 
It's not the full carpet because it's 
just one level of recursion, but it's a 
good start. 
Okay. 
Now I go get the template for generative 
recursion. 
There it is. 
I copy it. 
I bring it over to here. 
I paste it in. 
I comment out the stub. 
I rename the template function. 
I rename the recursive call. 
And I like the parameter s for this 
because it's the side length. 
So I've got fix all of those. 
Now I've got to decide some of these 
other things. 
Let's see. 
What is the trivial case? 
What's the case where there's no more 
recursion or, in our old terminology, 
what's the base case. 
Well, that's the same as it was for the 
triangle, it's just less than or equal to 
ask for the cutoff. 
What's the trivial answer. 
Well the trivial answer was, we just make 
a square of this size. 
And what's the nontrivial answer. 
Well, we're going to overlay, a square of 
this size [SOUND] with, what? 
Well we're going to do this local thing 
so that we don't make the recursive call 
eight times. 
[SOUND] There's the recursive call from 
the template, but we have to decide what 
the next problem is. 
Well, next problem is s divided by 3, 
because each inner squared is one third 
the side length. 
[SOUND] We also need blk [SOUND] and it's 
above, let me try to get it right this 
time. 
Beside sub sub sub [SOUND]. 
Beside, beside sub blk sub, beside sub 
sub sub. 
Your mat just passed and let's try a big 
one. 
Hmm, that doesn't look quite right. 
Why doesn't it look that right? 
It doesn't look rich enough. 
Oh, I know what's wrong. 
[SOUND] forgot to change cutoff back to 
2. 
So there's not many levels of recursion. 
[BLANK_AUDIO] Let's try it again. 
[SOUND] [BLANK_AUDIO] This is taking 
longer. 
Yeah, that looks a lot better. 
So there you go, that's my version of the 
Sierpinski triangle, and the Sierpinski 
carpet. 
If your version of the carpet came up 
significantly different than that or even 
different, be sure to compare my version 
to your version, and be sure that you, 
your version really only differs in 
details. 
The version really still has to have the 
same recursive structure based on this 
template. 
And then in the next video we'll talk 
about the last piece of the recipe for 
generative recursion.