1 00:00:06,380 --> 00:00:08,845 In this video, we're going to draw some pretty pictures. 2 00:00:08,845 --> 00:00:11,600 Or I guess they're pretty pictures of a certain kind. 3 00:00:11,600 --> 00:00:15,763 Some people call them math art. We're going to look at fractals and 4 00:00:15,763 --> 00:00:20,540 fractals are images where the image itself has a recursive structure. 5 00:00:21,800 --> 00:00:25,340 The fractals we're going to do are quite simple and, and so they're not going to 6 00:00:25,340 --> 00:00:29,860 be too elaborate or too gorgeous. But if you do a Google search, you can 7 00:00:29,860 --> 00:00:34,060 find a bunch of other fractals. And after you work on these, you can try 8 00:00:34,060 --> 00:00:39,940 some more elaborate ones of your own. I'm in fractals-starter.rkt. 9 00:00:39,940 --> 00:00:43,530 The problem that I'm given here is to design a function that consumes a number 10 00:00:43,530 --> 00:00:46,430 and produces a Sierpinski triangle of that size. 11 00:00:47,620 --> 00:00:51,669 And it says that function should use generative recursion. 12 00:00:51,669 --> 00:00:54,650 And it talks a little bit about how to draw a Sierpinksi triangle. 13 00:00:54,650 --> 00:00:58,970 You start with an equilateral triangle of a given side length, s. 14 00:01:00,000 --> 00:01:03,040 And then inside that triangle are three more triangles. 15 00:01:03,040 --> 00:01:07,310 And then inside of those are three more triangles, and so on, and so on. 16 00:01:07,310 --> 00:01:10,540 In the end you end up with something that looks like that. 17 00:01:11,650 --> 00:01:15,410 So even without knowing quite what generative recursion is yet, I think we 18 00:01:15,410 --> 00:01:18,840 can see that this clearly has a recursive structure. 19 00:01:18,840 --> 00:01:21,610 You draw a triangle. Inside it there's three more. 20 00:01:21,610 --> 00:01:25,700 Inside each of those there's three more. And eventually you have to stop. 21 00:01:26,820 --> 00:01:30,849 So what I'm going to do is I'm going to follow the generative recursion recipe 22 00:01:30,849 --> 00:01:33,300 here. And then talk a little bit at the end 23 00:01:33,300 --> 00:01:37,580 about why that recipe works the way it does. 24 00:01:37,580 --> 00:01:41,761 So, the first thing I'm going to do is do just a little bit of domain analysis. 25 00:01:41,761 --> 00:01:48,866 Let's see. If this triangle, this outer triangle has 26 00:01:48,866 --> 00:01:56,280 a side length of S, then that means each of these sub triangles have a side length 27 00:01:56,280 --> 00:02:01,910 of S over 2. And that's kind of the end of the domain 28 00:02:01,910 --> 00:02:05,120 analysis really. And I just have to keep making them until 29 00:02:05,120 --> 00:02:08,710 they get somehow small enough. So, let's see. 30 00:02:08,710 --> 00:02:14,260 Let's start following the for the HCDF recipe for generative recursion, which is 31 00:02:14,260 --> 00:02:17,825 like the HCDF recipe but just a little bit different with regard to the 32 00:02:17,825 --> 00:02:22,360 template. And it requires an additional step at the 33 00:02:22,360 --> 00:02:24,200 end. We're going to consume a number, which is 34 00:02:24,200 --> 00:02:26,661 a side length, and we're going to produce an image. 35 00:02:26,661 --> 00:02:44,860 And it's just produce a Sierpinski Triangle of size s, or of the given size. 36 00:02:44,860 --> 00:02:55,740 [SOUND] Let's do a Stub, we'll call it stri s and it's gotta produce some image. 37 00:02:55,740 --> 00:03:02,638 So we'll do that familiar blank image that we've done before, square, zero, 38 00:03:02,638 --> 00:03:09,960 solid white. Now let's do some check expects. 39 00:03:09,960 --> 00:03:15,880 Now we don't have the recipe for generative recursion mastered yet. 40 00:03:15,880 --> 00:03:20,290 But I can tell you right away, that one element of it is to do the base case test 41 00:03:20,290 --> 00:03:23,460 first. That's going to be in common with the 42 00:03:23,460 --> 00:03:26,000 kinds of recursion, functions we've already been designing. 43 00:03:27,630 --> 00:03:30,850 So what's the base case, in a function like this. 44 00:03:30,850 --> 00:03:36,320 Well, the base case in this function is that we're asked to produce a triangle 45 00:03:36,320 --> 00:03:39,430 that's so small that we're not going to recurse anymore. 46 00:03:39,430 --> 00:03:42,375 We've gotten to the smallest size triangle that we're going to make. 47 00:03:42,375 --> 00:03:47,200 And I don't know what that is, but clearly that's going be kind of an 48 00:03:47,200 --> 00:03:50,110 interesting number. So, you know, I'm going to give it a name 49 00:03:50,110 --> 00:03:53,620 as a constant. [SOUND] I'll call it cutoff. 50 00:03:53,620 --> 00:03:59,937 And, I don't know, we'll just say 2. 2 seems pretty small. 51 00:04:01,120 --> 00:04:05,050 You might end up not being right in the sense that it won't look quite right, but 52 00:04:05,050 --> 00:04:07,280 since it's a constant, we'll be good to go. 53 00:04:07,280 --> 00:04:20,410 So what that means is if I'm asked to draw a Sierpinski Triangle of that size, 54 00:04:20,410 --> 00:04:25,590 of the cutoff size, 5, then there won't be any recursion involved at all. 55 00:04:26,600 --> 00:04:36,050 I'll just produce a triangle of the cut off sides, that is of outline form and is 56 00:04:36,050 --> 00:04:41,740 red. And here, I'm going to use a trick that I 57 00:04:41,740 --> 00:04:45,530 haven't shown you in a while. which is, when I'm doing check-expects 58 00:04:45,530 --> 00:04:49,890 for graphical things and I kind of want to make sure my check-expects are right 59 00:04:49,890 --> 00:04:52,940 in the sense that the images actually are looking the way I want them to look. 60 00:04:52,940 --> 00:04:56,220 A great thing to do at this point is to run it. 61 00:04:56,220 --> 00:05:03,328 And the task will fail but I can actually kind of see what the test was supposed to 62 00:05:03,328 --> 00:05:07,442 be. And, of course, that's very, very hard to 63 00:05:07,442 --> 00:05:11,556 see but you know, there is a triangle there. 64 00:05:11,556 --> 00:05:17,030 Let's do another one. Our domain analysis says that the next 65 00:05:17,030 --> 00:05:22,130 biggest size of triangle in some sense is cutoff times 2. 66 00:05:22,130 --> 00:05:26,295 Of course, it could be not exactly a multiple of cutoff, but just to make my 67 00:05:26,295 --> 00:05:37,230 check-expect simple, let's do that case. Let's say check-expect Sierpinski 68 00:05:37,230 --> 00:05:43,744 Triangle times cutoff 2. And what's that going to be? 69 00:05:43,744 --> 00:05:58,820 That's going to be a big triangle, of that size with three little triangles in 70 00:05:58,820 --> 00:06:05,210 it. So there's going to be some kind of, 71 00:06:05,210 --> 00:06:10,850 we're going to take that triangle, the big one and we're going to put three 72 00:06:10,850 --> 00:06:15,060 little triangles in it. And now, let's make the three little 73 00:06:15,060 --> 00:06:17,380 triangles. Well, each of the three little triangles 74 00:06:17,380 --> 00:06:19,950 is the same. So let me just make one of them using 75 00:06:19,950 --> 00:06:23,168 local. I'll avoid redundant computation here. 76 00:06:23,168 --> 00:06:26,885 And there's recursion going on here so this a good place to avoid redundant 77 00:06:26,885 --> 00:06:31,290 computation. I'll say let's define something which 78 00:06:31,290 --> 00:06:38,362 I'll just call sub, for the sub triangle. And then what's this going to be? 79 00:06:38,362 --> 00:06:43,246 Well, this is just a Sierpinski triangle of size cutoff, because if I take times 80 00:06:43,246 --> 00:06:47,623 cutoff 2 and divide it by 2, that's cutoff. 81 00:06:47,623 --> 00:06:55,293 And I know that a Sierpinski triangle of size cutoff is just a triangle, so this 82 00:06:55,293 --> 00:07:02,020 is really just going to be this thing here. 83 00:07:02,020 --> 00:07:07,560 And now, I've got one of them and I need to arrange the three of them. 84 00:07:07,560 --> 00:07:10,840 There's kind of two on the bottom and one on the top. 85 00:07:10,840 --> 00:07:15,139 And I can do that this way by staying above the one on the top. 86 00:07:16,490 --> 00:07:19,530 And then the side, so this is the bottom row. 87 00:07:19,530 --> 00:07:30,411 That's the bottom row and that's the top row, and if I want to be silly, I could 88 00:07:30,411 --> 00:07:35,030 do that. Just accentuate the way it's going to be. 89 00:07:35,030 --> 00:07:40,090 That's kind of what a Sierpinski triangle of size times 2 cutoff is supposed to be. 90 00:07:40,090 --> 00:07:42,281 Let's run that and see what it looks like. 91 00:07:42,281 --> 00:07:47,023 And here we're starting kind of to be able to see it's sort of maybe a little 92 00:07:47,023 --> 00:07:49,750 bit. You know what I could do? 93 00:07:49,750 --> 00:07:53,620 Great thing about having done this as a cut off, and great thing about having 94 00:07:53,620 --> 00:07:59,820 used cut off in all my check expects, I just temporarily make this 20. 95 00:07:59,820 --> 00:08:03,310 Which is of course going to be much too big for real good looking Sierpinski 96 00:08:03,310 --> 00:08:06,219 triangles, but it'll help me see what my tests are doing. 97 00:08:11,280 --> 00:08:15,540 Oh yeah, that looks like a base case and that looks like a case that's kind of a 98 00:08:15,540 --> 00:08:18,540 little bit bigger than a base case. Hm, that's looking pretty good. 99 00:08:18,540 --> 00:08:24,597 Let me go ahead and make this 2 again. Now, I've got the examples. 100 00:08:24,597 --> 00:08:29,890 Let's try to code this thing up. [SOUND] Well, what I'm going to do now is 101 00:08:29,890 --> 00:08:32,470 to get the template for generative recursion. 102 00:08:32,470 --> 00:08:36,320 And where I'm going to get the template for generative recursion is I'm going to 103 00:08:36,320 --> 00:08:40,880 go to the course website. So I go over to the Coursera website. 104 00:08:40,880 --> 00:08:45,810 I go over to the Design Recipes page and I follow the Generative Recursion link. 105 00:08:45,810 --> 00:08:48,658 And here is the template for generative recursion. 106 00:08:48,658 --> 00:08:54,098 I'm just going to copy it, and bring it back over to DrRacket. 107 00:08:54,098 --> 00:08:59,740 Now, I'm pasting the template. This, of course, is the stub. 108 00:08:59,740 --> 00:09:06,930 [BLANK_AUDIO] At this point in the course, we don't leave stubs around, but 109 00:09:06,930 --> 00:09:11,140 I'm leaving this stub around just because this is the first time we've done 110 00:09:11,140 --> 00:09:14,170 generative recursion. This is the template. 111 00:09:15,590 --> 00:09:18,734 I'll make two copies of it, just so we can talk about it. 112 00:09:18,734 --> 00:09:24,054 [SOUND] So this is the template. Now, let me get going. 113 00:09:24,054 --> 00:09:33,630 I've got to rename the template because the function that I want to design is 114 00:09:33,630 --> 00:09:37,310 called stri. So I rename the template. 115 00:09:37,310 --> 00:09:43,870 I rename its recursive call. And I've been using s for this perimeter 116 00:09:43,870 --> 00:09:47,460 because its the side length. So I'm going to go ahead and do that 117 00:09:47,460 --> 00:10:00,740 everywhere within this function as well. And now, I've got this template. 118 00:10:00,740 --> 00:10:06,500 I've got some check-expects. What does this template mean? 119 00:10:06,500 --> 00:10:11,765 Well, the way to read this template is this question, if trivial question mark 120 00:10:11,765 --> 00:10:14,460 s. Another way to read that question is it's 121 00:10:14,460 --> 00:10:17,420 the same thing as saying, are we in the base case? 122 00:10:17,420 --> 00:10:21,930 The reason we call it trivial in this template is this is the problem that's so 123 00:10:21,930 --> 00:10:26,240 simple that we're not going to have to do any recursion. 124 00:10:26,240 --> 00:10:30,555 So when is a Sierpinski triangle, so simple that we won't have to do any 125 00:10:30,555 --> 00:10:33,880 recursion? Well, it's when the size reaches cutoff. 126 00:10:35,290 --> 00:10:38,710 That's sort of what we decided is cutoff was the smallest one we were going to do. 127 00:10:38,710 --> 00:10:46,840 So I'm going to change trivial here to be less than or equal to s to cutoff. 128 00:10:46,840 --> 00:10:50,610 I could have made it less than. Now that's just a detail in how we do 129 00:10:50,610 --> 00:10:53,765 this particular function. But I'm saying less than or equal s to 130 00:10:53,765 --> 00:10:59,110 cutoff. And now trivial answer in the template is 131 00:10:59,110 --> 00:11:02,640 telling me hey what you need to fill in here is what you're going to do if 132 00:11:02,640 --> 00:11:05,840 there's not going to be any more recursion. 133 00:11:05,840 --> 00:11:07,911 Well, I know what I'm going to do if there's not anymore recursion. 134 00:11:07,911 --> 00:11:14,419 I'm just going to make a triangle of that size. 135 00:11:14,419 --> 00:11:20,926 Okay? I'm just going to say triangle s outline 136 00:11:20,926 --> 00:11:22,125 red. Okay? 137 00:11:22,125 --> 00:11:28,440 That's the trivial answer. So the trivial question is we've reached 138 00:11:28,440 --> 00:11:31,535 the trivial case if s is less than or equal to cutoff. 139 00:11:31,535 --> 00:11:35,780 And in that case we make a triangle of size s. 140 00:11:35,780 --> 00:11:38,770 Notice I'm making a triangle of size s here. 141 00:11:38,770 --> 00:11:43,160 I'm not making a triangle of size cutoff. The reason I'm doing that is this less 142 00:11:43,160 --> 00:11:46,455 than or equal to means that s might be smaller than cutoff. 143 00:11:46,455 --> 00:11:50,590 Okay? It's just, at least it's smallest cutoff 144 00:11:50,590 --> 00:11:53,068 so that's this is an s here rather than cutoff. 145 00:11:53,068 --> 00:11:58,450 So then, what do I do in the recursive case? 146 00:11:58,450 --> 00:12:01,523 Well, you know, it's kind of right here. Okay? 147 00:12:01,523 --> 00:12:17,505 I'm going to overlay a triangle of current size [SOUND] that's outline in 148 00:12:17,505 --> 00:12:22,683 red. With what? 149 00:12:22,683 --> 00:12:25,983 Well, here is the recursion in the template, so I'm going to build around 150 00:12:25,983 --> 00:12:28,905 that. And what my example tells me is, only do 151 00:12:28,905 --> 00:12:32,820 the recursion once. Don't do it three times. 152 00:12:32,820 --> 00:12:38,776 So I'll say, local, define sub. I'm just giving a name for the recursion. 153 00:12:38,776 --> 00:12:44,410 There's the recursion. And now what's this next problem thing? 154 00:12:44,410 --> 00:12:48,740 Well, next problem is the piece of the template that tells me, hey. 155 00:12:48,740 --> 00:12:51,970 You better not make the recursive call be with S. 156 00:12:51,970 --> 00:12:55,290 If you make the recursive call be with S, we've got a problem, because this is 157 00:12:55,290 --> 00:12:59,632 going to happen forever. You've gotta somehow reduce S. 158 00:12:59,632 --> 00:13:06,180 And in this case, the way we reduce S, we make a smaller triangle, and each time, 159 00:13:06,180 --> 00:13:10,040 we make a triangle that's half as big. That's what came from our domain 160 00:13:10,040 --> 00:13:14,780 analysis. So we make that triangle. 161 00:13:14,780 --> 00:13:20,350 I'm getting this from the examples. And then what do we do? 162 00:13:20,350 --> 00:13:23,253 Well, we do the thing that is in our check-expects. 163 00:13:24,360 --> 00:13:36,230 We do above, beside. Let's try it. 164 00:13:36,230 --> 00:13:38,560 Hey, the test passed. Let's try a bigger one. 165 00:13:38,560 --> 00:13:42,805 What I'll do is, I'll make the interactions area bigger, by doing a 166 00:13:42,805 --> 00:13:49,336 Command+D. I'll say stri of 100 and that's a bigger 167 00:13:49,336 --> 00:13:54,673 one. Let's see stri of 200 is even bigger. 168 00:13:54,673 --> 00:13:57,380 There you go. You could make them even bigger. 169 00:13:59,870 --> 00:14:04,320 Command D to get me back to the code. You can see the problem I'm about to give 170 00:14:04,320 --> 00:14:06,450 you, but let me talk about this for just a second. 171 00:14:06,450 --> 00:14:10,140 Look, what did we do? We were asked to draw an image that 172 00:14:10,140 --> 00:14:15,190 looked like that. We did a little domain analysis, we 173 00:14:15,190 --> 00:14:18,990 realized oh, first you make a triangle and then you make three triangles that 174 00:14:18,990 --> 00:14:22,140 are each half as big. And then [INAUDIBLE] each of those you do 175 00:14:22,140 --> 00:14:24,900 it again and again and again, until the triangle gets too small. 176 00:14:24,900 --> 00:14:28,908 That's cutoff. Then we followed HTDF. 177 00:14:28,908 --> 00:14:33,080 Good old-fashioned HTDF pretty much. We did a signature. 178 00:14:33,080 --> 00:14:35,140 We did a purpose. We did some examples. 179 00:14:36,190 --> 00:14:41,520 We did a stub to support the examples. Then there was one difference here, which 180 00:14:41,520 --> 00:14:47,390 we used this new template. This template for generative recursion. 181 00:14:47,390 --> 00:14:51,310 And in this template, there were three key pieces we had to fill in. 182 00:14:51,310 --> 00:14:56,360 The trivial predicate, which meant hey we've reached the end of the recursion, 183 00:14:56,360 --> 00:15:00,980 the trivial answer, which is what we do at the end of the recursion. 184 00:15:00,980 --> 00:15:05,070 In the terminology we used, for structural recursion, this was the base 185 00:15:05,070 --> 00:15:10,460 case test and this was the base case result. 186 00:15:10,460 --> 00:15:16,700 And then, we did the non-base case where we do something with the current value d, 187 00:15:16,700 --> 00:15:20,780 and we call ourselves recursively with some next problem. 188 00:15:20,780 --> 00:15:24,301 And that's how this ended up looking. It ended up looking just like this. 189 00:15:24,301 --> 00:15:28,202 So that's kind of neat, that's kind of fun. 190 00:15:28,202 --> 00:15:35,140 What I want you to do now is to do the second problem in this starter file, 191 00:15:35,140 --> 00:15:39,430 which is to design a function to produce a Sierpinski carpet of size S. 192 00:15:39,430 --> 00:15:43,230 And here's an example of a large Sierpinski carpet. 193 00:15:43,230 --> 00:15:46,069 And let me just observe one thing for you that will help. 194 00:15:48,130 --> 00:15:55,545 The idea is you make a square and inside of that square you rut eight copies of a 195 00:15:55,545 --> 00:16:00,470 recursive call. Those sit all around the edge, one, two, 196 00:16:00,470 --> 00:16:05,200 three, four, five, six, seven, eight. And right in the middle you just put a 197 00:16:05,200 --> 00:16:11,000 blank square of that size. So it's almost the same structure as the 198 00:16:11,000 --> 00:16:14,030 triangle. The key inside you need is going to be 199 00:16:14,030 --> 00:16:21,415 eight copies of the recursive call to s carpet and a blank square in the middle. 200 00:16:21,415 --> 00:16:26,050 Why don't you do that and we'll talk when you're done. 201 00:16:28,950 --> 00:16:32,962 What I'm going to do now is just quickly go through the design of the s carpet 202 00:16:32,962 --> 00:16:38,612 function. Let's see. 203 00:16:38,612 --> 00:17:03,898 We can assume a number will produce an image. 204 00:17:03,898 --> 00:17:07,017 [SOUND] Now, let's see. We start with the base case or because 205 00:17:07,017 --> 00:17:11,306 it's a general recursion function. Perhaps I should say the trivial case, 206 00:17:11,306 --> 00:17:15,180 which is that we're making a very small carpet. 207 00:17:15,180 --> 00:17:17,550 I just used the same cutoff constant as before. 208 00:17:17,550 --> 00:17:20,812 Maybe I could've done a different one. Or I'll just use the same one. 209 00:17:20,812 --> 00:17:29,490 If we reached out size, then the result is just a square of that size, that's an 210 00:17:29,490 --> 00:17:33,140 outline and red. I could also perhaps have made a constant 211 00:17:33,140 --> 00:17:34,311 for the color. I didn't do that. 212 00:17:34,311 --> 00:17:42,105 Now lets do one that's a bit bigger. Now it doesn't have to be times cutoff 3. 213 00:17:42,105 --> 00:17:47,560 I'm just making it times cut off 3 to keep the math simple. 214 00:17:47,560 --> 00:17:53,538 Because of course each of the inner squares is one third the side length of 215 00:17:53,538 --> 00:17:56,640 the outer square. So that keeps it a bit simpler for me. 216 00:17:56,640 --> 00:18:00,580 If I'm doing that carpet then let's see. It's an overlay. 217 00:18:00,580 --> 00:18:17,710 It's an overlay of a square of that full size, with what? 218 00:18:17,710 --> 00:18:24,187 [SOUND] With well I need some inner squares and I'm going to need the same 219 00:18:24,187 --> 00:18:30,760 square repeated time, so I'll do that local thing again. 220 00:18:30,760 --> 00:18:37,490 I'll call the one that's actually carpet. I'll call that one sub. 221 00:18:37,490 --> 00:18:39,168 And what is that we're going to be in this case? 222 00:18:39,168 --> 00:18:44,970 Well, it's going to be a carpet of size cutoff because times cutoff 3 divided by 223 00:18:44,970 --> 00:18:49,614 3 is cutoff. So that's a square of size cutoff outline 224 00:18:49,614 --> 00:18:53,952 in red. Remember, we're doing the cases just one 225 00:18:53,952 --> 00:18:58,503 bigger, there's just going to be one recursion here. 226 00:18:58,503 --> 00:19:02,499 And, we also need that blank one in the middle. 227 00:19:02,499 --> 00:19:09,956 That's just doesn't have any color to it, that's just a square-sized cutoff. 228 00:19:09,956 --> 00:19:14,660 But it's, this doesn't have to be solid. The key thing is, it has to be white. 229 00:19:14,660 --> 00:19:24,380 So now I've got those two. I've got the outer square, I've got the 230 00:19:24,380 --> 00:19:28,090 makings of the nine inner squares. Now, I just have to put the nine inner 231 00:19:28,090 --> 00:19:41,090 squares together above the, the side. Sub, sub, sub, beside sub blank. 232 00:19:41,090 --> 00:19:45,150 So now you see why I used a 3 letter name for a blank. 233 00:19:45,150 --> 00:19:48,872 Right. There's a method to my madness, beside 234 00:19:48,872 --> 00:19:58,189 blk blk blk. That's all of that. 235 00:19:58,189 --> 00:20:05,321 [NOISE] Run it to see if it's well formed. 236 00:20:05,321 --> 00:20:08,270 It is. I can't really see it. 237 00:20:08,270 --> 00:20:13,422 Let's do that same trick I did before of temporarily making cutoff much bigger. 238 00:20:13,422 --> 00:20:17,030 Running it again. I'm looking at my failing test. 239 00:20:17,030 --> 00:20:21,550 But seeing if the expected values look hm, that doesn't look very good at all. 240 00:20:21,550 --> 00:20:36,311 What happened there? That's not what I wanted. 241 00:20:36,311 --> 00:20:44,091 Oh, I put nothing but blank on the bottom row. 242 00:20:44,091 --> 00:20:51,880 Silly me. The bottom row has to be sub, sub, sub. 243 00:20:51,880 --> 00:20:55,970 Let's see what they look like now. Oh yeah that looks much better. 244 00:20:55,970 --> 00:21:00,880 It's not the full carpet because it's just one level of recursion, but it's a 245 00:21:00,880 --> 00:21:05,100 good start. Okay. 246 00:21:05,100 --> 00:21:08,220 Now I go get the template for generative recursion. 247 00:21:08,220 --> 00:21:11,170 There it is. I copy it. 248 00:21:11,170 --> 00:21:15,170 I bring it over to here. I paste it in. 249 00:21:15,170 --> 00:21:21,694 I comment out the stub. I rename the template function. 250 00:21:23,310 --> 00:21:28,930 I rename the recursive call. And I like the parameter s for this 251 00:21:28,930 --> 00:21:32,360 because it's the side length. So I've got fix all of those. 252 00:21:32,360 --> 00:21:41,470 Now I've got to decide some of these other things. 253 00:21:41,470 --> 00:21:43,470 Let's see. What is the trivial case? 254 00:21:43,470 --> 00:21:46,870 What's the case where there's no more recursion or, in our old terminology, 255 00:21:46,870 --> 00:21:49,630 what's the base case. Well, that's the same as it was for the 256 00:21:49,630 --> 00:21:54,150 triangle, it's just less than or equal to ask for the cutoff. 257 00:21:54,150 --> 00:21:56,910 What's the trivial answer. Well the trivial answer was, we just make 258 00:21:56,910 --> 00:22:10,180 a square of this size. And what's the nontrivial answer. 259 00:22:10,180 --> 00:22:23,504 Well, we're going to overlay, a square of this size [SOUND] with, what? 260 00:22:23,504 --> 00:22:29,300 Well we're going to do this local thing so that we don't make the recursive call 261 00:22:29,300 --> 00:22:33,037 eight times. [SOUND] There's the recursive call from 262 00:22:33,037 --> 00:22:37,874 the template, but we have to decide what the next problem is. 263 00:22:37,874 --> 00:22:50,966 Well, next problem is s divided by 3, because each inner squared is one third 264 00:22:50,966 --> 00:23:02,093 the side length. [SOUND] We also need blk [SOUND] and it's 265 00:23:02,093 --> 00:23:06,702 above, let me try to get it right this time. 266 00:23:06,702 --> 00:23:20,720 Beside sub sub sub [SOUND]. Beside, beside sub blk sub, beside sub 267 00:23:20,720 --> 00:23:32,294 sub sub. Your mat just passed and let's try a big 268 00:23:32,294 --> 00:23:36,350 one. Hmm, that doesn't look quite right. 269 00:23:36,350 --> 00:23:43,410 Why doesn't it look that right? It doesn't look rich enough. 270 00:23:43,410 --> 00:23:48,135 Oh, I know what's wrong. [SOUND] forgot to change cutoff back to 271 00:23:48,135 --> 00:23:53,165 2. So there's not many levels of recursion. 272 00:23:53,165 --> 00:24:04,680 [BLANK_AUDIO] Let's try it again. [SOUND] [BLANK_AUDIO] This is taking 273 00:24:04,680 --> 00:24:06,190 longer. Yeah, that looks a lot better. 274 00:24:10,970 --> 00:24:15,340 So there you go, that's my version of the Sierpinski triangle, and the Sierpinski 275 00:24:15,340 --> 00:24:18,400 carpet. If your version of the carpet came up 276 00:24:18,400 --> 00:24:23,150 significantly different than that or even different, be sure to compare my version 277 00:24:23,150 --> 00:24:27,090 to your version, and be sure that you, your version really only differs in 278 00:24:27,090 --> 00:24:29,420 details. The version really still has to have the 279 00:24:29,420 --> 00:24:32,780 same recursive structure based on this template. 280 00:24:32,780 --> 00:24:36,940 And then in the next video we'll talk about the last piece of the recipe for 281 00:24:36,940 --> 00:24:40,806 generative recursion.