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.