1 00:00:00,000 --> 00:00:15,000 2 00:00:15,000 --> 00:00:16,000 3 00:00:16,000 --> 00:00:18,000 4 00:00:18,000 --> 00:00:30,000 This presentation is delivered by the Stanford Center for Professional Development. 5 00:00:30,000 --> 00:00:34,000 Instructor (Julie Zelenski):Hey. 6 00:00:34,000 --> 00:00:37,000 Good afternoon. So kind of remind ourselves about thinking 7 00:00:37,000 --> 00:00:41,000 recursively and where we're trying to work out way toward. 8 00:00:41,000 --> 00:00:44,000 Recursive [inaudible] is really the hard part. Somebody gives you a problem and they say 9 00:00:44,000 --> 00:00:46,000 solve this recursively, 10 00:00:46,000 --> 00:00:50,000 where are you gonna find you spend your time is saying, well, given this problem how can I find that self similarity 11 00:00:50,000 --> 00:00:52,000 in it, how can I 12 00:00:52,000 --> 00:00:55,000 break it apart in such a way that a smaller form of the problem 13 00:00:55,000 --> 00:00:59,000 within, right, if I made that recursive call and then used it 14 00:00:59,000 --> 00:01:02,000 was gonna solve the whole problem for me. Maybe there's more than one solve problem, maybe 15 00:01:02,000 --> 00:01:04,000 it's a divide in half, 16 00:01:04,000 --> 00:01:05,000 something like that, but 17 00:01:05,000 --> 00:01:08,000 that part is usually where you'll spend a lot of your time is trying to figure out 18 00:01:08,000 --> 00:01:13,000 how it is you can structure it to divide it in a self similar way. Once 19 00:01:13,000 --> 00:01:16,000 you have that plan about how you're getting a little bit smaller, a little bit simpler, 20 00:01:16,000 --> 00:01:20,000 it's usually not so hard to follow that to the logical conclusion and say well, 21 00:01:20,000 --> 00:01:24,000 if I keep doing that enough times, what do I get to that will really allow me to terminate 22 00:01:24,000 --> 00:01:26,000 this, the simplest possible case 23 00:01:26,000 --> 00:01:27,000 that 24 00:01:27,000 --> 00:01:29,000 all of those, 25 00:01:29,000 --> 00:01:33,000 you know, minimizing of the problem might eventually lead to something so simple we can directly 26 00:01:33,000 --> 00:01:34,000 solve it 27 00:01:34,000 --> 00:01:37,000 that we're working toward. Sometimes there's more than one base case, but ideally, 28 00:01:37,000 --> 00:01:41,000 there's exactly one that everything comes to. It kind of cleans up your code if you can make 29 00:01:41,000 --> 00:01:43,000 it come out that way. There's a 30 00:01:43,000 --> 00:01:46,000 couple common patterns and we've seen some of these already and we're gonna see them again 31 00:01:46,000 --> 00:01:48,000 and again, but 32 00:01:48,000 --> 00:01:50,000 partly what you're trying to develop is a 33 00:01:50,000 --> 00:01:51,000 set of 34 00:01:51,000 --> 00:01:55,000 examples you've seen before that help you to kind of use those patterns to explore further problems 35 00:01:55,000 --> 00:01:56,000 in the future 36 00:01:56,000 --> 00:02:00,000 and so a very common way of dividing stuff is you have some collection, whether 37 00:02:00,000 --> 00:02:03,000 it's a vector or a string or 38 00:02:03,000 --> 00:02:04,000 a 39 00:02:04,000 --> 00:02:06,000 set of paths or something like 40 00:02:06,000 --> 00:02:10,000 that that part of the recursion often is that you somehow separate one from them so when 41 00:02:10,000 --> 00:02:13,000 we were trying to choose the people to go to the flicks, right, 42 00:02:13,000 --> 00:02:14,000 we picked some student 43 00:02:14,000 --> 00:02:17,000 at random and said okay, this student is either in or out 44 00:02:17,000 --> 00:02:22,000 and so we separated one from the mass, leaving us an N minus 1 and then that N minus 1, 45 00:02:22,000 --> 00:02:23,000 right, was that recursive 46 00:02:23,000 --> 00:02:27,000 piece about that substructure saying, well, if I had the answer for the remaining N 47 00:02:27,000 --> 00:02:28,000 minus 1, 48 00:02:28,000 --> 00:02:33,000 right, I could use the information about this 1 I've separated out to join it together. 49 00:02:33,000 --> 00:02:36,000 So sometimes, that's the first person, sometimes that's the last person. 50 00:02:36,000 --> 00:02:39,000 51 00:02:39,000 --> 00:02:42,000 Sometimes it's almost a random person that you're picking, but the idea of 52 00:02:42,000 --> 00:02:44,000 separating one or some small number 53 00:02:44,000 --> 00:02:47,000 leaving the N minus that number to work on. 54 00:02:47,000 --> 00:02:51,000 Sometimes it's a bigger chunk, it's a division in half or in thirds or something 55 00:02:51,000 --> 00:02:54,000 where I'm dividing and conquering the binary search doing that saying. 56 00:02:54,000 --> 00:02:56,000 We've got some information from 57 00:02:56,000 --> 00:02:58,000 the middle that tells us about 58 00:02:58,000 --> 00:03:00,000 what these two halves 59 00:03:00,000 --> 00:03:04,000 are in the case of binary search, we only do recurring one. We'll see some cases 60 00:03:04,000 --> 00:03:06,000 we're actually able to divide it in half and recur on both, 61 00:03:06,000 --> 00:03:10,000 but where we're still just dividing the problem in easier, in this case, half as big 62 00:03:10,000 --> 00:03:14,000 versions of the same problem, but then we can attack recursively. And sometimes there's 63 00:03:14,000 --> 00:03:18,000 more like a choice. This is maybe the thematic thing for some of the later things when 64 00:03:18,000 --> 00:03:21,000 [inaudible] is that there's some choice of the options that remain 65 00:03:21,000 --> 00:03:24,000 and the recursions 66 00:03:24,000 --> 00:03:27,000 that attack it to make it one of those choices, which then kind of 67 00:03:27,000 --> 00:03:31,000 leads you to a state that has fewer choices to be made, fewer decisions 68 00:03:31,000 --> 00:03:36,000 and allows you try decisions from there to work your way to some base case. 69 00:03:36,000 --> 00:03:39,000 One of the things I'm also gonna be talking about today is 70 00:03:39,000 --> 00:03:44,000 some of the implications of the relationship between when you process this part you've separated 71 00:03:44,000 --> 00:03:46,000 out and when you make the recursive call. But 72 00:03:46,000 --> 00:03:48,000 it's actually totally not 73 00:03:48,000 --> 00:03:52,000 irrelevant whether I make the recursive and then try to process the one, or whether I process 74 00:03:52,000 --> 00:03:53,000 it and then do the recursion. 75 00:03:53,000 --> 00:03:56,000 In some situations, they'll produce different 76 00:03:56,000 --> 00:03:59,000 results and different answers that are interesting to know about 77 00:03:59,000 --> 00:04:05,000 how those things play out. 78 00:04:05,000 --> 00:04:07,000 So today, the theme is procedure recursion 79 00:04:07,000 --> 00:04:09,000 and procedural is differentiated from functional in 80 00:04:09,000 --> 00:04:15,000 a very minute almost a bit semantic about the definition, but it's worth telling 81 00:04:15,000 --> 00:04:18,000 you. A functional recursion problem is one where you have a function 82 00:04:18,000 --> 00:04:22,000 returning an answer like is [inaudible] true/false. 83 00:04:22,000 --> 00:04:23,000 The 84 00:04:23,000 --> 00:04:25,000 factorial is a raised power 85 00:04:25,000 --> 00:04:26,000 telling you what the answer is. In 86 00:04:26,000 --> 00:04:30,000 a procedural recursion, we have functions that don't return anything 87 00:04:30,000 --> 00:04:33,000 so there's not an answer being computed in result of that, 88 00:04:33,000 --> 00:04:37,000 but there is recursive in [inaudible] so there's a procedure here that calls itself 89 00:04:37,000 --> 00:04:41,000 eventually bottoming out at some base case and as a result of all that 90 00:04:41,000 --> 00:04:45,000 recursion being done, something happens. The one I'm gonna do at the beginning here is some drawing pictures, 91 00:04:45,000 --> 00:04:49,000 some graphics that draw fractal graphics 92 00:04:49,000 --> 00:04:52,000 where there's not an answer being computed, but there's something being illustrated on 93 00:04:52,000 --> 00:04:53,000 the graphics window. 94 00:04:53,000 --> 00:04:57,000 So I'm gonna look at two examples of this because I think sometimes for 95 00:04:57,000 --> 00:05:01,000 some students the numbers and the strings aren't the best way to get 96 00:05:01,000 --> 00:05:02,000 it; sometimes visually 97 00:05:02,000 --> 00:05:04,000 really helps to 98 00:05:04,000 --> 00:05:08,000 open up the enlightenment for what recursion means in terms of the structure. 99 00:05:08,000 --> 00:05:11,000 We're gonna look at some pictures that have a self similar structure 100 00:05:11,000 --> 00:05:14,000 that repeat within itself that you if you look at it at one level of detail 101 00:05:14,000 --> 00:05:18,000 you'll see certain elements that, actually, if you look a little closer, you'll see that same 102 00:05:18,000 --> 00:05:22,000 element, but just repeated on a smaller scale within that and then within that again kind 103 00:05:22,000 --> 00:05:24,000 of moving down to that base case. 104 00:05:24,000 --> 00:05:29,000 The way these things that we've written in code will give us some outer fractal that you draw 105 00:05:29,000 --> 00:05:33,000 that is part of its handling then makes recursive calls to draw these inner, smaller versions 106 00:05:33,000 --> 00:05:36,000 of the fractal within itself. 107 00:05:36,000 --> 00:05:40,000 Okay. So here is a little bit of code. 108 00:05:40,000 --> 00:05:44,000 So I'm not gonna tell you what it goes, but we're gonna sort of just imagine thinking it through and 109 00:05:44,000 --> 00:05:45,000 looking at this 110 00:05:45,000 --> 00:05:47,000 to see what kind of things it could produce. 111 00:05:47,000 --> 00:05:51,000 Draw fractal, let's give it an X, Y in width and height, which I'll assume is the bounding rectangle of what's 112 00:05:51,000 --> 00:05:52,000 being drawn 113 00:05:52,000 --> 00:05:54,000 and then it makes a call to some helper 114 00:05:54,000 --> 00:05:56,000 called draw triangle. 115 00:05:56,000 --> 00:05:59,000 If I assume that does what it seems like it does it says oh, it draws a triangle, right, that's 116 00:05:59,000 --> 00:06:03,000 inscribed within that rectangle. 117 00:06:03,000 --> 00:06:06,000 Next up I'm seeing this base case that's, like, well, if that triangle was particularly small, 118 00:06:06,000 --> 00:06:10,000 in this case, two tenths of an inch or smaller in either dimension, then we don't do anything further 119 00:06:10,000 --> 00:06:12,000 with it. We leave it alone. 120 00:06:12,000 --> 00:06:15,000 Otherwise, we do a little bit of computation here, a little bit of 121 00:06:15,000 --> 00:06:18,000 math to compute some coordinates 122 00:06:18,000 --> 00:06:22,000 and they're labeled the left, top and right, which is basically it's making a call 123 00:06:22,000 --> 00:06:23,000 on 124 00:06:23,000 --> 00:06:25,000 the left 125 00:06:25,000 --> 00:06:28,000 sort of sub region of this 126 00:06:28,000 --> 00:06:30,000 rectangle that's at the lower left corner, 127 00:06:30,000 --> 00:06:32,000 but half as tall, half as wide. 128 00:06:32,000 --> 00:06:35,000 Here's one that starts in the middle and 129 00:06:35,000 --> 00:06:39,000 is also half as tall, half as wide that represents a chunk out of the top, 130 00:06:39,000 --> 00:06:41,000 and then one that's to the 131 00:06:41,000 --> 00:06:45,000 right. 132 00:06:45,000 --> 00:06:48,000 133 00:06:48,000 --> 00:06:51,000 This produced something you've seen 134 00:06:51,000 --> 00:06:52,000 before, 135 00:06:52,000 --> 00:06:54,000 but you generated it a very different 136 00:06:54,000 --> 00:06:58,000 way last time. Right. In assignment one, we had you do the chaos demonstration, 137 00:06:58,000 --> 00:07:02,000 it produced this drawing, which is due to Sirpinski 138 00:07:02,000 --> 00:07:04,000 from a different mechanism, 139 00:07:04,000 --> 00:07:07,000 but in fact, it is a very recursive drawing when you look at it. Right. There's this 140 00:07:07,000 --> 00:07:09,000 outer triangle 141 00:07:09,000 --> 00:07:11,000 and then within it, there is a 142 00:07:11,000 --> 00:07:16,000 left most, a top most and a right most reproduction kind of the outer triangle at a smaller level 143 00:07:16,000 --> 00:07:17,000 of scale. 144 00:07:17,000 --> 00:07:21,000 If I look in each of those triangles, would I see that same self-similarity? 145 00:07:21,000 --> 00:07:22,000 146 00:07:22,000 --> 00:07:25,000 If 147 00:07:25,000 --> 00:07:30,000 I just keep going down at each level of scale, I see the same thing, that there's a triangle 148 00:07:30,000 --> 00:07:32,000 which itself has these three 149 00:07:32,000 --> 00:07:34,000 left, right, top regions 150 00:07:34,000 --> 00:07:35,000 that 151 00:07:35,000 --> 00:07:38,000 exhibit the same structure the outer one did, but just a little bit smaller. It 152 00:07:38,000 --> 00:07:40,000 eventually gets so small 153 00:07:40,000 --> 00:07:41,000 that 154 00:07:41,000 --> 00:07:46,000 it stops drawing and that's what terminates our recursion. 155 00:07:46,000 --> 00:07:49,000 156 00:07:49,000 --> 00:07:51,000 157 00:07:51,000 --> 00:07:56,000 158 00:07:56,000 --> 00:07:59,000 159 00:07:59,000 --> 00:08:03,000 160 00:08:03,000 --> 00:08:06,000 161 00:08:06,000 --> 00:08:07,000 162 00:08:07,000 --> 00:08:11,000 163 00:08:11,000 --> 00:08:12,000 164 00:08:12,000 --> 00:08:16,000 165 00:08:16,000 --> 00:08:17,000 166 00:08:17,000 --> 00:08:21,000 167 00:08:21,000 --> 00:08:24,000 168 00:08:24,000 --> 00:08:26,000 169 00:08:26,000 --> 00:08:27,000 170 00:08:27,000 --> 00:08:28,000 171 00:08:28,000 --> 00:08:29,000 172 00:08:29,000 --> 00:08:33,000 173 00:08:33,000 --> 00:08:34,000 174 00:08:34,000 --> 00:08:36,000 175 00:08:36,000 --> 00:08:38,000 176 00:08:38,000 --> 00:08:43,000 177 00:08:43,000 --> 00:08:46,000 So 178 00:08:46,000 --> 00:08:48,000 179 00:08:48,000 --> 00:08:51,000 that is 180 00:08:51,000 --> 00:08:54,000 181 00:08:54,000 --> 00:08:57,000 182 00:08:57,000 --> 00:09:02,000 183 00:09:02,000 --> 00:09:05,000 184 00:09:05,000 --> 00:09:07,000 185 00:09:07,000 --> 00:09:13,000 186 00:09:13,000 --> 00:09:15,000 one of the aspects we'll be looking at. Okay. I did the work first. 187 00:09:15,000 --> 00:09:18,000 What happens if I 188 00:09:18,000 --> 00:09:21,000 turn it around 189 00:09:21,000 --> 00:09:25,000 so I have the same base case right and the same order of left, top, right here, 190 00:09:25,000 --> 00:09:28,000 but I wait to draw the big triangle until after I've drawn 191 00:09:28,000 --> 00:09:31,000 all the other interior fractals 192 00:09:31,000 --> 00:09:34,000 so doing the processing for this one after I've done those. I'm 193 00:09:34,000 --> 00:09:39,000 gonna get the same picture, but 194 00:09:39,000 --> 00:09:43,000 it's gonna grow in a different way 195 00:09:43,000 --> 00:09:46,000 that only I've done the whole thing is the outer triangle; in this case, drawn on 196 00:09:46,000 --> 00:09:49,000 top which isn't actually very noticeable because the 197 00:09:49,000 --> 00:09:51,000 inner piece is kind of already made up the 198 00:09:51,000 --> 00:09:54,000 outer boundaries anyway. 199 00:09:54,000 --> 00:09:57,000 Student: Can you go slower? Instructor (Julie Zelenski):Yeah, I slowed this one down a little bit. It isn't any slower in real 200 00:09:57,000 --> 00:10:01,000 life. I was kind of screwing with the pausing because I wanted to get it just right and then one 201 00:10:01,000 --> 00:10:05,000 of the pauses I think the pause is slightly faster than the other. 202 00:10:05,000 --> 00:10:08,000 But growing right from that lower left corner up 203 00:10:08,000 --> 00:10:11,000 then working all the way through the top and then all the way through the right 204 00:10:11,000 --> 00:10:13,000 and then the outer most something only being built 205 00:10:13,000 --> 00:10:17,000 is an after effect of once the inners have been constructed, so the very first 206 00:10:17,000 --> 00:10:18,000 one appearing 207 00:10:18,000 --> 00:10:21,000 way down here. Now, let 208 00:10:21,000 --> 00:10:24,000 me change my three recursive calls. 209 00:10:24,000 --> 00:10:28,000 It currently goes left, top, right. 210 00:10:28,000 --> 00:10:31,000 I'm gonna change the code to go top, left, right. 211 00:10:31,000 --> 00:10:33,000 I'll get the same picture, 212 00:10:33,000 --> 00:10:41,000 but where is the very first triangle drawn? Is it small or big? 213 00:10:41,000 --> 00:10:42,000 It's small 214 00:10:42,000 --> 00:10:46,000 and where does it live within the triangle? 215 00:10:46,000 --> 00:10:48,000 The very, very top, right? 216 00:10:48,000 --> 00:10:52,000 So the top most point?the top small little triangle, it goes there. What is the 217 00:10:52,000 --> 00:10:59,000 second triangle that's drawn? 218 00:10:59,000 --> 00:11:03,000 The one that's just down to the left of that one so I should see 219 00:11:03,000 --> 00:11:06,000 the top most one, it's left most neighbor and it's right most neighbor 220 00:11:06,000 --> 00:11:08,000 and then we'll start working our way down from there. 221 00:11:08,000 --> 00:11:13,000 One thing that is sometimes helpful to think about in terms of visualizing what 222 00:11:13,000 --> 00:11:14,000 a recursive procedure is doing 223 00:11:14,000 --> 00:11:19,000 is to think of it as a kind of an upside down tree where here's my draw fractal to the 224 00:11:19,000 --> 00:11:21,000 outer one 225 00:11:21,000 --> 00:11:23,000 and then it makes these calls, right to top 226 00:11:23,000 --> 00:11:25,000 to left 227 00:11:25,000 --> 00:11:28,000 to right. 228 00:11:28,000 --> 00:11:31,000 Realize that the way that the recursion proceeds is that 229 00:11:31,000 --> 00:11:34,000 it makes the call to the draw fractal of top, 230 00:11:34,000 --> 00:11:38,000 which then makes a call to the draw fractal of its top, which makes the call to the draw fractal of 231 00:11:38,000 --> 00:11:41,000 this top so it goes deep, 232 00:11:41,000 --> 00:11:43,000 right, until it hits that base case 233 00:11:43,000 --> 00:11:47,000 and so this was where I went top, top, top, top, top, top, top, right 234 00:11:47,000 --> 00:11:49,000 to the very top most one. 235 00:11:49,000 --> 00:11:53,000 Well, after it bottoms out here, it comes back to this one that said, okay, well, I drew the little tiny 236 00:11:53,000 --> 00:11:57,000 top, now, I need to draw the left and the right and so the ones that are fleshed out 237 00:11:57,000 --> 00:12:00,000 at the bottom here are the left and right of the top most one. 238 00:12:00,000 --> 00:12:04,000 And after those, it kind of comes back. 239 00:12:04,000 --> 00:12:06,000 240 00:12:06,000 --> 00:12:10,000 241 00:12:10,000 --> 00:12:13,000 242 00:12:13,000 --> 00:12:15,000 243 00:12:15,000 --> 00:12:17,000 244 00:12:17,000 --> 00:12:20,000 245 00:12:20,000 --> 00:12:21,000 246 00:12:21,000 --> 00:12:25,000 So sometimes thinking about it in terms of a tree and realizing that 247 00:12:25,000 --> 00:12:28,000 it is not sort of level by level or [inaudible], it's not like it draws 248 00:12:28,000 --> 00:12:32,000 all the outer ones and then the inner side of that, it really goes all 249 00:12:32,000 --> 00:12:33,000 the way down to that base case 250 00:12:33,000 --> 00:12:36,000 before it start unwinding and backing up 251 00:12:36,000 --> 00:12:37,000 and revisiting 252 00:12:37,000 --> 00:12:41,000 the pieces that kind of deferred as part of the recursion to come back 253 00:12:41,000 --> 00:12:42,000 to. 254 00:12:42,000 --> 00:12:45,000 So the very first call to draw fractal is sitting on the stack frame while all these 255 00:12:45,000 --> 00:12:47,000 other ones are active 256 00:12:47,000 --> 00:12:49,000 and when they finish their work and unwind, 257 00:12:49,000 --> 00:12:53,000 it picks up where it left off in drawing the other two thirds of the fractal. 258 00:12:53,000 --> 00:12:57,000 So this one should grow down from the top 259 00:12:57,000 --> 00:12:59,000 260 00:12:59,000 --> 00:12:59,000 261 00:12:59,000 --> 00:13:00,000 from there and then it should 262 00:13:00,000 --> 00:13:02,000 start to go to the left 263 00:13:02,000 --> 00:13:03,000 also from the top 264 00:13:03,000 --> 00:13:06,000 working its way down 265 00:13:06,000 --> 00:13:07,000 and then once it's 266 00:13:07,000 --> 00:13:11,000 worked out the whole of the left, do the right also from the top 267 00:13:11,000 --> 00:13:12,000 working its way down. 268 00:13:12,000 --> 00:13:16,000 So same picture in all these cases, right, am I doing the big triangle first, the inner triangle 269 00:13:16,000 --> 00:13:18,000 first, the left, the top, the right, 270 00:13:18,000 --> 00:13:23,000 but they show you that kind of the processing and how it would evolve is different. 271 00:13:23,000 --> 00:13:26,000 In some cases, this is gonna really matter to us. It's gonna actually change 272 00:13:26,000 --> 00:13:30,000 the outcome of the recursion how we're doing this so it's good to have a little bit 273 00:13:30,000 --> 00:13:33,000 of an idea how to visualize the different 274 00:13:33,000 --> 00:13:34,000 tracing 275 00:13:34,000 --> 00:13:37,000 through the calls. Any questions? Student:Is it possible to draw 276 00:13:37,000 --> 00:13:41,000 by 277 00:13:41,000 --> 00:13:43,000 joining in three different places at the same time? Instructor 278 00:13:43,000 --> 00:13:47,000 Well, I mean, [inaudible] control, right, and so at any given point we're 279 00:13:47,000 --> 00:13:49,000 doing one thing at a time, so 280 00:13:49,000 --> 00:13:50,000 really without 281 00:13:50,000 --> 00:13:51,000 more fancy things, 282 00:13:51,000 --> 00:13:55,000 the answer is basically no. 283 00:13:55,000 --> 00:13:58,000 Let me show you more little 284 00:13:58,000 --> 00:14:01,000 recursive 285 00:14:01,000 --> 00:14:03,000 fractal. And this is based on 286 00:14:03,000 --> 00:14:04,000 a famous Dutch painter 287 00:14:04,000 --> 00:14:06,000 Mondrian, right, who was 288 00:14:06,000 --> 00:14:07,000 289 00:14:07,000 --> 00:14:08,000 alive in the first half of the 290 00:14:08,000 --> 00:14:10,000 20th Century there, 291 00:14:10,000 --> 00:14:13,000 one of the Cubists, the group he belongs to, and you've probably seen 292 00:14:13,000 --> 00:14:16,000 some of these paintings. They might look familiar to you with these very bright primary 293 00:14:16,000 --> 00:14:18,000 colors, 294 00:14:18,000 --> 00:14:19,000 a lot of 295 00:14:19,000 --> 00:14:22,000 horizontal and 296 00:14:22,000 --> 00:14:24,000 vertical lines bisecting the canvas and then 297 00:14:24,000 --> 00:14:29,000 some of those squares being filled in with bright colors. This is sort of one of the more 298 00:14:29,000 --> 00:14:31,000 famous of the pieces that he did. 299 00:14:31,000 --> 00:14:35,000 And his little philosophy I quoted from there, right, was this idea that this 300 00:14:35,000 --> 00:14:37,000 is about harmony and beauty 301 00:14:37,000 --> 00:14:39,000 and you can 302 00:14:39,000 --> 00:14:43,000 just through lines and colors produce things that really have an aesthetic component to them. 303 00:14:43,000 --> 00:14:45,000 I think it's a pretty neat thing. 304 00:14:45,000 --> 00:14:49,000 But I'm not an artist, by any means, so I think the solution to that is if I want to create 305 00:14:49,000 --> 00:14:50,000 beautiful things I need to write 306 00:14:50,000 --> 00:14:53,000 computer programs that do them for me because if it was up to me, I won't 307 00:14:53,000 --> 00:14:55,000 do it with my own hands. 308 00:14:55,000 --> 00:14:59,000 So what I'm gonna show you is a technique for thinking of this 309 00:14:59,000 --> 00:15:01,000 as a recursive problem. 310 00:15:01,000 --> 00:15:03,000 If you look at what a Mondrian is 311 00:15:03,000 --> 00:15:04,000 and 312 00:15:04,000 --> 00:15:06,000 if you're sitting down to start this, 313 00:15:06,000 --> 00:15:10,000 you have a big canvas in front of you. It starts blank 314 00:15:10,000 --> 00:15:11,000 and you say, well, 315 00:15:11,000 --> 00:15:13,000 where should I begin? 316 00:15:13,000 --> 00:15:16,000 Well, let me just pick a random 317 00:15:16,000 --> 00:15:17,000 318 00:15:17,000 --> 00:15:19,000 direction, horizontal or vertical, 319 00:15:19,000 --> 00:15:23,000 and then I'll pick a random placement for it so I decide I'm gonna bisect vertically and I pick 320 00:15:23,000 --> 00:15:25,000 a spot somewhere in the middle of the thing and then 321 00:15:25,000 --> 00:15:28,000 I do a bisection of that with my big black line 322 00:15:28,000 --> 00:15:34,000 and now I look at the thing that I have left and I've got well two smaller canvases; one to the left of the line, one to the right, 323 00:15:34,000 --> 00:15:36,000 which themselves I could imagine 324 00:15:36,000 --> 00:15:39,000 using that same strategy for. Well, look at it and decide whether to 325 00:15:39,000 --> 00:15:41,000 make a horizontal or a vertical line 326 00:15:41,000 --> 00:15:43,000 and then, 327 00:15:43,000 --> 00:15:45,000 occasionally, along the way decide to throw in a little color 328 00:15:45,000 --> 00:15:47,000 so when I have a canvas maybe 329 00:15:47,000 --> 00:15:50,000 wash it in red or blue 330 00:15:50,000 --> 00:15:54,000 before I go through my division. And sometimes, I decide not to divide it at all. 331 00:15:54,000 --> 00:15:56,000 So this canvas that I've 332 00:15:56,000 --> 00:16:00,000 sectioned off here, I might just decide to leave it there and say, okay, that's good enough. I don't want to 333 00:16:00,000 --> 00:16:04,000 go any further on that 334 00:16:04,000 --> 00:16:07,000 one. That's not what I wanted to do. 335 00:16:07,000 --> 00:16:11,000 So it has these three options, divide the canvas horizontally, divide it vertically, 336 00:16:11,000 --> 00:16:12,000 do nothing 337 00:16:12,000 --> 00:16:15,000 and then when I have those two smaller canvases, 338 00:16:15,000 --> 00:16:19,000 I recursively can apply the same kind of Mondrian style 339 00:16:19,000 --> 00:16:20,000 affect to it 340 00:16:20,000 --> 00:16:24,000 and when I get to something that's too small, I can stop 341 00:16:24,000 --> 00:16:26,000 trying to divide it further. 342 00:16:26,000 --> 00:16:30,000 So I'll show you what the code looks like here and then I'll show it running to you. 343 00:16:30,000 --> 00:16:33,000 Most of it actually is a little bit gunky just because there's a little math of adding 344 00:16:33,000 --> 00:16:35,000 and moving and stuff like that around, but 345 00:16:35,000 --> 00:16:39,000 it has this idea of oh, here's the rectangle you're trying to draw a Mondrian in. If it's 346 00:16:39,000 --> 00:16:43,000 too small, in this case, anything under an inch I decided was too small. 347 00:16:43,000 --> 00:16:46,000 Otherwise, I fill the rectangle in the random color, which often, is white, sometimes yellow, 348 00:16:46,000 --> 00:16:48,000 sometimes blue, 349 00:16:48,000 --> 00:16:50,000 and then based on three cases of a random choice, 350 00:16:50,000 --> 00:16:54,000 I either decide to just leave it as is filled with whatever color I chose or 351 00:16:54,000 --> 00:16:56,000 I make a line, 352 00:16:56,000 --> 00:16:59,000 vertically in this case or horizontally in that case, and then 353 00:16:59,000 --> 00:17:02,000 recursively section off the two portions I've made 354 00:17:02,000 --> 00:17:09,000 to recursively apply a drawn Mondrian to draw some more Mondrian in those pieces. 355 00:17:09,000 --> 00:17:12,000 Does it work? 356 00:17:12,000 --> 00:17:15,000 Any by work, the code works, but 357 00:17:15,000 --> 00:17:17,000 does it actually produce 358 00:17:17,000 --> 00:17:21,000 art? You can be the judge. 359 00:17:21,000 --> 00:17:30,000 Now, the 360 00:17:30,000 --> 00:17:35,000 good thing is see it's easy to make new ones if you don't like that one. I 361 00:17:35,000 --> 00:17:41,000 don't like 362 00:17:41,000 --> 00:17:43,000 that one either. A little too much blue. 363 00:17:43,000 --> 00:17:46,000 That's 364 00:17:46,000 --> 00:17:50,000 getting somewhere. I might put that on my wall 365 00:17:50,000 --> 00:17:53,000 and then at this point, I just started making them just as many as you want and just keep going. Some 366 00:17:53,000 --> 00:17:56,000 of them it stops early, it has nothing to do. 367 00:17:56,000 --> 00:18:00,000 My mother-in-law is an artist and I feel like I have to apologize to her whenever I do this because 368 00:18:00,000 --> 00:18:04,000 I'm really not trying to make fun of art as though actually a computer can do anything. The truth 369 00:18:04,000 --> 00:18:06,000 is, when you do this actually what you realize is that 370 00:18:06,000 --> 00:18:09,000 it's not art, right, what's truly aesthetic is something that actually 371 00:18:09,000 --> 00:18:11,000 is not generated by randomness 372 00:18:11,000 --> 00:18:12,000 and recursion, 373 00:18:12,000 --> 00:18:16,000 but it's still interesting how [inaudible] have that pattern to them that 374 00:18:16,000 --> 00:18:18,000 are sort of Mondrianesque 375 00:18:18,000 --> 00:18:21,000 just by simply taking this recursive strategy and saying 376 00:18:21,000 --> 00:18:25,000 that's a little Mondrian, this is a little Mondrian and if you assemble them all together, 377 00:18:25,000 --> 00:18:31,000 you've built a big Mondrian. 378 00:18:31,000 --> 00:18:32,000 Millions of dollars right here I'm 379 00:18:32,000 --> 00:18:37,000 generating. I tell you, when I retire from teaching, that's gonna be my next career, 380 00:18:37,000 --> 00:18:41,000 turning out fake Mondrian's. All right. 381 00:18:41,000 --> 00:18:45,000 So any questions about little pictures and graphics and things? Student:On the previous one, could you go over what's passed in each 382 00:18:45,000 --> 00:18:48,000 of 383 00:18:48,000 --> 00:18:49,000 recursive 384 00:18:49,000 --> 00:18:52,000 or draw a Mondrian? Instructor (Julie Zelenski):Yeah. So the only thing it takes is it's just a rectangle. 385 00:18:52,000 --> 00:18:56,000 It says, this rectangle you should fill with Mondrian like things, so the outer rectangle is the 386 00:18:56,000 --> 00:18:57,000 whole canvas 387 00:18:57,000 --> 00:18:59,000 and then once I've done a bisection, right, 388 00:18:59,000 --> 00:19:03,000 I've picked some point in the middle, I've divided the rectangle into two smaller rectangles, the 389 00:19:03,000 --> 00:19:04,000 left and the right. 390 00:19:04,000 --> 00:19:07,000 It's not necessarily exactly, but 391 00:19:07,000 --> 00:19:09,000 I have one that 392 00:19:09,000 --> 00:19:12,000 starts in the origin and goes to the midpoint, one that starts in the midpoint and goes to the 393 00:19:12,000 --> 00:19:16,000 right side and so it's just basically taking the outer rectangle and dividing it. If 394 00:19:16,000 --> 00:19:19,000 I drew a picture here, it might help. 395 00:19:19,000 --> 00:19:20,000 You've got this thing. 396 00:19:20,000 --> 00:19:25,000 You choose to bisect this way and so what you're passing, is this rectangle and that rectangle, and when this 397 00:19:25,000 --> 00:19:29,000 one decides to bisect this way, then it'll pass this rectangle and that rectangle and so at each 398 00:19:29,000 --> 00:19:32,000 stage you'll have these smaller rectangles that were 399 00:19:32,000 --> 00:19:35,000 pieces of the outer rectangle that you're continuing to draw Mondrian into and 400 00:19:35,000 --> 00:19:39,000 eventually they get so small that you say I won't further divide that up anymore. I'll just stop 401 00:19:39,000 --> 00:19:42,000 right here. 402 00:19:42,000 --> 00:19:45,000 And so the line actually is drawn on the way down it turns out. 403 00:19:45,000 --> 00:19:48,000 If you'll notice, the draw black line happens before 404 00:19:48,000 --> 00:19:51,000 it draws the thing, so draw the line and then draw a background on top 405 00:19:51,000 --> 00:19:53,000 around it and stuff. 406 00:19:53,000 --> 00:19:55,000 Either way it doesn't actually really matter. You could draw it on the way out and you'd end 407 00:19:55,000 --> 00:19:57,000 up with the same picture. 408 00:19:57,000 --> 00:19:59,000 If 409 00:19:59,000 --> 00:20:01,000 just would appear differently. Student:Explain why you 410 00:20:01,000 --> 00:20:05,000 haven't returned something, like, a break or some other leads? Instructor (Julie 411 00:20:05,000 --> 00:20:09,000 Zelenski):Well, in general, I just need something that says 412 00:20:09,000 --> 00:20:11,000 don't go through the 413 00:20:11,000 --> 00:20:15,000 rest of this code. I'm not trying to get out of a loop or a switch 414 00:20:15,000 --> 00:20:16,000 415 00:20:16,000 --> 00:20:19,000 statement, right, so if 416 00:20:19,000 --> 00:20:22,000 I really want to leave the function, return is the quickest way to do that. 417 00:20:22,000 --> 00:20:26,000 The alternative is I could've inverted the sense of this task and said, well, if it's at least an inch 418 00:20:26,000 --> 00:20:30,000 wide and an inch tall, then get into this code and effectively it would say if, and it didn't 419 00:20:30,000 --> 00:20:33,000 pass if you didn't put a drop in the bottom and falling off, 420 00:20:33,000 --> 00:20:35,000 but either way, right. 421 00:20:35,000 --> 00:20:38,000 So I think I probably tend to prefer to do it this way just because I like to get my base case up from the front 422 00:20:38,000 --> 00:20:42,000 of my eyes seeing what it does and, typically, the right thing for the base case to do is 423 00:20:42,000 --> 00:20:47,000 identify that you're at the base case, do whatever simple processing is required in that case 424 00:20:47,000 --> 00:20:52,000 and then return the answer or just return right away saying, I've handled the base case and now 425 00:20:52,000 --> 00:20:56,000 let the rest of the code be and now in the recursive case going on. 426 00:20:56,000 --> 00:20:59,000 This is very much the 427 00:20:59,000 --> 00:21:03,000 style I tend to use. If we're at the base case, 428 00:21:03,000 --> 00:21:11,000 do the base case stuff and return. 429 00:21:11,000 --> 00:21:12,000 Now I'm gonna hit you with 430 00:21:12,000 --> 00:21:14,000 the most classic 431 00:21:14,000 --> 00:21:19,000 recursion example known to all cs students worldwide. 432 00:21:19,000 --> 00:21:20,000 433 00:21:20,000 --> 00:21:23,000 I wouldn't be doing my duty 434 00:21:23,000 --> 00:21:24,000 if I didn't 435 00:21:24,000 --> 00:21:26,000 teach you a little bit about 436 00:21:26,000 --> 00:21:31,000 the legend of Brahmin and its towers and how relevant it is in today's world that you 437 00:21:31,000 --> 00:21:31,000 know how to move 438 00:21:31,000 --> 00:21:35,000 graduated discs around. All right. 439 00:21:35,000 --> 00:21:37,000 So I'll give you the set up. Apparently, 440 00:21:37,000 --> 00:21:38,000 there 441 00:21:38,000 --> 00:21:42,000 are these monks and there's a legend of the tower Brahmin that these monks, apparently, 442 00:21:42,000 --> 00:21:45,000 big troublemakers, monks, you know how they are, 443 00:21:45,000 --> 00:21:49,000 you gotta keep them out of trouble so the dyad here had this idea. Well, I'm gonna give them this task that's gonna 444 00:21:49,000 --> 00:21:53,000 keep them busy for a long time and 445 00:21:53,000 --> 00:21:55,000 that way they won't be 446 00:21:55,000 --> 00:21:56,000 causing problems. 447 00:21:56,000 --> 00:22:00,000 So what he did was he stacked up these three spindles, A, B, and C, big poles 448 00:22:00,000 --> 00:22:04,000 and he had these big heavy discs, they were made of solid gold apparently in the 449 00:22:04,000 --> 00:22:06,000 Brahmin religion 450 00:22:06,000 --> 00:22:09,000 and they are graduated so the big 451 00:22:09,000 --> 00:22:12,000 disc at the bottom and a slightly smaller one on top and then so on, and they're all stacked up let's say on 452 00:22:12,000 --> 00:22:16,000 tower A. I've labeled them, A, B and C just to keep track of which is which, 453 00:22:16,000 --> 00:22:20,000 and the dyad says yeah, I got all these discs all stacked up on this in A, but it turns out I'd really 454 00:22:20,000 --> 00:22:22,000 much rather have them on tower B. 455 00:22:22,000 --> 00:22:23,000 Sorry. What can you do? I 456 00:22:23,000 --> 00:22:27,000 accidently put them there and I'm so strong and big and heavy I could move 457 00:22:27,000 --> 00:22:30,000 them, you on the other hand, right, puny little human beings that you are, 458 00:22:30,000 --> 00:22:34,000 are restricted to being able to only move one disc at a time because they are so inordinately 459 00:22:34,000 --> 00:22:39,000 heavy that it takes everybody's strength to move just even the smallest of the discs 460 00:22:39,000 --> 00:22:41,000 from one place to another. 461 00:22:41,000 --> 00:22:45,000 And he further in states these rules that the discs all have to live on a spindle so 462 00:22:45,000 --> 00:22:50,000 you can't actually just pick them up and start throwing them around in the desert. 463 00:22:50,000 --> 00:22:53,000 You're trying to move this whole tower from A to B. 464 00:22:53,000 --> 00:22:57,000 You can move one at a time. And in addition, because they're so heavy, if you were ever to put a small disc 465 00:22:57,000 --> 00:23:01,000 on a spindle and put a larger disc on top it would 466 00:23:01,000 --> 00:23:03,000 immediately crush the one underneath it. 467 00:23:03,000 --> 00:23:07,000 So that's disallowed as well. So you always have to keep an ordering of 468 00:23:07,000 --> 00:23:11,000 large ones on the bottom to smaller ones on the top. 469 00:23:11,000 --> 00:23:13,000 All right. That's the deal. That's the set 470 00:23:13,000 --> 00:23:19,000 up. Those trouble-making monks. Apparently, there's 64 of these 471 00:23:19,000 --> 00:23:21,000 things. All right. In computer science, 472 00:23:21,000 --> 00:23:24,000 I don't have any solid gold heavy discs, 473 00:23:24,000 --> 00:23:26,000 but I do have 474 00:23:26,000 --> 00:23:29,000 475 00:23:29,000 --> 00:23:31,000 some very brightly colored plastic 476 00:23:31,000 --> 00:23:35,000 discs. So this is not so much the towers of Brahmin or the towers of [inaudible], I changed 477 00:23:35,000 --> 00:23:36,000 locations somewhere along the 478 00:23:36,000 --> 00:23:40,000 point of history; this is the towers of Fischer Price. 479 00:23:40,000 --> 00:23:42,000 I did not actually steal these from my children, but 480 00:23:42,000 --> 00:23:45,000 they have one at home, which I keep waiting to see them show evidence of their recursive 481 00:23:45,000 --> 00:23:47,000 nature and I must say 482 00:23:47,000 --> 00:23:50,000 very, very disappointing. Okay. 483 00:23:50,000 --> 00:23:54,000 So I've got a tower, in this case, of six. 484 00:23:54,000 --> 00:23:54,000 This is A, 485 00:23:54,000 --> 00:23:56,000 this is B, this is C 486 00:23:56,000 --> 00:23:59,000 and I want to get this from here to here 487 00:23:59,000 --> 00:24:03,000 and I don't want to violate all those rules. I can't just start throwing the discs around and making a 488 00:24:03,000 --> 00:24:08,000 mess. I have to move it from here to here. I don't have a lot of choices here, 489 00:24:08,000 --> 00:24:10,000 but once it's there, for example, this yellow guy 490 00:24:10,000 --> 00:24:14,000 can't go on top of it because it would squash it, right? So I could kind of move yellow in there, so there's something 491 00:24:14,000 --> 00:24:16,000 a little bit about this idea that 492 00:24:16,000 --> 00:24:19,000 somehow there's gonna have to be some back and forth that is a part of what's 493 00:24:19,000 --> 00:24:21,000 going on. 494 00:24:21,000 --> 00:24:23,000 So let's go back and look at this for a second. 495 00:24:23,000 --> 00:24:27,000 So as I said, many of your classic recursive patterns involve sort of looking at the problem you have at hand and 496 00:24:27,000 --> 00:24:31,000 trying to decide is there some way you could separate it a little bit and one of the more 497 00:24:31,000 --> 00:24:36,000 likely ways to do it is say is there some way I can move one disc out of the way leaving N minus 498 00:24:36,000 --> 00:24:37,000 1 499 00:24:37,000 --> 00:24:41,000 that could be worked on recursively? Okay. 500 00:24:41,000 --> 00:24:45,000 So it's probably not likely that I'm gonna be able to get, let's say the blue disc out of the middle very easily, so it seems 501 00:24:45,000 --> 00:24:49,000 like probably the two most likely candidates for that are either the top most disc somehow gets moved out 502 00:24:49,000 --> 00:24:49,000 of the way 503 00:24:49,000 --> 00:24:52,000 to uncover the bottom part 504 00:24:52,000 --> 00:24:55,000 or the bottomless one, somehow I get this other tower out of the way. So let's start by thinking 505 00:24:55,000 --> 00:24:59,000 about the top one because that's certainly the easiest. I can get this top guy, as I said, 506 00:24:59,000 --> 00:25:01,000 and stick it somewhere. 507 00:25:01,000 --> 00:25:05,000 Well, let's say I put it over here in the temporary one. Okay. 508 00:25:05,000 --> 00:25:09,000 I get it out of the way and now I have the tower of N minus 1 left. 509 00:25:09,000 --> 00:25:11,000 Okay. That seems like it's kind 510 00:25:11,000 --> 00:25:12,000 of getting me somewhere 511 00:25:12,000 --> 00:25:15,000 and now I need to move that tower, N minus 512 00:25:15,000 --> 00:25:16,000 1, over here, 513 00:25:16,000 --> 00:25:17,000 but 514 00:25:17,000 --> 00:25:22,000 the situation I made is I've actually made the problem, not easier in the situation, 515 00:25:22,000 --> 00:25:25,000 it's a little bit smaller but it's actually further complicated by the fact that given 516 00:25:25,000 --> 00:25:29,000 this small disc is over here occupying the small spindle 517 00:25:29,000 --> 00:25:33,000 means that, suddenly, this spindle is out of commission. So the purpose of moving this spindle 518 00:25:33,000 --> 00:25:35,000 might as not exact, right, because this guy 519 00:25:35,000 --> 00:25:38,000 is blocking anybody from getting there. So it seems like 520 00:25:38,000 --> 00:25:41,000 I have a problem that looks what I started with, but it's 521 00:25:41,000 --> 00:25:45,000 not actually any easier, in fact, it actually got a little bit harder. So let 522 00:25:45,000 --> 00:25:47,000 me back up from that. Let me just let that be 523 00:25:47,000 --> 00:25:51,000 a dead end for now. What about this purple disc 524 00:25:51,000 --> 00:25:52,000 that is down here on the bottom? 525 00:25:52,000 --> 00:25:55,000 I'd like to get to the purple disc. 526 00:25:55,000 --> 00:25:58,000 Well, I can't just pick up the whole tower and move it, 527 00:25:58,000 --> 00:26:01,000 or can I? 528 00:26:01,000 --> 00:26:02,000 Well, let's think. I've 529 00:26:02,000 --> 00:26:04,000 got this tower of N minus 1 530 00:26:04,000 --> 00:26:08,000 on top of the purple tower. 531 00:26:08,000 --> 00:26:10,000 If 532 00:26:10,000 --> 00:26:14,000 I were able to produce a delegate, a clone, a co-worker, right, 533 00:26:14,000 --> 00:26:15,000 who I could say, Hey, 534 00:26:15,000 --> 00:26:19,000 by the way, you know how to move towers, could you please move the N minus 1 discs 535 00:26:19,000 --> 00:26:21,000 that are on top of the purple one 536 00:26:21,000 --> 00:26:27,000 over to the temporary spindle using this other one 537 00:26:27,000 --> 00:26:29,000 538 00:26:29,000 --> 00:26:31,000 539 00:26:31,000 --> 00:26:36,000 540 00:26:36,000 --> 00:26:40,000 as the 541 00:26:40,000 --> 00:26:41,000 542 00:26:41,000 --> 00:26:45,000 spare? Well, 543 00:26:45,000 --> 00:26:48,000 that's kind of interesting. 544 00:26:48,000 --> 00:26:48,000 545 00:26:48,000 --> 00:26:54,000 So if I could move that N minus 1 out of my way and over to that temporary spindle, 546 00:26:54,000 --> 00:26:57,000 then it would uncover this bottomless one 547 00:26:57,000 --> 00:27:02,000 which then is one step away from where it wants to be; it wants to move to the middle. 548 00:27:02,000 --> 00:27:06,000 549 00:27:06,000 --> 00:27:10,000 550 00:27:10,000 --> 00:27:13,000 551 00:27:13,000 --> 00:27:16,000 552 00:27:16,000 --> 00:27:17,000 553 00:27:17,000 --> 00:27:19,000 554 00:27:19,000 --> 00:27:22,000 555 00:27:22,000 --> 00:27:25,000 556 00:27:25,000 --> 00:27:26,000 557 00:27:26,000 --> 00:27:30,000 558 00:27:30,000 --> 00:27:33,000 559 00:27:33,000 --> 00:27:36,000 560 00:27:36,000 --> 00:27:39,000 561 00:27:39,000 --> 00:27:43,000 So this is really where recursions are kind 562 00:27:43,000 --> 00:27:45,000 of buying us a lot of 563 00:27:45,000 --> 00:27:47,000 the heavy lifting. 564 00:27:47,000 --> 00:27:49,000 I want to get this tower from here to there. 565 00:27:49,000 --> 00:27:53,000 There's all these rules. It's very complicated. I can't think about it, it makes my head hurt, but 566 00:27:53,000 --> 00:27:55,000 if I just believed that 567 00:27:55,000 --> 00:27:58,000 I was in the midst of solving this problem that I haven't yet solved 568 00:27:58,000 --> 00:28:03,000 and if I had that solution and I believed and I had faith, right, and I believe 569 00:28:03,000 --> 00:28:04,000 that it will work, 570 00:28:04,000 --> 00:28:06,000 I move these guys out of the way, 571 00:28:06,000 --> 00:28:08,000 I move this over here, 572 00:28:08,000 --> 00:28:11,000 I move it back. 573 00:28:11,000 --> 00:28:14,000 So let's see how much I can do without blowing it. 574 00:28:14,000 --> 00:28:16,000 All done. Don't ask to see it 575 00:28:16,000 --> 00:28:18,000 again. 576 00:28:18,000 --> 00:28:23,000 I'll show you 577 00:28:23,000 --> 00:28:26,000 a 578 00:28:26,000 --> 00:28:28,000 579 00:28:28,000 --> 00:28:29,000 little 580 00:28:29,000 --> 00:28:31,000 code. 581 00:28:31,000 --> 00:28:35,000 I'll 582 00:28:35,000 --> 00:28:37,000 583 00:28:37,000 --> 00:28:40,000 584 00:28:40,000 --> 00:28:42,000 show 585 00:28:42,000 --> 00:28:46,000 you 586 00:28:46,000 --> 00:28:50,000 587 00:28:50,000 --> 00:29:01,000 588 00:29:01,000 --> 00:29:03,000 the 589 00:29:03,000 --> 00:29:05,000 code. 590 00:29:05,000 --> 00:29:07,000 591 00:29:07,000 --> 00:29:09,000 592 00:29:09,000 --> 00:29:10,000 Tiny, 593 00:29:10,000 --> 00:29:13,000 tiny little piece of code 594 00:29:13,000 --> 00:29:16,000 that solves the whole problem. 595 00:29:16,000 --> 00:29:19,000 I've got a [inaudible] coming in here, which is the height of the tower to move 596 00:29:19,000 --> 00:29:23,000 and I'm identifying the source destination attempt, the three spindles that are 597 00:29:23,000 --> 00:29:27,000 currently in play here with these letters, characters; 598 00:29:27,000 --> 00:29:31,000 if there's something to move - so I'm gonna talk about the base case in a second, but in 599 00:29:31,000 --> 00:29:36,000 the general case where I've got five things to move it says move the four discs 600 00:29:36,000 --> 00:29:38,000 that are on the source. 601 00:29:38,000 --> 00:29:40,000 So the source, let's say is A in this case, 602 00:29:40,000 --> 00:29:44,000 and now instead of moving them to the destination, move them aside to the temporary spindle 603 00:29:44,000 --> 00:29:47,000 using the destination as the temporary. 604 00:29:47,000 --> 00:29:49,000 Once you've gotten those out of the way, 605 00:29:49,000 --> 00:29:52,000 you move that single disc, the bottom of the disc from the source of the destination, 606 00:29:52,000 --> 00:29:55,000 and then you go pick up N minus 1 tower you left on temporary 607 00:29:55,000 --> 00:30:00,000 and stack it on top of you in the destination now using the source as your temporary. At 608 00:30:00,000 --> 00:30:04,000 any given stage, you've got three to go and then you have to move the tower of height off of you. When 609 00:30:04,000 --> 00:30:07,000 you've got two to go, you have to move the tower of height of 1 off you. 610 00:30:07,000 --> 00:30:12,000 Base case you could imagine being pretty easy while single height tower, 611 00:30:12,000 --> 00:30:14,000 just one disc, could be exactly moved, 612 00:30:14,000 --> 00:30:17,000 this actually prefers going to even a simpler case, right, which is 613 00:30:17,000 --> 00:30:20,000 if you're asking to move a zero height tower there's nothing to do. 614 00:30:20,000 --> 00:30:24,000 In fact, the base case for the zero is if N equals zero, do nothing 615 00:30:24,000 --> 00:30:27,000 for any positive number then it goes through the process of 616 00:30:27,000 --> 00:30:28,000 shuffling the 617 00:30:28,000 --> 00:30:31,000 ones off of you to uncover your bottomless disc 618 00:30:31,000 --> 00:30:33,000 and then moving them back on. 619 00:30:33,000 --> 00:30:36,000 So five little lines 620 00:30:36,000 --> 00:30:40,000 and all the power in the world. Question? 621 00:30:40,000 --> 00:30:43,000 Student:Why use the 622 00:30:43,000 --> 00:30:48,000 destination as a temporary? Instructor (Julie Zelenski):The idea is that if we're moving here from A 623 00:30:48,000 --> 00:30:49,000 to B, right, 624 00:30:49,000 --> 00:30:51,000 I need to leave this one open, 625 00:30:51,000 --> 00:30:54,000 right, so that I'll be able to move the purple one when the time comes. So I'm trying to move 626 00:30:54,000 --> 00:30:56,000 this out of the way, 627 00:30:56,000 --> 00:30:58,000 right, so here's where it's trying to go 628 00:30:58,000 --> 00:31:01,000 and in the process, right, you have these two places you can kind of shuffle things back and 629 00:31:01,000 --> 00:31:04,000 forth, where they came from, where they're not going and where they are going, 630 00:31:04,000 --> 00:31:05,000 631 00:31:05,000 --> 00:31:06,000 632 00:31:06,000 --> 00:31:09,000 so there's also the source of destination and it's pretty obvious; and then what happens 633 00:31:09,000 --> 00:31:13,000 is that whatever is left over is the one that gets used as a temp. Student:Why can't you 634 00:31:13,000 --> 00:31:15,000 put those on the second one? Instructor (Julie Zelenski):Well, if 635 00:31:15,000 --> 00:31:19,000 I put them on the second one, how am I gonna get the purple one underneath them? 636 00:31:19,000 --> 00:31:22,000 Student:Well, you wanted to put them on the last one. Instructor (Julie Zelenski):Well, my plan was to move from A to B actually. It 637 00:31:22,000 --> 00:31:24,000 doesn't really matter. Student:Oh, okay. Instructor (Julie Zelenski):I'm trying 638 00:31:24,000 --> 00:31:29,000 to move from A to B so in fact, C is the place where I'm just leaving stuff 639 00:31:29,000 --> 00:31:33,000 640 00:31:33,000 --> 00:31:37,000 temporarily. 641 00:31:37,000 --> 00:31:42,000 642 00:31:42,000 --> 00:31:46,000 Student:Okay. Instructor 643 00:31:46,000 --> 00:31:48,000 (Julie 644 00:31:48,000 --> 00:31:51,000 Zelenski):So you're 645 00:31:51,000 --> 00:31:52,000 646 00:31:52,000 --> 00:32:03,000 647 00:32:03,000 --> 00:32:05,000 648 00:32:05,000 --> 00:32:07,000 gonna see 649 00:32:07,000 --> 00:32:11,000 that 650 00:32:11,000 --> 00:32:13,000 the 651 00:32:13,000 --> 00:32:16,000 stack 652 00:32:16,000 --> 00:32:18,000 frames 653 00:32:18,000 --> 00:32:22,000 here show how deep the 654 00:32:22,000 --> 00:32:25,000 recursion ever gets at any given point, right, at this case, having four discs it gets about 655 00:32:25,000 --> 00:32:26,000 four deep, 656 00:32:26,000 --> 00:32:29,000 actually five because it goes to the zero case 657 00:32:29,000 --> 00:32:32,000 and that you'll see it kind of go down and back 658 00:32:32,000 --> 00:32:33,000 as it shows it kind of 659 00:32:33,000 --> 00:32:37,000 moving the tower away and then getting back to moving the bottomless disc and then 660 00:32:37,000 --> 00:32:38,000 doing another 661 00:32:38,000 --> 00:32:42,000 deep recursion to move that tower back on top. 662 00:32:42,000 --> 00:32:46,000 And so at any given stage, right, they're all stacked up and the start/finish attempts start 663 00:32:46,000 --> 00:32:50,000 switching positions depending on what level of the recursion we're at. 664 00:32:50,000 --> 00:32:54,000 Each time we get to zero we hit our base case and unwind. Let me 665 00:32:54,000 --> 00:32:59,000 make it go a little bit faster because it's 666 00:32:59,000 --> 00:33:03,000 a little bit slow. Student:[Inaudible] Instructor (Julie Zelenski):[Inaudible]. All right. So I just moved the tower of height three all the way away and now let's move the bottomless one 667 00:33:03,000 --> 00:33:04,000 back 668 00:33:04,000 --> 00:33:05,000 and now it's gonna start moving 669 00:33:05,000 --> 00:33:07,000 the 670 00:33:07,000 --> 00:33:11,000 tower that was shuffled away back on to it 671 00:33:11,000 --> 00:33:19,000 and then it will eventually stack it back up on the B where it wants to go. I can make him 672 00:33:19,000 --> 00:33:23,000 move the tower. Student:Sixty-four. 673 00:33:23,000 --> 00:33:25,000 Instructor 674 00:33:25,000 --> 00:33:30,000 (Julie Zelenski):Yeah. Sixty-four. We'll talk a little bit about why I wouldn't want to put in the number 64. You 675 00:33:30,000 --> 00:33:31,000 can see I'm kind of it around. 676 00:33:31,000 --> 00:33:34,000 Dancing, dancing, much better than I would do. 677 00:33:34,000 --> 00:33:47,000 I actually maintained the rules at all times. No discs getting smashed. I go up to six and 678 00:33:47,000 --> 00:33:50,000 so never getting lost, always keeping track of what it's up to, right, it's a very tricky 679 00:33:50,000 --> 00:33:54,000 thing for a human to do, but a very easy thing for a computer to be able to identify what part of the recursion 680 00:33:54,000 --> 00:33:57,000 we're at and what we're trying to do right now without 681 00:33:57,000 --> 00:34:01,000 getting confused about the other things that are also kind of ongoing. They're all 682 00:34:01,000 --> 00:34:03,000 very neatly 683 00:34:03,000 --> 00:34:04,000 kept apart. 684 00:34:04,000 --> 00:34:06,000 685 00:34:06,000 --> 00:34:10,000 686 00:34:10,000 --> 00:34:12,000 687 00:34:12,000 --> 00:34:21,000 688 00:34:21,000 --> 00:34:24,000 689 00:34:24,000 --> 00:34:27,000 690 00:34:27,000 --> 00:34:33,000 691 00:34:33,000 --> 00:34:34,000 692 00:34:34,000 --> 00:34:36,000 693 00:34:36,000 --> 00:34:38,000 694 00:34:38,000 --> 00:34:42,000 695 00:34:42,000 --> 00:34:44,000 696 00:34:44,000 --> 00:34:45,000 697 00:34:45,000 --> 00:34:48,000 698 00:34:48,000 --> 00:34:51,000 699 00:34:51,000 --> 00:34:55,000 700 00:34:55,000 --> 00:34:57,000 701 00:34:57,000 --> 00:35:02,000 702 00:35:02,000 --> 00:35:04,000 703 00:35:04,000 --> 00:35:08,000 704 00:35:08,000 --> 00:35:13,000 705 00:35:13,000 --> 00:35:18,000 706 00:35:18,000 --> 00:35:20,000 So 707 00:35:20,000 --> 00:35:24,000 when 708 00:35:24,000 --> 00:35:27,000 709 00:35:27,000 --> 00:35:30,000 710 00:35:30,000 --> 00:35:32,000 711 00:35:32,000 --> 00:35:35,000 712 00:35:35,000 --> 00:35:39,000 people 713 00:35:39,000 --> 00:35:41,000 714 00:35:41,000 --> 00:35:43,000 will 715 00:35:43,000 --> 00:35:47,000 ask 716 00:35:47,000 --> 00:35:53,000 717 00:35:53,000 --> 00:35:54,000 718 00:35:54,000 --> 00:35:58,000 you 719 00:35:58,000 --> 00:36:02,000 720 00:36:02,000 --> 00:36:04,000 721 00:36:04,000 --> 00:36:06,000 about recursion, 722 00:36:06,000 --> 00:36:09,000 everyone will want to know have you been exposed to the 723 00:36:09,000 --> 00:36:13,000 towers problem, and now, you have. So 724 00:36:13,000 --> 00:36:16,000 very powerful little piece of code, right, 725 00:36:16,000 --> 00:36:18,000 and it feels very much like a trick. 726 00:36:18,000 --> 00:36:23,000 I can remember sitting in a room, not unlike yourselves, a gazillion years ago 727 00:36:23,000 --> 00:36:26,000 and having someone explain the towers of Hanoi to me 728 00:36:26,000 --> 00:36:28,000 and just not believing. 729 00:36:28,000 --> 00:36:32,000 Just saying that can't work. You didn't do anything. All you did 730 00:36:32,000 --> 00:36:35,000 was call yourself before you were even done and that's just nonsense and 731 00:36:35,000 --> 00:36:36,000 that's just not right. 732 00:36:36,000 --> 00:36:37,000 733 00:36:37,000 --> 00:36:39,000 And then after some amount of 734 00:36:39,000 --> 00:36:41,000 thinking about it 735 00:36:41,000 --> 00:36:45,000 and working it through, I did conclude that it actually did work, but at first, it really did 736 00:36:45,000 --> 00:36:46,000 seem like a trick. So 737 00:36:46,000 --> 00:36:49,000 if you're feeling that way, this is 738 00:36:49,000 --> 00:36:51,000 par for the course. It is 739 00:36:51,000 --> 00:36:53,000 a little wacky to get your head around, 740 00:36:53,000 --> 00:36:57,000 but it is sort of relying on this idea of the mathematical induction; if you can do it for 741 00:36:57,000 --> 00:36:59,000 the smaller version of the problem 742 00:36:59,000 --> 00:37:00,000 and then 743 00:37:00,000 --> 00:37:02,000 build on that to solve the bigger problem, 744 00:37:02,000 --> 00:37:07,000 as long as you make that logical progression from this problem to the smaller one down to that 745 00:37:07,000 --> 00:37:12,000 simple case, you will eventually solve the whole thing. Student:[Inaudible] Instructor (Julie 746 00:37:12,000 --> 00:37:18,000 Zelenski):Source destination in this case. Okay. So then there are 747 00:37:18,000 --> 00:37:23,000 two problems I want to do. I'll probably only do one today and I'll do one on Friday 748 00:37:23,000 --> 00:37:29,000 that are what I think of as the mother problems of all recursions 749 00:37:29,000 --> 00:37:35,000 that many, many problems in the end just boil down to an instance of either the permutations 750 00:37:35,000 --> 00:37:37,000 problem or the subset problem. 751 00:37:37,000 --> 00:37:41,000 So I'm gonna show you permutations and subsets sort of in gory detail and then I'll try 752 00:37:41,000 --> 00:37:44,000 to build with you about how many things actually are just a permutations problem 753 00:37:44,000 --> 00:37:49,000 or subset problem when looked at the right way and so once you kind of have these two in your arsenal, 754 00:37:49,000 --> 00:37:54,000 you're very much prepared to attack a lot of different recursion things using those same 755 00:37:54,000 --> 00:37:55,000 patterns. 756 00:37:55,000 --> 00:37:58,000 So the one I'm looking at here is permutations. 757 00:37:58,000 --> 00:38:01,000 You have an input string, let's say it's the alphabet A 758 00:38:01,000 --> 00:38:03,000 through Z, 26 letters, 759 00:38:03,000 --> 00:38:06,000 what you'd like to do is enumerate or print or list 760 00:38:06,000 --> 00:38:08,000 all of the ways you could permute the alphabet. 761 00:38:08,000 --> 00:38:10,000 So there's 26 letters in the alphabet, 762 00:38:10,000 --> 00:38:14,000 if you know anything about combinations and permutations, you realize there's 763 00:38:14,000 --> 00:38:17,000 26 ways you can choose the first letters, A, B, C, all the way to Z 764 00:38:17,000 --> 00:38:21,000 and then that leaves you with 25 letters from which to pick the next one, right, so there's 25 765 00:38:21,000 --> 00:38:22,000 ways to do that 766 00:38:22,000 --> 00:38:24,000 and then 24 ways to pick after that 767 00:38:24,000 --> 00:38:29,000 and so at each step you have one fewer choices remaining to conclude the 768 00:38:29,000 --> 00:38:30,000 permutation; 769 00:38:30,000 --> 00:38:34,000 and then the number of permutations is then factorials in the length of the input, so 770 00:38:34,000 --> 00:38:37,000 26 factorial, which is an enormous number. It 771 00:38:37,000 --> 00:38:40,000 tells you about all the different ways you could rearrange the alphabet. 772 00:38:40,000 --> 00:38:42,000 For a smaller string, you know, A, B, C, right, 773 00:38:42,000 --> 00:38:46,000 there are three factorials for that, six different ways you could permute that. 774 00:38:46,000 --> 00:38:51,000 The same principle applies no matter how large the string is. So 775 00:38:51,000 --> 00:38:53,000 our goal is 776 00:38:53,000 --> 00:38:56,000 to write a function that, given an input string, 777 00:38:56,000 --> 00:39:00,000 will print all of the permutations of that string. 778 00:39:00,000 --> 00:39:03,000 That's the goal. Okay. 779 00:39:03,000 --> 00:39:07,000 So I've got A, B, C, D coming in, I want to be able to print D, C, B, A and C, 780 00:39:07,000 --> 00:39:11,000 A B, D and all these other variations. 781 00:39:11,000 --> 00:39:16,000 I'm gonna use the strategy that actually I described just the way I did kind of intuitively about 782 00:39:16,000 --> 00:39:19,000 how permutations are constructed. 783 00:39:19,000 --> 00:39:23,000 That at any given point, right, I have a choice to make, and that choice in this 784 00:39:23,000 --> 00:39:27,000 case, will be what's the next letter to attach to the permutations. So if I measure my goal by trying to build 785 00:39:27,000 --> 00:39:29,000 the permutation up one letter at a time. 786 00:39:29,000 --> 00:39:33,000 I start with an empty string so I'm gonna have the input and the output. The input is the letters 787 00:39:33,000 --> 00:39:34,000 I haven't yet 788 00:39:34,000 --> 00:39:35,000 used, so 789 00:39:35,000 --> 00:39:39,000 in the case of the string, A, B, C, it might be the whole string, A, B, C. 790 00:39:39,000 --> 00:39:41,000 I've got this output, which is what letters I've chosen so far. 791 00:39:41,000 --> 00:39:43,000 It starts empty. 792 00:39:43,000 --> 00:39:45,000 I look at my A, B, C and I say, Well, 793 00:39:45,000 --> 00:39:47,000 each of those letters 794 00:39:47,000 --> 00:39:49,000 could be the next one that's here, 795 00:39:49,000 --> 00:39:52,000 why don't I go ahead and pick one, 796 00:39:52,000 --> 00:39:54,000 pick A for that matter, 797 00:39:54,000 --> 00:39:55,000 put it on the output 798 00:39:55,000 --> 00:39:56,000 and then 799 00:39:56,000 --> 00:40:01,000 recursively call myself to say well given A is in the front, because you also print all 800 00:40:01,000 --> 00:40:03,000 the things that 801 00:40:03,000 --> 00:40:06,000 you can permute the remaining letters, B, C, behind it. 802 00:40:06,000 --> 00:40:10,000 After the magic recursion has done what it's gonna do 803 00:40:10,000 --> 00:40:11,000 I can 804 00:40:11,000 --> 00:40:13,000 come back to the call I was at 805 00:40:13,000 --> 00:40:17,000 and say okay, well, now it's not just A in the front I need to try; I also need to try B in the front. 806 00:40:17,000 --> 00:40:20,000 So I tried B in the front and now permute the A, C, that I leave behind. 807 00:40:20,000 --> 00:40:24,000 I try C in the front and permute the A, B, that's left behind. 808 00:40:24,000 --> 00:40:27,000 So at any given stage of this recursion, right, I have 809 00:40:27,000 --> 00:40:30,000 these options, which are of all the letters remaining in the input, 810 00:40:30,000 --> 00:40:33,000 each of them needs to be tried as the next one to go 811 00:40:33,000 --> 00:40:36,000 and then I need to recursively permute 812 00:40:36,000 --> 00:40:39,000 on this slightly smaller form of the same problem where 813 00:40:39,000 --> 00:40:40,000 the 814 00:40:40,000 --> 00:40:44,000 output is one shorter of. I've removed one letter from consideration because I've picked it 815 00:40:44,000 --> 00:40:48,000 and the input is one longer. So at each level of the recursion, one letter is shuffled from 816 00:40:48,000 --> 00:40:50,000 the output to the input 817 00:40:50,000 --> 00:40:53,000 after I've done that N times, right, I will have created a permutation and then I can just 818 00:40:53,000 --> 00:40:54,000 print it. 819 00:40:54,000 --> 00:40:55,000 820 00:40:55,000 --> 00:40:59,000 821 00:40:59,000 --> 00:41:03,000 822 00:41:03,000 --> 00:41:05,000 823 00:41:05,000 --> 00:41:06,000 824 00:41:06,000 --> 00:41:07,000 825 00:41:07,000 --> 00:41:11,000 826 00:41:11,000 --> 00:41:14,000 So I've talked about this. Let me just show you the code because I think that 827 00:41:14,000 --> 00:41:18,000 is where we can spend the most time illuminating what's trying to go on. So here's 828 00:41:18,000 --> 00:41:20,000 recursive permute. 829 00:41:20,000 --> 00:41:25,000 The form that I'm gonna use here is gonna take two arguments. I'll 830 00:41:25,000 --> 00:41:29,000 explain the need for it in a second, but largely what I'm gonna be tracking is that input and 831 00:41:29,000 --> 00:41:34,000 output. What I have assembled so far is in that first parameter, so the things I have 832 00:41:34,000 --> 00:41:36,000 committed in the permutation I'm building right now, 833 00:41:36,000 --> 00:41:41,000 the rest is those letters that haven't been chosen that have been passed over so far 834 00:41:41,000 --> 00:41:43,000 that are remaining to be permuted 835 00:41:43,000 --> 00:41:47,000 and attached on to so far. 836 00:41:47,000 --> 00:41:49,000 If the rest is empty, 837 00:41:49,000 --> 00:41:55,000 that means everything has been attached in so far, I have a permutation and then I just print it. If 838 00:41:55,000 --> 00:41:58,000 it's not empty, 839 00:41:58,000 --> 00:42:01,000 then for every letter 840 00:42:01,000 --> 00:42:04,000 that remains in the rest - so 841 00:42:04,000 --> 00:42:07,000 imagine I'm starting with the whole alphabet and so far was 842 00:42:07,000 --> 00:42:08,000 empty, 843 00:42:08,000 --> 00:42:11,000 this four loop is going to iterate 26 times, 844 00:42:11,000 --> 00:42:14,000 it's going to take out the [inaudible] character 845 00:42:14,000 --> 00:42:17,000 and it's gonna append it to the permutation 846 00:42:17,000 --> 00:42:20,000 and then it's gonna remove it from 847 00:42:20,000 --> 00:42:22,000 the rest 848 00:42:22,000 --> 00:42:27,000 to show that it's been used so we won't accidently 849 00:42:27,000 --> 00:42:29,000 repeat it later in the permutation. 850 00:42:29,000 --> 00:42:31,000 And then we make this recursive call saying 851 00:42:31,000 --> 00:42:34,000 okay, now having picked the letter N and put it in the front, 852 00:42:34,000 --> 00:42:38,000 853 00:42:38,000 --> 00:42:42,000 here's the whole alphabet without 854 00:42:42,000 --> 00:42:46,000 855 00:42:46,000 --> 00:42:51,000 856 00:42:51,000 --> 00:42:52,000 857 00:42:52,000 --> 00:42:54,000 858 00:42:54,000 --> 00:42:59,000 859 00:42:59,000 --> 00:42:59,000 860 00:42:59,000 --> 00:43:04,000 861 00:43:04,000 --> 00:43:06,000 862 00:43:06,000 --> 00:43:07,000 N. 863 00:43:07,000 --> 00:43:08,000 864 00:43:08,000 --> 00:43:13,000 865 00:43:13,000 --> 00:43:21,000 So 866 00:43:21,000 --> 00:43:27,000 at the beginning 867 00:43:27,000 --> 00:43:28,000 we have 868 00:43:28,000 --> 00:43:35,000 everything in the input, nothing in the output. Well, once we pick something 869 00:43:35,000 --> 00:43:40,000 that shuffles on character from here to there. A subsequent call down here 870 00:43:40,000 --> 00:43:43,000 moves another character 871 00:43:43,000 --> 00:43:48,000 and then eventually 872 00:43:48,000 --> 00:43:50,000 we've emptied out the rest. 873 00:43:50,000 --> 00:43:55,000 There are other alternatives though, for example, up here it could be that we picked B and 874 00:43:55,000 --> 00:43:57,000 left behind A, C, 875 00:43:57,000 --> 00:44:01,000 it could be that we picked C and left behind A, 876 00:44:01,000 --> 00:44:05,000 B. Before it's all done, we're gonna have to try all of those things and so 877 00:44:05,000 --> 00:44:09,000 the very first level of the recursion is gonna make a number of calls equal to the length of the 878 00:44:09,000 --> 00:44:12,000 input. Each subsequent level, right, 879 00:44:12,000 --> 00:44:13,000 in here makes 880 00:44:13,000 --> 00:44:15,000 one fewer call at each branch. 881 00:44:15,000 --> 00:44:20,000 So if I had a 26 at the top, each of those 26 then makes a 25 underneath 882 00:44:20,000 --> 00:44:23,000 so there's 26 25s branching down there 883 00:44:23,000 --> 00:44:27,000 and then each of the 25 makes a 24. So this is an enormously wide tree. 884 00:44:27,000 --> 00:44:30,000 The depth is bounded by 885 00:44:30,000 --> 00:44:32,000 the total number of characters, 886 00:44:32,000 --> 00:44:35,000 but very, very wide. 887 00:44:35,000 --> 00:44:36,000 I'm just 888 00:44:36,000 --> 00:44:39,000 gonna show you a little part of the tree to get an idea. 889 00:44:39,000 --> 00:44:42,000 If I'm permuting A, B, C, D in 890 00:44:42,000 --> 00:44:44,000 the so far for the input, 891 00:44:44,000 --> 00:44:45,000 892 00:44:45,000 --> 00:44:48,000 [inaudible] starts empty 893 00:44:48,000 --> 00:44:50,000 and there are four calls that are being made, 894 00:44:50,000 --> 00:44:54,000 first with A, then with B, then with C, then with D and in each case, removing that 895 00:44:54,000 --> 00:44:59,000 letter from what remains and then exploring. So if I kind of further expand this call, 896 00:44:59,000 --> 00:45:00,000 it makes three calls, right, 897 00:45:00,000 --> 00:45:03,000 one having pulling B to attach on, 898 00:45:03,000 --> 00:45:06,000 one having attached C on, and one having attached D 899 00:45:06,000 --> 00:45:09,000 on leaving the remaining two characters. 900 00:45:09,000 --> 00:45:12,000 And then underneath that, picking that third character 901 00:45:12,000 --> 00:45:15,000 and then eventually pocking the fourth character which there's no choices there. So 902 00:45:15,000 --> 00:45:18,000 this is only a partial part of the tree, 903 00:45:18,000 --> 00:45:21,000 but it gives you an idea of what the shape of that recursion looks like. 904 00:45:21,000 --> 00:45:24,000 905 00:45:24,000 --> 00:45:28,000 906 00:45:28,000 --> 00:45:30,000 907 00:45:30,000 --> 00:45:31,000 908 00:45:31,000 --> 00:45:33,000 909 00:45:33,000 --> 00:45:37,000 910 00:45:37,000 --> 00:45:38,000 911 00:45:38,000 --> 00:45:41,000 912 00:45:41,000 --> 00:45:43,000 913 00:45:43,000 --> 00:45:47,000 914 00:45:47,000 --> 00:45:49,000 915 00:45:49,000 --> 00:45:53,000 916 00:45:53,000 --> 00:45:58,000 917 00:45:58,000 --> 00:46:05,000 918 00:46:05,000 --> 00:46:08,000 This is a 919 00:46:08,000 --> 00:46:10,000 tricky thing to get your head around. 920 00:46:10,000 --> 00:46:12,000 But it is a 921 00:46:12,000 --> 00:46:14,000 critical pattern 922 00:46:14,000 --> 00:46:16,000 923 00:46:16,000 --> 00:46:20,000 to get in your arsenals to you know how to apply it. So what this is sort of that choice pattern, 924 00:46:20,000 --> 00:46:21,000 right; 925 00:46:21,000 --> 00:46:23,000 of the choices I have, 926 00:46:23,000 --> 00:46:27,000 I need to go through the process of making those choices, updating my state to show that 927 00:46:27,000 --> 00:46:31,000 choice has been made and then recursing from there - making that recursive call to 928 00:46:31,000 --> 00:46:32,000 929 00:46:32,000 --> 00:46:36,000 further explore whatever choices remain having made this one, which caused there to be one fewer 930 00:46:36,000 --> 00:46:40,000 choices to be made. And in a permutation, you have to make 26 choices, right, for the alphabet. 931 00:46:40,000 --> 00:46:43,000 Well, you make one and then you have 25 to go, you make one, you have 24 to go. Each of 932 00:46:43,000 --> 00:46:46,000 those calls, right, is working its way down. 933 00:46:46,000 --> 00:46:49,000 There's one little detail I'll mention and then we'll finish on Friday, which is 934 00:46:49,000 --> 00:46:53,000 that probably the way this function would be presented to a client or a user 935 00:46:53,000 --> 00:46:57,000 who wanted to get the permutations is it makes more sense for them to say here's the string I have, 936 00:46:57,000 --> 00:46:59,000 could you please just list the permutations. 937 00:46:59,000 --> 00:47:03,000 This notion that somehow I need to track what I've generated so far is very much an internal 938 00:47:03,000 --> 00:47:05,000 housekeeping part 939 00:47:05,000 --> 00:47:08,000 and so it effects permutations to look like this 940 00:47:08,000 --> 00:47:12,000 and then just immediately turn around and make a call to the real recursive function that set up the state, 941 00:47:12,000 --> 00:47:15,000 the housekeeping that was being tracked through it, 942 00:47:15,000 --> 00:47:17,000 so we'll call this thing a wrapper function. 943 00:47:17,000 --> 00:47:21,000 All it is one line of code that just sets up the right state to get the recursion 944 00:47:21,000 --> 00:47:22,000 going and kind of 945 00:47:22,000 --> 00:47:24,000 state managed. 946 00:47:24,000 --> 00:47:27,000 We will see that quite a lot in a lot of codes. They just know about it. 947 00:47:27,000 --> 00:47:29,000 Come Friday, we'll talk about subsets 948 00:47:29,000 --> 00:47:30,000 and then we'll 949 00:47:30,000 --> 00:47:35,000 start looking at recursive backtracking.