1 00:00:00,000 --> 00:00:08,000 2 00:00:08,000 --> 00:00:11,000 3 00:00:11,000 --> 00:00:15,000 This presentation is delivered by the Stanford Center for Professional Development. 4 00:00:15,000 --> 00:00:24,000 5 00:00:24,000 --> 00:00:26,000 Good afternoon. 6 00:00:26,000 --> 00:00:29,000 You guys are talkative. 7 00:00:29,000 --> 00:00:32,000 So we talked just a little bit about the vocabulary of recursion at the 8 00:00:32,000 --> 00:00:36,000 end of Friday. It was very rushed for time, so I'm 9 00:00:36,000 --> 00:00:40,000 just gonna repeat some of those words to get us thinking about what the 10 00:00:40,000 --> 00:00:42,000 context for solving problems recursively looks like. And then we're gonna go along and 11 00:00:42,000 --> 00:00:45,000 do a lot of examples [cuts out]. 12 00:00:45,000 --> 00:00:48,000 So the idea is that a recursive function is one that calls itself. 13 00:00:48,000 --> 00:00:51,000 That's really all it means 14 00:00:51,000 --> 00:00:54,000 at the most trivial level. It says that in the context of writing a 15 00:00:54,000 --> 00:00:56,000 function binky, it's gonna make a call 16 00:00:56,000 --> 00:01:00,000 or one or more calls to binky itself past 17 00:01:00,000 --> 00:01:03,000 an argument as part of solving or doing some task. 18 00:01:03,000 --> 00:01:04,000 The idea is that 19 00:01:04,000 --> 00:01:08,000 we're using that because the problem itself has some self-similarity where the 20 00:01:08,000 --> 00:01:11,000 answer I was seeking - so the idea of surveying the whole campus can actually be thought of as well if 21 00:01:11,000 --> 00:01:14,000 I could get somebody to survey this part of campus and this part of campus, 22 00:01:14,000 --> 00:01:17,000 somebody to survey all the freshmen, somebody to [cuts out] 23 00:01:17,000 --> 00:01:18,000 and whatnot, 24 00:01:18,000 --> 00:01:21,000 that those in a sense are - those surveys are just smaller instances of the same kind 25 00:01:21,000 --> 00:01:24,000 of problem I was originally trying to solve. And 26 00:01:24,000 --> 00:01:26,000 if I could recursively 27 00:01:26,000 --> 00:01:30,000 delegate those things out, and then they themselves may in turn delegate even 28 00:01:30,000 --> 00:01:32,000 further to smaller but same 29 00:01:32,000 --> 00:01:36,000 structured problems to where we could eventually get to something so simple - in 30 00:01:36,000 --> 00:01:40,000 that case of asking ten people for their input 31 00:01:40,000 --> 00:01:44,000 that don't require any further decomposition - we will have worked our way to this base 32 00:01:44,000 --> 00:01:48,000 case that then we can gather back up all the results and solve the whole thing. 33 00:01:48,000 --> 00:01:51,000 This is gonna feel very mysterious at first, 34 00:01:51,000 --> 00:01:53,000 and some of the examples I give you'll say I have 35 00:01:53,000 --> 00:01:56,000 really easy alternatives other than recursion, so it's not gonna seem worth 36 00:01:56,000 --> 00:01:58,000 the pain of trying to get your head around it. 37 00:01:58,000 --> 00:02:03,000 But eventually, we're gonna work our way up to problems where recursion really is the right solution, 38 00:02:03,000 --> 00:02:06,000 and there are no other alternatives that are obvious or simple 39 00:02:06,000 --> 00:02:07,000 to do. 40 00:02:07,000 --> 00:02:07,000 So the 41 00:02:07,000 --> 00:02:11,000 idea throughout this week is actually just a lot of practice. Telling you 42 00:02:11,000 --> 00:02:13,000 what the terms mean I think is not actually gonna help you understand it. I think what you 43 00:02:13,000 --> 00:02:18,000 need to see is examples. So I'm gonna be doing four or five examples today, four or five 44 00:02:18,000 --> 00:02:20,000 examples on Wednesday, and four or five examples on Friday 45 00:02:20,000 --> 00:02:22,000 that each kind of 46 00:02:22,000 --> 00:02:25,000 build on each other, kind of take the ideas 47 00:02:25,000 --> 00:02:27,000 and get a little more sophisticated. 48 00:02:27,000 --> 00:02:28,000 But 49 00:02:28,000 --> 00:02:31,000 by the end of the week, I'm hoping that you're gonna start to see these patterns, and realize 50 00:02:31,000 --> 00:02:35,000 that in some sense the recursive solutions tend to be more alike than different. 51 00:02:35,000 --> 00:02:37,000 Once you have your head around how to solve 52 00:02:37,000 --> 00:02:41,000 one type of problem, you may very well be able to take the exact same technique 53 00:02:41,000 --> 00:02:43,000 and solve several other problems that 54 00:02:43,000 --> 00:02:46,000 may sound different at first glance, but in the end, the recursive structure looks the 55 00:02:46,000 --> 00:02:47,000 same. 56 00:02:47,000 --> 00:02:54,000 So I'd say just hold the discomfort a little bit, and wait to see as 57 00:02:54,000 --> 00:02:57,000 we keep working which example may be the one that kind of sticks out for you to 58 00:02:57,000 --> 00:02:59,000 help you get it through. 59 00:02:59,000 --> 00:03:02,000 So we're gonna start with things that fit in the category of 60 00:03:02,000 --> 00:03:03,000 functional recursion. 61 00:03:03,000 --> 00:03:05,000 The functional in this case just says that 62 00:03:05,000 --> 00:03:09,000 you're writing functions that return some non-void thing, an integer, a string, 63 00:03:09,000 --> 00:03:10,000 some 64 00:03:10,000 --> 00:03:12,000 vector of results, or whatever that is, 65 00:03:12,000 --> 00:03:14,000 and that's all it means to be a functional recursion. It's a recursive 66 00:03:14,000 --> 00:03:18,000 function that has a result to it. And because of the recursive nature, it's gonna 67 00:03:18,000 --> 00:03:22,000 say that the outer problem's result, the answer to the larger problem is gonna be 68 00:03:22,000 --> 00:03:26,000 based on making calls, one or more calls to the function itself to get the answer 69 00:03:26,000 --> 00:03:30,000 to a smaller problem, and then adding them, multiplying them, comparing them to decide 70 00:03:30,000 --> 00:03:33,000 how to formulate the larger answer. 71 00:03:33,000 --> 00:03:35,000 All recursive 72 00:03:35,000 --> 00:03:35,000 code 73 00:03:35,000 --> 00:03:38,000 follows the same decomposition 74 00:03:38,000 --> 00:03:42,000 into two cases. Sometimes there's some subdivisions within there, but two general 75 00:03:42,000 --> 00:03:43,000 cases. 76 00:03:43,000 --> 00:03:45,000 The first thing - this base case. 77 00:03:45,000 --> 00:03:48,000 That's something that the recursion eventually has to stop. 78 00:03:48,000 --> 00:03:52,000 We keep saying take the task and break it down, make it a little smaller, 79 00:03:52,000 --> 00:03:55,000 but at some point we really have to stop doing that. We can't 80 00:03:55,000 --> 00:03:57,000 go on infinitely. 81 00:03:57,000 --> 00:04:00,000 There has to be some base case, the simplest possible version of the problem that 82 00:04:00,000 --> 00:04:05,000 you can directly solve. You don't need to make any further recursive calls. So the idea 83 00:04:05,000 --> 00:04:10,000 is that it kinda bottoms out there, and then allows the recursion to kind of 84 00:04:10,000 --> 00:04:10,000 unwind. 85 00:04:10,000 --> 00:04:12,000 The recursive cases, 86 00:04:12,000 --> 00:04:15,000 and there may be one or more of these, are the cases where it's not that simple, that the 87 00:04:15,000 --> 00:04:20,000 answer isn't directly solvable, but if you had the answer to a smaller, simpler 88 00:04:20,000 --> 00:04:20,000 version, you 89 00:04:20,000 --> 00:04:24,000 would be able to assemble that answer you're looking for 90 00:04:24,000 --> 00:04:27,000 using that information from the recursive call. 91 00:04:27,000 --> 00:04:31,000 So that's the kind of structure that they all look like. If I'm 92 00:04:31,000 --> 00:04:34,000 at the base case, then do the base case and return it. 93 00:04:34,000 --> 00:04:37,000 Otherwise, make some recursive calls, and 94 00:04:37,000 --> 00:04:43,000 use that to return a result from this iteration. 95 00:04:43,000 --> 00:04:45,000 So let's first look at something that 96 00:04:45,000 --> 00:04:48,000 - the first couple examples that I'm gonna show you actually are gonna be so 97 00:04:48,000 --> 00:04:52,000 easy that in some sense they're almost gonna be a little bit counterproductive because they're gonna 98 00:04:52,000 --> 00:04:54,000 teach you that recursion lets you do things that you already 99 00:04:54,000 --> 00:04:57,000 know how to do. And then I'm gonna work my way up to ones that actually 100 00:04:57,000 --> 00:04:59,000 get beyond that. 101 00:04:59,000 --> 00:05:02,000 But let's look at first the raise to power. 102 00:05:02,000 --> 00:05:05,000 C++ has no built-in exponentiation operator. There's nothing that raises 103 00:05:05,000 --> 00:05:07,000 a base to a particular exponent 104 00:05:07,000 --> 00:05:08,000 in the operator set. 105 00:05:08,000 --> 00:05:12,000 So if you want it, you need to write it, or you can use - there's a math library called 106 00:05:12,000 --> 00:05:15,000 pow for raise to power. We're gonna run our own version of it 107 00:05:15,000 --> 00:05:17,000 because it's gonna give us some practice thing about this. 108 00:05:17,000 --> 00:05:20,000 The first one I'm gonna show you is one that should feel very familiar and 109 00:05:20,000 --> 00:05:24,000 very intuitive, which is using an iterative formulation. If I'm 110 00:05:24,000 --> 00:05:27,000 trying to raise the base to the exponent, then that's really simply 111 00:05:27,000 --> 00:05:30,000 multiplying base by itself exponent times. 112 00:05:30,000 --> 00:05:31,000 So this one 113 00:05:31,000 --> 00:05:32,000 uses a for loop 114 00:05:32,000 --> 00:05:37,000 and does so. It starts the result at one, and for 115 00:05:37,000 --> 00:05:40,000 iterations through the number of exponents keeps 116 00:05:40,000 --> 00:05:46,000 multiplying to get there. So 117 00:05:46,000 --> 00:05:48,000 that one's fine, and it will perfectly work. 118 00:05:48,000 --> 00:05:51,000 I'm gonna show you this alternative way 119 00:05:51,000 --> 00:05:54,000 that starts you thinking about what it means to divide a problem up in a 120 00:05:54,000 --> 00:05:56,000 recursive strategy. 121 00:05:56,000 --> 00:06:00,000 Base to the exponent - I wanna raise five to the tenth power. If 122 00:06:00,000 --> 00:06:05,000 I had around some delegate, some 123 00:06:05,000 --> 00:06:08,000 clone of myself that I could dispatch to solve 124 00:06:08,000 --> 00:06:11,000 the slightly smaller problem of computing five to the ninth power, 125 00:06:11,000 --> 00:06:15,000 then all I would need to do is take that answer and multiply it by one more five, and I'd get 126 00:06:15,000 --> 00:06:17,000 five to the tenth. 127 00:06:17,000 --> 00:06:19,000 Okay. 128 00:06:19,000 --> 00:06:22,000 If I write code 129 00:06:22,000 --> 00:06:25,000 that's based on that, 130 00:06:25,000 --> 00:06:28,000 then I end up with something here - and I'm gonna 131 00:06:28,000 --> 00:06:31,000 let these two things go through to show us 132 00:06:31,000 --> 00:06:32,000 that 133 00:06:32,000 --> 00:06:34,000 to compute the answer to five 134 00:06:34,000 --> 00:06:36,000 to the tenth power, 135 00:06:36,000 --> 00:06:38,000 what I really need is the answer to five 136 00:06:38,000 --> 00:06:42,000 to the ninth power, which I do by making a recursive call to the same function I'm in 137 00:06:42,000 --> 00:06:43,000 the middle of writing. 138 00:06:43,000 --> 00:06:45,000 So this is raise that I'm 139 00:06:45,000 --> 00:06:49,000 defining, and in the body of it, it makes a call to raise. That's what is the 140 00:06:49,000 --> 00:06:51,000 mark of a recursive function here. I 141 00:06:51,000 --> 00:06:55,000 pass slightly different arguments. In this case, one smaller exponent 142 00:06:55,000 --> 00:06:57,000 which is getting a little bit closer 143 00:06:57,000 --> 00:07:00,000 to that simplest possible case 144 00:07:00,000 --> 00:07:02,000 that we will eventually terminate at where 145 00:07:02,000 --> 00:07:07,000 we can say I don't need to further dispatch any delegates and any clones out there 146 00:07:07,000 --> 00:07:08,000 to do the work, but if 147 00:07:08,000 --> 00:07:11,000 the exponent I'm raising it to is zero, by 148 00:07:11,000 --> 00:07:16,000 definition anything raised to the exponent of zero is one, I could just stop there. 149 00:07:16,000 --> 00:07:19,000 So when computing five to the tenth, we're gonna 150 00:07:19,000 --> 00:07:21,000 see some recursion at work. Let me 151 00:07:21,000 --> 00:07:24,000 take this code into the compiler 152 00:07:24,000 --> 00:07:27,000 153 00:07:27,000 --> 00:07:31,000 so that we can see a little bit about how this actually works 154 00:07:31,000 --> 00:07:32,000 in terms of that. 155 00:07:32,000 --> 00:07:35,000 So that's exactly the code I have there, but 156 00:07:35,000 --> 00:07:42,000 I can say 157 00:07:42,000 --> 00:07:43,000 something that I 158 00:07:43,000 --> 00:07:46,000 know the answer to. How about that? 159 00:07:46,000 --> 00:07:49,000 160 00:07:49,000 --> 00:07:51,000 First, we'll take a look at it 161 00:07:51,000 --> 00:07:55,000 doing its work, so five times five times five should be 125. 162 00:07:55,000 --> 00:07:57,000 So we can test a couple 163 00:07:57,000 --> 00:07:58,000 little 164 00:07:58,000 --> 00:08:01,000 values while we're at it. Two the sixth power, that should be 165 00:08:01,000 --> 00:08:07,000 64, just to see a couple of the cases, just to feel good about what's going on. 166 00:08:07,000 --> 00:08:10,000 And then raising say 23 to the zero power 167 00:08:10,000 --> 00:08:11,000 should be one 168 00:08:11,000 --> 00:08:14,000 as anything raised to the zero power should be. 169 00:08:14,000 --> 00:08:16,000 So a little bit of spot testing 170 00:08:16,000 --> 00:08:18,000 to feel good about what's going on. 171 00:08:18,000 --> 00:08:22,000 Now I'm gonna go back to this idea like two to the sixth. 172 00:08:22,000 --> 00:08:24,000 And I'm gonna set a breakpoint here. 173 00:08:24,000 --> 00:08:25,000 Get my breakpoint out. 174 00:08:25,000 --> 00:08:36,000 And I'm gonna run this guy in the debugger. 175 00:08:36,000 --> 00:08:39,000 Takes a little bit longer to get the debugger up and running, 176 00:08:39,000 --> 00:08:44,000 so I'll have to make a little padder up while we're going here. 177 00:08:44,000 --> 00:08:47,000 And then it tells me right now it's breaking on raise, and 178 00:08:47,000 --> 00:08:53,000 I can look around in the debugger. This is a - did not 179 00:08:53,000 --> 00:08:56,000 pick up my compilation? I think it did not. I 180 00:08:56,000 --> 00:08:59,000 must not have saved it right before I did it because it's actually got the base is 23 and the 181 00:08:59,000 --> 00:09:00,000 exponent is zero. It turns 182 00:09:00,000 --> 00:09:06,000 out I don't wanna see that case, so I'm gonna go back and 183 00:09:06,000 --> 00:09:08,000 try again. I 184 00:09:08,000 --> 00:09:16,000 wanna see it - 185 00:09:16,000 --> 00:09:24,000 no, I did not. 186 00:09:24,000 --> 00:09:28,000 And I'm just interested in knowing a little bit about the mechanics of what's gonna happen in a 187 00:09:28,000 --> 00:09:29,000 recursive situation. 188 00:09:29,000 --> 00:09:33,000 If I look at the first time that I hit my breakpoint, 189 00:09:33,000 --> 00:09:35,000 then I'll see that there's a little bit of the beginnings of the 190 00:09:35,000 --> 00:09:39,000 student main, some stuff behind it. There's a little bit of magic underneath your 191 00:09:39,000 --> 00:09:43,000 stack that you don't really need to know about, but starting from main it went into raise, 192 00:09:43,000 --> 00:09:46,000 and the arguments it has there is the base is two, the exponent is six. 193 00:09:46,000 --> 00:09:50,000 If I continue from here, then you'll notice the stack frame got one deeper. 194 00:09:50,000 --> 00:09:53,000 There's actually another indication of raise, and in fact, they're both active at the 195 00:09:53,000 --> 00:09:54,000 same time. 196 00:09:54,000 --> 00:09:57,000 The previous raise that was trying to compute two to the sixth 197 00:09:57,000 --> 00:10:01,000 is kind of in stasis back there waiting for the answer to come back from 198 00:10:01,000 --> 00:10:05,000 this version, which is looking to raise two to the fifth power. I continue again, 199 00:10:05,000 --> 00:10:08,000 I get two to the fourth. I keep doing this. I'm gonna see these guys kinda stack up, 200 00:10:08,000 --> 00:10:12,000 each one of those kind of waiting for the delegate or the clone 201 00:10:12,000 --> 00:10:17,000 to come back with that answer, so that then it can do its further work 202 00:10:17,000 --> 00:10:19,000 incorporating that result to compute the thing it needed to do. 203 00:10:19,000 --> 00:10:22,000 I get down here to raising 204 00:10:22,000 --> 00:10:24,000 two to the first power, 205 00:10:24,000 --> 00:10:26,000 and then finally I get to two to the zero, 206 00:10:26,000 --> 00:10:29,000 so now I've got these eight or so stacked frames, 207 00:10:29,000 --> 00:10:30,000 six up there. 208 00:10:30,000 --> 00:10:32,000 This one, if I step 209 00:10:32,000 --> 00:10:34,000 from here, 210 00:10:34,000 --> 00:10:37,000 it's gonna hit the base case of returning one, 211 00:10:37,000 --> 00:10:39,000 and then 212 00:10:39,000 --> 00:10:43,000 we will end up kind of working our way back out. So now, we are 213 00:10:43,000 --> 00:10:46,000 at the end of the two to the one case 214 00:10:46,000 --> 00:10:49,000 that's using the answer it got from the other one, multiplying it by two. 215 00:10:49,000 --> 00:10:53,000 Now I'm at the two to the two case, and so each of them's kind of unfolding in the stack is 216 00:10:53,000 --> 00:10:55,000 what's called unwinding. It's popping back off 217 00:10:55,000 --> 00:10:57,000 the stack frames that are there 218 00:10:57,000 --> 00:11:01,000 and kind of revisiting them, each passing up the information it got back, 219 00:11:01,000 --> 00:11:04,000 and eventually telling us that 220 00:11:04,000 --> 00:11:08,000 the answer was 64, so I will let that go. 221 00:11:08,000 --> 00:11:15,000 222 00:11:15,000 --> 00:11:17,000 So the idea that 223 00:11:17,000 --> 00:11:21,000 all of those stack frames kind of exist at the same time - they're all being maintained 224 00:11:21,000 --> 00:11:24,000 independently, so the idea that the compiler isn't confused by the idea that raise is 225 00:11:24,000 --> 00:11:26,000 invoking raise which is invoking raise, 226 00:11:26,000 --> 00:11:30,000 that each of the raise stack frames is distinct from the other ones, so the 227 00:11:30,000 --> 00:11:33,000 indications are actually kept separate. So one had two to the sixth, the next one had two to 228 00:11:33,000 --> 00:11:35,000 the fifth, and so on. 229 00:11:35,000 --> 00:11:36,000 And then eventually 230 00:11:36,000 --> 00:11:37,000 we 231 00:11:37,000 --> 00:11:40,000 need to make some progress toward that base case, so that we can then 232 00:11:40,000 --> 00:11:42,000 stop that recursion 233 00:11:42,000 --> 00:11:43,000 and unwind. 234 00:11:43,000 --> 00:11:47,000 Let me actually show you something while I'm here, which is one thing that's 235 00:11:47,000 --> 00:11:48,000 a pretty common mistake 236 00:11:48,000 --> 00:11:51,000 to make early on in a recursion is to somehow fail to make progress toward 237 00:11:51,000 --> 00:11:53,000 that base case 238 00:11:53,000 --> 00:11:57,000 or to 239 00:11:57,000 --> 00:11:58,000 - 240 00:11:58,000 --> 00:12:01,000 not all cases make it to the base case. For example, if 241 00:12:01,000 --> 00:12:03,000 I did something where 242 00:12:03,000 --> 00:12:06,000 I forgot to 243 00:12:06,000 --> 00:12:07,000 subtract one [cuts out], 244 00:12:07,000 --> 00:12:10,000 and I said oh yeah, I need to [cuts out]. In this case, I'm passing it exactly the 245 00:12:10,000 --> 00:12:13,000 same arguments I got. 246 00:12:13,000 --> 00:12:16,000 If I do this and I run this guy, 247 00:12:16,000 --> 00:12:19,000 then what's gonna happen is it's gonna go two to the sixth, two to the sixth, two to the sixth, 248 00:12:19,000 --> 00:12:20,000 and I'm gonna 249 00:12:20,000 --> 00:12:21,000 let go of 250 00:12:21,000 --> 00:12:23,000 this breakpoint here because 251 00:12:23,000 --> 00:12:30,000 I don't really wanna watch it all happening. 252 00:12:30,000 --> 00:12:31,000 And there it goes. 253 00:12:31,000 --> 00:12:35,000 Loading 6,493 stack frames, zero percent completed, so 254 00:12:35,000 --> 00:12:38,000 that's gonna take a while as you 255 00:12:38,000 --> 00:12:41,000 can imaging. And usually, once you see this error message, it's your clue to say I 256 00:12:41,000 --> 00:12:45,000 can cancel, I know what happened. The only reason I should've 257 00:12:45,000 --> 00:12:46,000 gotten 258 00:12:46,000 --> 00:12:50,000 6,500 stack frames loaded up is because I made a mistake that 259 00:12:50,000 --> 00:12:53,000 caused the stack to totally overflow. 260 00:12:53,000 --> 00:12:57,000 So the behavior in C++ or C is that when you have 261 00:12:57,000 --> 00:13:01,000 so many of those stack frames, eventually the space that's been allocated or set 262 00:13:01,000 --> 00:13:03,000 aside for the function stack will be exhausted. 263 00:13:03,000 --> 00:13:05,000 It will use all the space it has, 264 00:13:05,000 --> 00:13:09,000 and run up against a boundary, and typically report it in some way that 265 00:13:09,000 --> 00:13:13,000 suggests - sometimes you'll see stack overflow, stack out of memory error. 266 00:13:13,000 --> 00:13:14,000 267 00:13:14,000 --> 00:13:15,000 In this case, it's showing you the 268 00:13:15,000 --> 00:13:17,000 7,000 stack frames that 269 00:13:17,000 --> 00:13:20,000 are behind you, and then if you were to examine them you would see they all have exactly the 270 00:13:20,000 --> 00:13:24,000 same argument, so they weren't getting anywhere. 271 00:13:24,000 --> 00:13:27,000 I'm not gonna actually let it do that because I'm 272 00:13:27,000 --> 00:13:28,000 too impatient. 273 00:13:28,000 --> 00:13:29,000 Let 274 00:13:29,000 --> 00:13:30,000 me fix this code while I'm here. 275 00:13:30,000 --> 00:13:33,000 But other things like even this code that actually looks correct for 276 00:13:33,000 --> 00:13:39,000 some situations also has a subtle bug in it. Even if 277 00:13:39,000 --> 00:13:40,000 I fixed this, which is 278 00:13:40,000 --> 00:13:44,000 that, right now it assumed that the exponent is positive, 279 00:13:44,000 --> 00:13:46,000 that it's some number 280 00:13:46,000 --> 00:13:47,000 281 00:13:47,000 --> 00:13:49,000 that I can subtract my way down to zero. 282 00:13:49,000 --> 00:13:53,000 If I actually miscalled raise, and I gave it a negative exponent, it would 283 00:13:53,000 --> 00:13:57,000 go into infinite recursion as well. If you started it 284 00:13:57,000 --> 00:14:00,000 at ten to the negative first power, it would go negative first, negative second, negative 285 00:14:00,000 --> 00:14:02,000 third. 286 00:14:02,000 --> 00:14:05,000 6,500 stack frames later, we'd run out of space. 287 00:14:05,000 --> 00:14:08,000 In this case, since we're only intending to handle those positive powers, we 288 00:14:08,000 --> 00:14:12,000 could just put an error that was like if the exponent is less than zero then 289 00:14:12,000 --> 00:14:14,000 raise an error and don't even 290 00:14:14,000 --> 00:14:21,000 try to do anything with it. Okay. So let 291 00:14:21,000 --> 00:14:25,000 me show you a slightly different way of doing this that's also recursive, 292 00:14:25,000 --> 00:14:28,000 but that actually gets the answer a little bit more efficiently. 293 00:14:28,000 --> 00:14:31,000 This is a different way of dividing it up, but still using a 294 00:14:31,000 --> 00:14:36,000 recursive strategy which is that if I'm trying to compute five to the tenth power, 295 00:14:36,000 --> 00:14:40,000 but if I have the answer not of five to ninth power, but instead I have the 296 00:14:40,000 --> 00:14:42,000 answer of five to the fifth power, 297 00:14:42,000 --> 00:14:44,000 and then I multiply that by itself, 298 00:14:44,000 --> 00:14:48,000 I would get that five to the tenth power that I seek. 299 00:14:48,000 --> 00:14:51,000 And then there's a little bit of a case though of what if the power I was trying to 300 00:14:51,000 --> 00:14:54,000 get was odd, if I was trying to raise it to the eleventh power, I could compute the 301 00:14:54,000 --> 00:14:58,000 half power which get me to the fifth - multiplied by the fifth, but then I need 302 00:14:58,000 --> 00:14:59,000 one more 303 00:14:59,000 --> 00:15:04,000 base multiplied in there to make up for that half. Okay. 304 00:15:04,000 --> 00:15:05,000 And so I can write 305 00:15:05,000 --> 00:15:08,000 another recursive formulation here. Same 306 00:15:08,000 --> 00:15:11,000 sort of base case about 307 00:15:11,000 --> 00:15:14,000 detecting when we've gotten down, but then in this case the recursive call we make is 308 00:15:14,000 --> 00:15:17,000 to base of the exponent divided by two, 309 00:15:17,000 --> 00:15:19,000 and then we use it with an 310 00:15:19,000 --> 00:15:23,000 if else whether the exponent was even or odd, it decided whether to just square 311 00:15:23,000 --> 00:15:25,000 that number or whether to square it and 312 00:15:25,000 --> 00:15:28,000 tack in another power of the base while we're at it. 313 00:15:28,000 --> 00:15:31,000 So this one is gonna be much more quick about getting down to it, 314 00:15:31,000 --> 00:15:34,000 whereas the one we saw was gonna put one stack frame down for every 315 00:15:34,000 --> 00:15:35,000 316 00:15:35,000 --> 00:15:39,000 successive exponent power. So if you wanted to raise something to the 10th, or 20th, 317 00:15:39,000 --> 00:15:41,000 or 30th power, then you were 318 00:15:41,000 --> 00:15:43,000 giving yourself 10, 20, 30 stack frames. 319 00:15:43,000 --> 00:15:46,000 Something like 30 stack frames is not really something to be worried 320 00:15:46,000 --> 00:15:48,000 about, but if you were really trying to make this work on much larger 321 00:15:48,000 --> 00:15:49,000 numbers, 322 00:15:49,000 --> 00:15:52,000 which would require some other work because exponent 323 00:15:52,000 --> 00:15:55,000 is a very rapidly growing operator and would overflow your integers quickly, 324 00:15:55,000 --> 00:15:57,000 but this way 325 00:15:57,000 --> 00:16:00,000 very quickly divides in half. So it goes from a power of 100, to a power of 326 00:16:00,000 --> 00:16:05,000 50, to 25, to 12, to 6, to 3, to 2, to 1, so 327 00:16:05,000 --> 00:16:08,000 that dividing in half is a much quicker way to work our way down to that base case 328 00:16:08,000 --> 00:16:12,000 and get our answer back, and we're doing a lot fewer calculations 329 00:16:12,000 --> 00:16:14,000 than all those multiplies, 330 00:16:14,000 --> 00:16:16,000 one per 331 00:16:16,000 --> 00:16:19,000 base. So just a little 332 00:16:19,000 --> 00:16:21,000 diversion. 333 00:16:21,000 --> 00:16:22,000 So let me tell you something, 334 00:16:22,000 --> 00:16:23,000 just a little bit about 335 00:16:23,000 --> 00:16:27,000 kind of style as it applies to recursion. 336 00:16:27,000 --> 00:16:28,000 Recursion is 337 00:16:28,000 --> 00:16:34,000 really best when you can express it in the most kind of direct, clear, and 338 00:16:34,000 --> 00:16:36,000 simple code. 339 00:16:36,000 --> 00:16:38,000 It's hard enough to get your head around a recursive formulation 340 00:16:38,000 --> 00:16:42,000 without complicating it by having a bunch of extraneous parts where 341 00:16:42,000 --> 00:16:43,000 you're 342 00:16:43,000 --> 00:16:47,000 doing more work than necessary, or redundantly handling certain things. And 343 00:16:47,000 --> 00:16:49,000 one thing that's actually very easy to fall in the trap of 344 00:16:49,000 --> 00:16:52,000 is thinking about there's lots of other base cases you might be able to 345 00:16:52,000 --> 00:16:56,000 easily handle, so why not just go ahead and call out for them, 346 00:16:56,000 --> 00:16:57,000 test for 347 00:16:57,000 --> 00:16:59,000 - you're at the base case. You're close to the base case. 348 00:16:59,000 --> 00:17:02,000 Checking before you might make a recursive call, if you're gonna hit the base case when you 349 00:17:02,000 --> 00:17:08,000 make that call, then why make the call. I'll just anticipate and get the answer it 350 00:17:08,000 --> 00:17:09,000 would've returned anyway. 351 00:17:09,000 --> 00:17:13,000 It can lead to code that looks a little bit like this before you're done. If the 352 00:17:13,000 --> 00:17:16,000 exponent's zero, that's one. If the exponent's one, then I can just 353 00:17:16,000 --> 00:17:19,000 return the base. If it's two, then I can just multiply the base by itself. If it's 354 00:17:19,000 --> 00:17:20,000 three, I can start doing this. 355 00:17:20,000 --> 00:17:22,000 Certainly, you 356 00:17:22,000 --> 00:17:25,000 can follow this to the point of absurdity, and even for some of the simple 357 00:17:25,000 --> 00:17:28,000 cases, it might seem like you're saving yourself a little bit of extra time. You're like 358 00:17:28,000 --> 00:17:31,000 why go back around and let it make another recursive call. I could stop it right 359 00:17:31,000 --> 00:17:33,000 here. It's easy to know that answer. 360 00:17:33,000 --> 00:17:36,000 But as you do this, it complicates the code. It's a little harder to read. It's 361 00:17:36,000 --> 00:17:38,000 a little harder to 362 00:17:38,000 --> 00:17:39,000 debug. 363 00:17:39,000 --> 00:17:43,000 Really, the expense of making that one extra call, two extra calls 364 00:17:43,000 --> 00:17:46,000 is not the thing to be worried about. 365 00:17:46,000 --> 00:17:50,000 What we really want is the cleanest code that expresses what we do, has the 366 00:17:50,000 --> 00:17:53,000 simplest cases to test, and to examine, and to follow, 367 00:17:53,000 --> 00:17:56,000 and not muck it up with things that in 368 00:17:56,000 --> 00:17:57,000 effect 369 00:17:57,000 --> 00:18:01,000 don't change the computational power of this but just introduce the opportunity for error. 370 00:18:01,000 --> 00:18:02,000 Instead of a 371 00:18:02,000 --> 00:18:05,000 multiply here, I accidentally put a plus. 372 00:18:05,000 --> 00:18:07,000 It might be easy to overlook it 373 00:18:07,000 --> 00:18:08,000 and not realize what I've done, 374 00:18:08,000 --> 00:18:10,000 and then 375 00:18:10,000 --> 00:18:14,000 end up computing the wrong answer when it gets to the base case of two. In fact, if 376 00:18:14,000 --> 00:18:15,000 you do it this 377 00:18:15,000 --> 00:18:17,000 way, most things would stop at three, 378 00:18:17,000 --> 00:18:20,000 but these would suddenly become kind of their own special cases that were only 379 00:18:20,000 --> 00:18:25,000 hit if you directly called them with the two. The recursive cases will all stop earlier. It 380 00:18:25,000 --> 00:18:28,000 just complicates your testing pass now because not everything is going through 381 00:18:28,000 --> 00:18:31,000 the same code. 382 00:18:31,000 --> 00:18:34,000 So we call this arm's length recursion. I put a big X on that 383 00:18:34,000 --> 00:18:35,000 looking ahead, 384 00:18:35,000 --> 00:18:36,000 testing before you get there. 385 00:18:36,000 --> 00:18:41,000 Just let the code fall through. 386 00:18:41,000 --> 00:18:43,000 So 387 00:18:43,000 --> 00:18:45,000 Dan, he's not here today, 388 00:18:45,000 --> 00:18:48,000 but he talked to me at the end of Friday's class, and it made 389 00:18:48,000 --> 00:18:49,000 me 390 00:18:49,000 --> 00:18:53,000 wanna actually just give you a little bit of 391 00:18:53,000 --> 00:18:54,000 insight into 392 00:18:54,000 --> 00:18:57,000 recursion as it relates to 393 00:18:57,000 --> 00:18:58,000 394 00:18:58,000 --> 00:19:02,000 efficiency. Recursion by itself, just the idea of applying a recursive technique to solving a 395 00:19:02,000 --> 00:19:06,000 problem, does not give you any guarantee that it's gonna be the best solution, the 396 00:19:06,000 --> 00:19:09,000 most efficient solution, or the fact that it's gonna give you a very inefficient solution. 397 00:19:09,000 --> 00:19:11,000 Sometimes people have kind of 398 00:19:11,000 --> 00:19:11,000 a 399 00:19:11,000 --> 00:19:15,000 bad rap on recursion. It's like recursion will definitely be inefficient. 400 00:19:15,000 --> 00:19:17,000 That actually is not guaranteed. 401 00:19:17,000 --> 00:19:21,000 Recursion often requires exactly the same resources as the iterative approach. 402 00:19:21,000 --> 00:19:24,000 It takes the same amount of effort. Surveying the campus - if you're gonna 403 00:19:24,000 --> 00:19:27,000 survey the 10,000 people on campus and get everybody's information back, 404 00:19:27,000 --> 00:19:30,000 whether you're doing it divide and conquer, or whether you're sitting out there in White 405 00:19:30,000 --> 00:19:30,000 Plaza 406 00:19:30,000 --> 00:19:34,000 asking each person one by one, in the end 10,000 people got survey. 407 00:19:34,000 --> 00:19:36,000 The recursion is not 408 00:19:36,000 --> 00:19:39,000 part of what made that longer or shorter. It might actually depending on how you 409 00:19:39,000 --> 00:19:42,000 have resources work out better. Like if you could get a bunch of people in parallel 410 00:19:42,000 --> 00:19:46,000 surveying, you might end up completing the whole thing in less time, but it required 411 00:19:46,000 --> 00:19:49,000 more people, and more clipboards, and more paper 412 00:19:49,000 --> 00:19:52,000 while the process is ongoing than me standing there with one piece of paper and a 413 00:19:52,000 --> 00:19:57,000 clipboard. But then again, it took lots of my time to do it. 414 00:19:57,000 --> 00:20:00,000 So in many situations, it's really no better or no worse 415 00:20:00,000 --> 00:20:02,000 than the alternative. It makes a little bit of some tradeoffs of where the time is 416 00:20:02,000 --> 00:20:03,000 spent. 417 00:20:03,000 --> 00:20:06,000 There are situations though where recursion can actually make something that was 418 00:20:06,000 --> 00:20:09,000 efficient inefficient. There are situations where it can take something that was inefficient and 419 00:20:09,000 --> 00:20:11,000 make it efficient. So 420 00:20:11,000 --> 00:20:15,000 it's more of a case-by-case basis to decide whether recursion is the 421 00:20:15,000 --> 00:20:18,000 right tool if efficiency is one of your primary concerns. 422 00:20:18,000 --> 00:20:21,000 I will say that for problems with simple iterative solutions 423 00:20:21,000 --> 00:20:24,000 that operate relatively efficiently, iteration 424 00:20:24,000 --> 00:20:26,000 is probably the best way to solve it. 425 00:20:26,000 --> 00:20:27,000 So like 426 00:20:27,000 --> 00:20:31,000 the raise to power, yeah you could certainly do that 427 00:20:31,000 --> 00:20:32,000 iteratively. There's not 428 00:20:32,000 --> 00:20:35,000 some huge advantage that recursion is offering. I'm using them here because they're 429 00:20:35,000 --> 00:20:37,000 simple enough to get our head around. 430 00:20:37,000 --> 00:20:39,000 We're gonna work our way toward problems where 431 00:20:39,000 --> 00:20:42,000 we're gonna find things that require recursion, which 432 00:20:42,000 --> 00:20:45,000 is kind of one of the third points I put in. Why do we learn recursion? What's recursion gonna be good 433 00:20:45,000 --> 00:20:48,000 for? First off, recursion is awesome. 434 00:20:48,000 --> 00:20:52,000 There are some problems that you just can't solve using anything but recursion, 435 00:20:52,000 --> 00:20:55,000 so that the alternatives like I'll just write it iteratively won't work. 436 00:20:55,000 --> 00:20:59,000 You'll try, but you'll fail. They inherently have a recursive 437 00:20:59,000 --> 00:20:59,000 structure to them 438 00:20:59,000 --> 00:21:02,000 where recursion is the right tool for the job. 439 00:21:02,000 --> 00:21:06,000 Often, it produces the most beautiful, direct, and clear elegant code. 440 00:21:06,000 --> 00:21:08,000 The next assignment that will go out 441 00:21:08,000 --> 00:21:11,000 has these problems that you do in recursion, and they're each about ten lines 442 00:21:11,000 --> 00:21:13,000 long. Some of them are like five lines long. 443 00:21:13,000 --> 00:21:18,000 They do incredible things in five lines because of the descriptive power of 444 00:21:18,000 --> 00:21:19,000 describing it as 445 00:21:19,000 --> 00:21:22,000 here's a base case, and here's a recursive case, and everything else just follows 446 00:21:22,000 --> 00:21:23,000 from 447 00:21:23,000 --> 00:21:26,000 applying this, and reducing the problem step by step. 448 00:21:26,000 --> 00:21:28,000 So you will see things where 449 00:21:28,000 --> 00:21:31,000 the recursive code is just beautiful, clean, elegant, easy to understand, easy to follow, 450 00:21:31,000 --> 00:21:32,000 easy to test, 451 00:21:32,000 --> 00:21:34,000 solves the recursive problem. And in 452 00:21:34,000 --> 00:21:37,000 those cases, it really is a much better answer than trying to hack up some 453 00:21:37,000 --> 00:21:39,000 other iterative form 454 00:21:39,000 --> 00:21:41,000 that may in the end be 455 00:21:41,000 --> 00:21:44,000 no more efficient. It may be even less efficient. So don't let efficiency be 456 00:21:44,000 --> 00:21:46,000 kind of a big 457 00:21:46,000 --> 00:21:52,000 fear of what recursion is for you. So I'm gonna do more examples. 458 00:21:52,000 --> 00:21:54,000 459 00:21:54,000 --> 00:21:56,000 I've got three more examples, 460 00:21:56,000 --> 00:21:58,000 or four I think today, so 461 00:21:58,000 --> 00:22:01,000 I will just keep 462 00:22:01,000 --> 00:22:03,000 showing you different things, and hopefully 463 00:22:03,000 --> 00:22:05,000 the patterns will start to kind of 464 00:22:05,000 --> 00:22:07,000 come out of the mist for you. 465 00:22:07,000 --> 00:22:10,000 A palindrome string is one that reads the same forwards and backwards 466 00:22:10,000 --> 00:22:14,000 when reversed. So was it a car or a cat I saw, if you read that 467 00:22:14,000 --> 00:22:16,000 backwards, it turns out 468 00:22:16,000 --> 00:22:17,000 it 469 00:22:17,000 --> 00:22:21,000 says the same thing. Go hang a salami, I'm a lasagna 470 00:22:21,000 --> 00:22:22,000 hog. Also 471 00:22:22,000 --> 00:22:26,000 handy when you need to have a bar bet over what the longest palindrome is 472 00:22:26,000 --> 00:22:28,000 to have these things around. 473 00:22:28,000 --> 00:22:31,000 There are certainly ways to do this iteratively. If you were given a string and you were interested to 474 00:22:31,000 --> 00:22:33,000 know is it a palindrome, 475 00:22:33,000 --> 00:22:36,000 you could kind of do this marching - you're looking outside and kind of marching your way 476 00:22:36,000 --> 00:22:38,000 into the middle. 477 00:22:38,000 --> 00:22:42,000 But we're gonna go ahead and let recursion kinda help us 478 00:22:42,000 --> 00:22:45,000 deal with the subproblem of this, 479 00:22:45,000 --> 00:22:47,000 and imagine that at the simplest possible form - you could say that 480 00:22:47,000 --> 00:22:49,000 a palindrome 481 00:22:49,000 --> 00:22:51,000 consists of 482 00:22:51,000 --> 00:22:53,000 an interior palindrome, 483 00:22:53,000 --> 00:22:56,000 and then the same letter tacked on to the front and the back. 484 00:22:56,000 --> 00:22:58,000 So if you look at was it a car or a cat I saw, 485 00:22:58,000 --> 00:23:01,000 there are two Ws there. It starts and it ends with a W, 486 00:23:01,000 --> 00:23:04,000 so all palindromes must start and end with the same letter. Okay. 487 00:23:04,000 --> 00:23:05,000 Let's check that, 488 00:23:05,000 --> 00:23:11,000 and if that matches, then extract that middle and see if it's a palindrome. 489 00:23:11,000 --> 00:23:13,000 So it feels like I didn't really do anything. It's like 490 00:23:13,000 --> 00:23:17,000 all I did was match two letters, and then I said by the way 491 00:23:17,000 --> 00:23:19,000 delegate this problem 492 00:23:19,000 --> 00:23:23,000 back to myself, making a call to a function I haven't even finished writing 493 00:23:23,000 --> 00:23:27,000 to examine the rest of the letters. 494 00:23:27,000 --> 00:23:29,000 And then I need a base case. 495 00:23:29,000 --> 00:23:31,000 I've got a recursive case, right? 496 00:23:31,000 --> 00:23:34,000 Take off the outer two letters. Make sure they match. 497 00:23:34,000 --> 00:23:37,000 Recur on the inside. 498 00:23:37,000 --> 00:23:42,000 What is the simplest possible palindrome? One letter? One 499 00:23:42,000 --> 00:23:44,000 letter. One letter makes a good palindrome. One letter is by 500 00:23:44,000 --> 00:23:47,000 definition first and last letter are the same letter, so it matches. That's 501 00:23:47,000 --> 00:23:53,000 a great base case. Is it the only base case? [Inaudible]. Two 502 00:23:53,000 --> 00:23:56,000 letters is also kind of important, but there's actually an even 503 00:23:56,000 --> 00:23:58,000 simpler form, right? 504 00:23:58,000 --> 00:24:02,000 It's the empty string. So both the empty string and the single character string are by 505 00:24:02,000 --> 00:24:05,000 definition the world's simplest palindromes. They meet the 506 00:24:05,000 --> 00:24:08,000 requirements that they read the same forward and backwards. Empty string forwards 507 00:24:08,000 --> 00:24:10,000 and backwards is trivially the 508 00:24:10,000 --> 00:24:14,000 same, so that makes it even easier than doing the two-letter case. 509 00:24:14,000 --> 00:24:17,000 So if I write this code to look like that where 510 00:24:17,000 --> 00:24:19,000 if the length of the strength is 511 00:24:19,000 --> 00:24:24,000 one or fewer, so that handles both the zero and the one case, then I return true. 512 00:24:24,000 --> 00:24:25,000 Those are trivial 513 00:24:25,000 --> 00:24:26,000 514 00:24:26,000 --> 00:24:28,000 palindromes of the easiest 515 00:24:28,000 --> 00:24:30,000 immediate detection. 516 00:24:30,000 --> 00:24:31,000 Otherwise, 517 00:24:31,000 --> 00:24:33,000 I've got a return here that says 518 00:24:33,000 --> 00:24:35,000 if the first character 519 00:24:35,000 --> 00:24:38,000 is the same as the last character, 520 00:24:38,000 --> 00:24:39,000 and the 521 00:24:39,000 --> 00:24:42,000 middle - so the substring starting at Position 1 522 00:24:42,000 --> 00:24:47,000 that goes for length minus two characters that picks up the interior 523 00:24:47,000 --> 00:24:50,000 discarding the first and last characters - if that's also a palindrome, then we've got a 524 00:24:50,000 --> 00:24:51,000 palindrome. 525 00:24:51,000 --> 00:24:54,000 So given the short circuiting nature of the and, if 526 00:24:54,000 --> 00:24:56,000 it looks at the outer two characters and they don't match, it immediately just 527 00:24:56,000 --> 00:24:58,000 stops right there and says false. 528 00:24:58,000 --> 00:25:01,000 If they do match, then it goes on looking 529 00:25:01,000 --> 00:25:03,000 at the next interior pair 530 00:25:03,000 --> 00:25:07,000 which will stack up a recursive call looking at its two things, and eventually we 531 00:25:07,000 --> 00:25:10,000 will either catch a pair that doesn't match, 532 00:25:10,000 --> 00:25:14,000 and then this false will immediately return its way out, or it will keep 533 00:25:14,000 --> 00:25:17,000 going all the way down to that base case, hit a true, 534 00:25:17,000 --> 00:25:21,000 and know that we do have a full palindrome there. 535 00:25:21,000 --> 00:25:24,000 So you could certainly write this with a for loop. Actually, writing 536 00:25:24,000 --> 00:25:27,000 it with a for loop is almost a little bit trickier because you 537 00:25:27,000 --> 00:25:30,000 have to keep track of which part of the string are you on, and what happens when you 538 00:25:30,000 --> 00:25:34,000 get to the middle and things like that. In some sense, the recursive 539 00:25:34,000 --> 00:25:35,000 form really kinda 540 00:25:35,000 --> 00:25:38,000 sidesteps that by really thinking about it in a more holistic way 541 00:25:38,000 --> 00:25:41,000 of like the outer letters plus an inner palindrome 542 00:25:41,000 --> 00:25:43,000 gives me the answer I'm looking for. 543 00:25:43,000 --> 00:25:46,000 So this idea of 544 00:25:46,000 --> 00:25:49,000 taking a function you're in the middle of writing and making a call to it as 545 00:25:49,000 --> 00:25:50,000 though it worked 546 00:25:50,000 --> 00:25:53,000 is something that - they require this idea of the leap of faith. 547 00:25:53,000 --> 00:25:55,000 You haven't even finished describing 548 00:25:55,000 --> 00:25:58,000 how is palindrome operates, 549 00:25:58,000 --> 00:26:01,000 and there you are making a call to it depending on it working in order to get 550 00:26:01,000 --> 00:26:02,000 your 551 00:26:02,000 --> 00:26:04,000 function working. It's a very kind of 552 00:26:04,000 --> 00:26:06,000 wacky thing to get your head around. 553 00:26:06,000 --> 00:26:08,000 It feels a little bit 554 00:26:08,000 --> 00:26:09,000 mystical at first. 555 00:26:09,000 --> 00:26:11,000 556 00:26:11,000 --> 00:26:13,000 That feeling you feel a little bit 557 00:26:13,000 --> 00:26:16,000 discombobulated about this is probably pretty normal, 558 00:26:16,000 --> 00:26:17,000 but we're gonna 559 00:26:17,000 --> 00:26:18,000 keep seeing examples, 560 00:26:18,000 --> 00:26:21,000 and hope that 561 00:26:21,000 --> 00:26:23,000 it starts to feel a little less unsettling. 562 00:26:23,000 --> 00:26:26,000 Anybody wanna ask a question about this so far? Yeah? 563 00:26:26,000 --> 00:26:28,000 So I guess create your 564 00:26:28,000 --> 00:26:30,000 base case first, then test it? [Inaudible]. That's a great question. 565 00:26:30,000 --> 00:26:35,000 So I would say typically that's a great strategy. Get a base 566 00:26:35,000 --> 00:26:38,000 case and test against the base case, so the one character and the two character 567 00:26:38,000 --> 00:26:39,000 strings. 568 00:26:39,000 --> 00:26:42,000 And then imagine one layer out, things that will make one recursive 569 00:26:42,000 --> 00:26:46,000 call only. So in this case for the palindrome, it's like what's a two-character 570 00:26:46,000 --> 00:26:47,000 string? 571 00:26:47,000 --> 00:26:50,000 One has AB. One has AA. So one that is a palindrome, one that isn't, 572 00:26:50,000 --> 00:26:52,000 and watch it go through. 573 00:26:52,000 --> 00:26:55,000 Then from there you have to almost take that leap and say 574 00:26:55,000 --> 00:26:58,000 it worked for the base case. It worked for one out. And then you have to start 575 00:26:58,000 --> 00:27:02,000 imagining if it worked for a string of length N, it'll work for one of N plus one, 576 00:27:02,000 --> 00:27:03,000 and 577 00:27:03,000 --> 00:27:07,000 that in some sense testing it exhaustively across all strings is 578 00:27:07,000 --> 00:27:09,000 of course impossible, so you have to kind of 579 00:27:09,000 --> 00:27:12,000 move to a sort of larger case where you can't just sit there and trace the whole 580 00:27:12,000 --> 00:27:15,000 thing. You'll have to in some sense take a faith thing that says 581 00:27:15,000 --> 00:27:18,000 if it could have computed whether the interior's a palindrome, then adding two 582 00:27:18,000 --> 00:27:21,000 characters on the outside 583 00:27:21,000 --> 00:27:21,000 584 00:27:21,000 --> 00:27:24,000 and massaging that with that answer should produce the right thing. So some bigger 585 00:27:24,000 --> 00:27:26,000 tests 586 00:27:26,000 --> 00:27:28,000 that 587 00:27:28,000 --> 00:27:30,000 verify that the recursive case 588 00:27:30,000 --> 00:27:32,000 when exercised does the right thing, 589 00:27:32,000 --> 00:27:34,000 then the pair together - All your code is going through 590 00:27:34,000 --> 00:27:38,000 these same lines. The outer case going down to the recursive case, down 591 00:27:38,000 --> 00:27:39,000 to that base case, and that's 592 00:27:39,000 --> 00:27:43,000 one of the beauty of writing it recursively is that in some sense 593 00:27:43,000 --> 00:27:46,000 once this piece of code works for some simple cases, the idea that setting it to 594 00:27:46,000 --> 00:27:48,000 larger cases 595 00:27:48,000 --> 00:27:51,000 is almost - I don't wanna 596 00:27:51,000 --> 00:27:54,000 say guaranteed. That maybe makes it sound too easy, but in fact, if it 597 00:27:54,000 --> 00:27:55,000 works for 598 00:27:55,000 --> 00:27:58,000 cases of N and then N plus one, then it'll work for 100, and 101, and 599 00:27:58,000 --> 00:28:02,000 6,000, and 6,001, and all the way through all the numbers by 600 00:28:02,000 --> 00:28:06,000 induction. Question? 601 00:28:06,000 --> 00:28:10,000 You have to remove all the [inaudible], all the spaces? Yeah. So definitely like the was it a car to match I should definitely 602 00:28:10,000 --> 00:28:13,000 be taking my spaces out of there to make it right. You 603 00:28:13,000 --> 00:28:21,000 are totally correct on that. 604 00:28:21,000 --> 00:28:22,000 So let me show you 605 00:28:22,000 --> 00:28:25,000 one where recursion is definitely 606 00:28:25,000 --> 00:28:27,000 gonna buy us some real efficiency 607 00:28:27,000 --> 00:28:30,000 and some real clarity in solving a 608 00:28:30,000 --> 00:28:32,000 search problem. I've got a 609 00:28:32,000 --> 00:28:35,000 vector. Let's say it's a vector of strings. It's a vector 610 00:28:35,000 --> 00:28:37,000 of numbers. A vector of anything, it doesn't really matter. 611 00:28:37,000 --> 00:28:40,000 And I wanna see if I can find a particular entry in it. So unlike the 612 00:28:40,000 --> 00:28:44,000 set which can do a fast contains for you, in vector 613 00:28:44,000 --> 00:28:46,000 if I haven't done anything special with it, 614 00:28:46,000 --> 00:28:49,000 then there's no guarantee about where to find something. So if I wanna say 615 00:28:49,000 --> 00:28:51,000 616 00:28:51,000 --> 00:28:54,000 did somebody score 75 on the exam, then I'm gonna have 617 00:28:54,000 --> 00:28:56,000 to just walk through the vector starting at Slot 618 00:28:56,000 --> 00:28:59,000 0, walk my way to the end, and 619 00:28:59,000 --> 00:29:02,000 compare to see if I find a 75. If I get to the end and I haven't found one, then 620 00:29:02,000 --> 00:29:04,000 I can say no. 621 00:29:04,000 --> 00:29:05,000 So that's what's called linear search. Linear 622 00:29:05,000 --> 00:29:10,000 kind of implies this left to right sequential processing. 623 00:29:10,000 --> 00:29:11,000 And linear search 624 00:29:11,000 --> 00:29:15,000 has the property that as the size of the input grows, the amount of time 625 00:29:15,000 --> 00:29:18,000 taken to search it grows in proportion. 626 00:29:18,000 --> 00:29:20,000 So if you have a 1000 number array, 627 00:29:20,000 --> 00:29:23,000 and you doubled its size, you would expect that doing a linear search on it should take 628 00:29:23,000 --> 00:29:30,000 twice as long for an array that's twice as large. 629 00:29:30,000 --> 00:29:34,000 The strategy we're gonna look at today is binary search 630 00:29:34,000 --> 00:29:37,000 which is gonna try to avoid this looking in every one of those boxes to 631 00:29:37,000 --> 00:29:38,000 find something. 632 00:29:38,000 --> 00:29:42,000 It's gonna take a divide and conquer strategy, and it's gonna require a sorted 633 00:29:42,000 --> 00:29:42,000 vector. 634 00:29:42,000 --> 00:29:45,000 So in order to do an efficient lookup, 635 00:29:45,000 --> 00:29:48,000 it helps if we've done some pre-rearrangement 636 00:29:48,000 --> 00:29:49,000 637 00:29:49,000 --> 00:29:51,000 of the data. In this case, putting it into sorted order 638 00:29:51,000 --> 00:29:55,000 is gonna make it much easier for us to be able to find something in it because 639 00:29:55,000 --> 00:29:55,000 we have 640 00:29:55,000 --> 00:29:58,000 better information about where to look, 641 00:29:58,000 --> 00:29:59,000 so much faster. 642 00:29:59,000 --> 00:30:03,000 So we'll see that surely there was some cost to that, 643 00:30:03,000 --> 00:30:05,000 but typically binary search is gonna be used when you have an array where you 644 00:30:05,000 --> 00:30:07,000 don't do a lot of changes to it so 645 00:30:07,000 --> 00:30:11,000 that putting it in a sorted order can be done once, and then from that point forward you can 646 00:30:11,000 --> 00:30:15,000 search it many times, getting the benefit of the work you did to put it in 647 00:30:15,000 --> 00:30:16,000 sorted order. 648 00:30:16,000 --> 00:30:19,000 If you plan to sort it just to search it, then in some sense all the time you spent 649 00:30:19,000 --> 00:30:20,000 sorting it 650 00:30:20,000 --> 00:30:25,000 would kind of count against you and unlikely to come out ahead. 651 00:30:25,000 --> 00:30:28,000 So the insight we're gonna use is 652 00:30:28,000 --> 00:30:32,000 that if we have this in sorted order, and 653 00:30:32,000 --> 00:30:34,000 we're trying to search the whole thing - we're looking for let's say the No. 75 654 00:30:34,000 --> 00:30:36,000 - 655 00:30:36,000 --> 00:30:38,000 is that if we just look at the middlemost element, 656 00:30:38,000 --> 00:30:40,000 so we have this idea that we're looking at the whole vector right now from the 657 00:30:40,000 --> 00:30:42,000 start to the end, 658 00:30:42,000 --> 00:30:45,000 and I look at the middle element, and I say it's a 54. I can say 659 00:30:45,000 --> 00:30:49,000 if 75 is in this vector because it's in sorted order, 660 00:30:49,000 --> 00:30:51,000 it can't be 661 00:30:51,000 --> 00:30:52,000 anywhere over here. 662 00:30:52,000 --> 00:30:55,000 If 54's right there, everything to the left of 54 663 00:30:55,000 --> 00:30:57,000 must be less than that, 664 00:30:57,000 --> 00:30:59,000 and 75 wouldn't be over there. 665 00:30:59,000 --> 00:31:00,000 So that means I can 666 00:31:00,000 --> 00:31:03,000 just discard that half of the 667 00:31:03,000 --> 00:31:06,000 vector from further consideration. 668 00:31:06,000 --> 00:31:07,000 So now I have this half 669 00:31:07,000 --> 00:31:10,000 to continue looking at which is the things that 670 00:31:10,000 --> 00:31:13,000 are the right of 54 all the way to the end. 671 00:31:13,000 --> 00:31:17,000 I use the same strategy again. I say if I'm searching a vector - so 672 00:31:17,000 --> 00:31:19,000 last time I was searching a vector that had 25 elements. Now I've got one that's got 673 00:31:19,000 --> 00:31:21,000 just 12. 674 00:31:21,000 --> 00:31:24,000 Again, I use the same strategy. Look at the one in the middle. 675 00:31:24,000 --> 00:31:26,000 I say oh, it's an 80, 676 00:31:26,000 --> 00:31:29,000 and then I say well the number I'm looking for is 75. 677 00:31:29,000 --> 00:31:30,000 It can't be 678 00:31:30,000 --> 00:31:35,000 to the right of the 80. It must be to the left of it. 679 00:31:35,000 --> 00:31:36,000 And then that lets me 680 00:31:36,000 --> 00:31:40,000 get rid of another quarter of the vector. If I keep doing this, I get rid of 681 00:31:40,000 --> 00:31:43,000 half, and then a quarter, and then an eighth, and 682 00:31:43,000 --> 00:31:47,000 then a 16th. Very quickly, I will narrow in on the position where if 75 is in 683 00:31:47,000 --> 00:31:53,000 this vector, it has to be. Or I'll be able to conclude it wasn't there at all. Then I kind of 684 00:31:53,000 --> 00:31:55,000 work on my in, and 685 00:31:55,000 --> 00:31:59,000 I found a 74 and a 76 over there, then I'm done. 686 00:31:59,000 --> 00:32:02,000 That base case comes when I have 687 00:32:02,000 --> 00:32:04,000 such a small little vector there 688 00:32:04,000 --> 00:32:05,000 where 689 00:32:05,000 --> 00:32:09,000 my bounds have crossed in such a way that I can say I never found what I 690 00:32:09,000 --> 00:32:16,000 was looking for. 691 00:32:16,000 --> 00:32:19,000 So let's walk through 692 00:32:19,000 --> 00:32:21,000 this 693 00:32:21,000 --> 00:32:22,000 694 00:32:22,000 --> 00:32:25,000 bit of code that kind of puts into C++ the thing I just described here. 695 00:32:25,000 --> 00:32:29,000 I've got a vector. In this case, I'm using a vector that's containing strings. 696 00:32:29,000 --> 00:32:32,000 It could be ints. It could be anything. It doesn't really matter. 697 00:32:32,000 --> 00:32:36,000 I've got a start and a stop, which I identify the sub-portion of the vector 698 00:32:36,000 --> 00:32:40,000 that we're interested in. So the start is the first index to consider. The stop is the 699 00:32:40,000 --> 00:32:41,000 last index to consider. 700 00:32:41,000 --> 00:32:46,000 So the very first call to this will have start set to zero and stop set to the vector's 701 00:32:46,000 --> 00:32:48,000 size minus one. I 702 00:32:48,000 --> 00:32:51,000 compute the midpoint index 703 00:32:51,000 --> 00:32:54,000 which is just the sum of the start and stop divided by two, 704 00:32:54,000 --> 00:32:56,000 and then I compare 705 00:32:56,000 --> 00:32:58,000 the key that I'm looking for to 706 00:32:58,000 --> 00:33:02,000 the value at that index. I'm looking right in the middle. If it happens to match, 707 00:33:02,000 --> 00:33:06,000 then I return that. The goal of binary search in this case is to return the index of a 708 00:33:06,000 --> 00:33:08,000 matching element within the vector, 709 00:33:08,000 --> 00:33:11,000 or to return this not found negative one constant 710 00:33:11,000 --> 00:33:14,000 if it was unable to find any match anywhere. 711 00:33:14,000 --> 00:33:16,000 So when we do find it 712 00:33:16,000 --> 00:33:20,000 at whatever the level the recursion is, we can just immediately return that. We're done. 713 00:33:20,000 --> 00:33:21,000 We found it. It's good. 714 00:33:21,000 --> 00:33:24,000 Otherwise, we're gonna make this recursive call 715 00:33:24,000 --> 00:33:28,000 that looks at either the left half or the right half based on if key is 716 00:33:28,000 --> 00:33:28,000 less than 717 00:33:28,000 --> 00:33:30,000 the value we found at the midpoint, 718 00:33:30,000 --> 00:33:32,000 then the place we're searching is - 719 00:33:32,000 --> 00:33:34,000 still has the same start position, 720 00:33:34,000 --> 00:33:36,000 but is now capped 721 00:33:36,000 --> 00:33:38,000 by the 722 00:33:38,000 --> 00:33:40,000 element exactly to the left of the midpoint, 723 00:33:40,000 --> 00:33:43,000 and then the right one, 724 00:33:43,000 --> 00:33:45,000 the inversion of that, 725 00:33:45,000 --> 00:33:47,000 one to the right of the midpoint 726 00:33:47,000 --> 00:33:49,000 and the stop unchanged. 727 00:33:49,000 --> 00:33:53,000 So taking off half of the elements under consideration at each stage, 728 00:33:53,000 --> 00:33:54,000 eventually 729 00:33:54,000 --> 00:33:58,000 I will get down to the simplest possible case. And the simplest possible case isn't that I have a one-element 730 00:33:58,000 --> 00:34:02,000 vector and I found it or not. The really simple case is actually that I have zero 731 00:34:02,000 --> 00:34:03,000 elements in my vector 732 00:34:03,000 --> 00:34:04,000 that I just kept 733 00:34:04,000 --> 00:34:06,000 moving in the 734 00:34:06,000 --> 00:34:09,000 upper and lower bound point until they crossed, 735 00:34:09,000 --> 00:34:12,000 which meant that I ran out of elements to check. 736 00:34:12,000 --> 00:34:15,000 And that happens when the start index is greater than the stop index. So the start 737 00:34:15,000 --> 00:34:19,000 and the stop if they're equal to each other mean that you have a one element vector left 738 00:34:19,000 --> 00:34:20,000 to search, 739 00:34:20,000 --> 00:34:22,000 but if you - For 740 00:34:22,000 --> 00:34:24,000 example, if you got to that case where you have that one element vector left to search, you'll look 741 00:34:24,000 --> 00:34:28,000 at that one, and if it matches, you'll be done. Otherwise, you'll end up 742 00:34:28,000 --> 00:34:30,000 either decrementing the stop 743 00:34:30,000 --> 00:34:33,000 to move past the start, or incrementing the start to move past the 744 00:34:33,000 --> 00:34:34,000 stop. 745 00:34:34,000 --> 00:34:36,000 And then that next iteration will hit this base case that said 746 00:34:36,000 --> 00:34:40,000 I looked at the element in a one-element vector. It didn't work 747 00:34:40,000 --> 00:34:40,000 out. 748 00:34:40,000 --> 00:34:43,000 I can tell you for sure it's not found. 749 00:34:43,000 --> 00:34:45,000 If it had been here, I would've seen it. 750 00:34:45,000 --> 00:34:47,000 And this is looking at just one element 751 00:34:47,000 --> 00:34:49,000 each 752 00:34:49,000 --> 00:34:50,000 recursive call, 753 00:34:50,000 --> 00:34:55,000 and the recursive calls in this case stack up to a depth 754 00:34:55,000 --> 00:34:57,000 based on the logarithm of the size 755 00:34:57,000 --> 00:34:59,000 to the power of two, 756 00:34:59,000 --> 00:35:02,000 so that if you have 1000 elements, 757 00:35:02,000 --> 00:35:06,000 you look at one, and now you have a 500-element collection to look 758 00:35:06,000 --> 00:35:09,000 at again. You look at one, you have 759 00:35:09,000 --> 00:35:12,000 a 250 element, 125, 60, 30, 760 00:35:12,000 --> 00:35:12,000 15. 761 00:35:12,000 --> 00:35:14,000 So at each stage 762 00:35:14,000 --> 00:35:15,000 half of them 763 00:35:15,000 --> 00:35:19,000 remain for the further call, and the number of times you can do that 764 00:35:19,000 --> 00:35:22,000 for 1000 is the number of times you can divide 1000 by two, which is 765 00:35:22,000 --> 00:35:24,000 the log based two of that, 766 00:35:24,000 --> 00:35:26,000 which is roughly ten. 767 00:35:26,000 --> 00:35:29,000 So if you were looking at 1000 number array, if it's in sorted order, 768 00:35:29,000 --> 00:35:32,000 it takes you ten comparisons 769 00:35:32,000 --> 00:35:34,000 to conclusively determine 770 00:35:34,000 --> 00:35:38,000 where an element is if it's in there, or that it doesn't exist in the array at 771 00:35:38,000 --> 00:35:39,000 all. 772 00:35:39,000 --> 00:35:41,000 If you take that 1000 element array, 773 00:35:41,000 --> 00:35:43,000 and you make it twice as big, 774 00:35:43,000 --> 00:35:46,000 so now I have a 2000 775 00:35:46,000 --> 00:35:50,000 number array, how much longer does it take? One more step. 776 00:35:50,000 --> 00:35:51,000 One more step. 777 00:35:51,000 --> 00:35:55,000 Just one, right? You look at one, and you have a 1000 number array, so however long it took 778 00:35:55,000 --> 00:35:56,000 you to do that 1000 number array, 779 00:35:56,000 --> 00:36:00,000 it takes one additional comparison, kinda one stack frame on top of that 780 00:36:00,000 --> 00:36:01,000 to get its way down. 781 00:36:01,000 --> 00:36:04,000 So this means actually this is super efficient. 782 00:36:04,000 --> 00:36:06,000 That you can search so for example 783 00:36:06,000 --> 00:36:09,000 a million is roughly two the 20th power. 784 00:36:09,000 --> 00:36:12,000 So you have a million entry 785 00:36:12,000 --> 00:36:16,000 collection to search, it will take you 20 comparisons to say for sure 786 00:36:16,000 --> 00:36:17,000 it's here or not, 787 00:36:17,000 --> 00:36:18,000 and here's where I found it, 788 00:36:18,000 --> 00:36:20,000 just 20. 789 00:36:20,000 --> 00:36:22,000 You go up to two million, it takes 790 00:36:22,000 --> 00:36:24,000 21. The 791 00:36:24,000 --> 00:36:27,000 very slow growing function, that logarithm function, so that tells you 792 00:36:27,000 --> 00:36:28,000 793 00:36:28,000 --> 00:36:31,000 that this is gonna be a very efficient way of searching a sorted array. A 794 00:36:31,000 --> 00:36:34,000 category 795 00:36:34,000 --> 00:36:37,000 thing called the divide and conquer that 796 00:36:37,000 --> 00:36:39,000 take a problem, 797 00:36:39,000 --> 00:36:42,000 divide it typically in half, but sometimes in thirds or some other 798 00:36:42,000 --> 00:36:45,000 way, and then kind of - in this case 799 00:36:45,000 --> 00:36:49,000 it's particularly handy that we can throw away some part of the problem, so we 800 00:36:49,000 --> 00:36:56,000 divide and focus on just one part to solve the problem. 801 00:36:56,000 --> 00:36:58,000 All right. So this is the first one 802 00:36:58,000 --> 00:37:02,000 that's gonna start to 803 00:37:02,000 --> 00:37:04,000 really inspire you for how recursion can help you solve problems 804 00:37:04,000 --> 00:37:05,000 that you might 805 00:37:05,000 --> 00:37:08,000 have no idea how to approach any other way 806 00:37:08,000 --> 00:37:10,000 than using a recursive formulation. 807 00:37:10,000 --> 00:37:13,000 So this is an exercise that comes out of the reader in Chapter 4, 808 00:37:13,000 --> 00:37:16,000 and the 809 00:37:16,000 --> 00:37:18,000 context of it is you have N things, 810 00:37:18,000 --> 00:37:22,000 so maybe it's N people in a dorm, 60 people in a dorm, 811 00:37:22,000 --> 00:37:26,000 and you would like to choose K of them. Let's K a real number, four 812 00:37:26,000 --> 00:37:29,000 - four people to go together to Flicks. 813 00:37:29,000 --> 00:37:32,000 So of your 60 dorm mates, how many different ways could you 814 00:37:32,000 --> 00:37:33,000 pick a subset 815 00:37:33,000 --> 00:37:35,000 of size four 816 00:37:35,000 --> 00:37:38,000 that doesn't repeat any of the others? So you can pick the 817 00:37:38,000 --> 00:37:41,000 two people from the first floor, one person from the middle floor, one person 818 00:37:41,000 --> 00:37:44,000 from the top floor, but then you can kind of shuffle it up. What if you took all the people from the 819 00:37:44,000 --> 00:37:45,000 first floor, or 820 00:37:45,000 --> 00:37:48,000 these people from that room, and whatnot? You can imagine there's a lot of kind of 821 00:37:48,000 --> 00:37:50,000 machinations 822 00:37:50,000 --> 00:37:53,000 that could be present here, 823 00:37:53,000 --> 00:37:57,000 and counting them, it's not quite obvious 824 00:37:57,000 --> 00:37:59,000 unless you kinda go back to start working on your real math 825 00:37:59,000 --> 00:38:01,000 skills 826 00:38:01,000 --> 00:38:05,000 how it is that you can write a formula for this. 827 00:38:05,000 --> 00:38:07,000 So what I'm gonna give you is 828 00:38:07,000 --> 00:38:11,000 a recursive way of thinking about this problem. 829 00:38:11,000 --> 00:38:12,000 So I drew 830 00:38:12,000 --> 00:38:15,000 a set of the things we're looking at? 831 00:38:15,000 --> 00:38:18,000 So there are N things that we're trying to choose K out 832 00:38:18,000 --> 00:38:21,000 of. So right now, I've got 833 00:38:21,000 --> 00:38:23,000 12 or so 834 00:38:23,000 --> 00:38:24,000 people, or 835 00:38:24,000 --> 00:38:26,000 items, whatever it is. 836 00:38:26,000 --> 00:38:29,000 What I'm gonna do is I'm gonna imagine just designating one 837 00:38:29,000 --> 00:38:30,000 totally at random. 838 00:38:30,000 --> 00:38:33,000 So pick Bob. 839 00:38:33,000 --> 00:38:35,000 Bob is one of the people in the dorm. I'm gonna kind of separate him from 840 00:38:35,000 --> 00:38:39,000 everybody else mentally in my mind, and draw this line, and kinda mark him with a red flag 841 00:38:39,000 --> 00:38:41,000 that says that's Bob. 842 00:38:41,000 --> 00:38:45,000 So Bob might go to Flicks or might not go to Flicks. Some of the subsets for 843 00:38:45,000 --> 00:38:52,000 going to Flicks will include Bob, and some will not. 844 00:38:52,000 --> 00:38:53,000 Okay. 845 00:38:53,000 --> 00:38:57,000 So what I'd like to think about is how many different subsets can I make that will 846 00:38:57,000 --> 00:38:58,000 include Bob, 847 00:38:58,000 --> 00:39:01,000 and how many different subsets can I make that don't include Bob. And 848 00:39:01,000 --> 00:39:05,000 if I added those together, then that should be the total number of subsets I can make 849 00:39:05,000 --> 00:39:08,000 from this collection. 850 00:39:08,000 --> 00:39:11,000 Okay, so the subsets that include Bob - 851 00:39:11,000 --> 00:39:15,000 so once I've committed to Bob being in the set, and let's say I'm trying to pick four 852 00:39:15,000 --> 00:39:16,000 members out of here, 853 00:39:16,000 --> 00:39:18,000 then I have Bob 854 00:39:18,000 --> 00:39:22,000 and I have to figure out how many ways can I pick three people to accompany Bob to 855 00:39:22,000 --> 00:39:24,000 the Flicks. 856 00:39:24,000 --> 00:39:28,000 So I'm picking from a slightly smaller population. The population went down by one, 857 00:39:28,000 --> 00:39:31,000 and the number I'm seeking went down by one, 858 00:39:31,000 --> 00:39:34,000 and that tells me all the ways I can pick three people to go with Bob. 859 00:39:34,000 --> 00:39:38,000 The ones that don't include Bob, and Bob's just out of the running, 860 00:39:38,000 --> 00:39:42,000 I look at the remaining population which is still one smaller, everybody but Bob, and I 861 00:39:42,000 --> 00:39:47,000 look for the ways I can still pick four people from there. 862 00:39:47,000 --> 00:39:51,000 So what I have here is trying to compute C of NK 863 00:39:51,000 --> 00:39:56,000 is trying to compute C of N minus one K minus one and add it to C of N minus one K. 864 00:39:56,000 --> 00:39:58,000 So this is 865 00:39:58,000 --> 00:39:59,000 picking 866 00:39:59,000 --> 00:40:02,000 friends to accompany Bob. This is picking people without Bob. 867 00:40:02,000 --> 00:40:03,000 Add those together, 868 00:40:03,000 --> 00:40:08,000 and I will have the total number of ways I can pick K things out of N. 869 00:40:08,000 --> 00:40:13,000 So we're very much relying on this recursive idea of if I had the answer 870 00:40:13,000 --> 00:40:16,000 - I don't feel smart enough to know the answer directly, 871 00:40:16,000 --> 00:40:20,000 but if I could defer it to someone who was actually willing to do more 872 00:40:20,000 --> 00:40:23,000 scrutiny into this thing, if you could tell me how many groups of three you can 873 00:40:23,000 --> 00:40:28,000 join with Bob, and how many groups of four you can pick without Bob, I can tell you 874 00:40:28,000 --> 00:40:30,000 what the total answer is. 875 00:40:30,000 --> 00:40:33,000 The simplest possible base case 876 00:40:33,000 --> 00:40:38,000 we're gonna work our way down to are when there are just no choices remaining at all. 877 00:40:38,000 --> 00:40:40,000 So if you look back at my 878 00:40:40,000 --> 00:40:43,000 things that are here, in 879 00:40:43,000 --> 00:40:46,000 both cases the population is getting smaller, 880 00:40:46,000 --> 00:40:50,000 and in one of the recursive calls, the number of things I'm trying to 881 00:40:50,000 --> 00:40:52,000 pick is also getting smaller. 882 00:40:52,000 --> 00:40:55,000 So they're both making progress toward kind of shrinking those down to where 883 00:40:55,000 --> 00:40:56,000 there's kind of 884 00:40:56,000 --> 00:40:59,000 more and more constraints on what I have to choose. 885 00:40:59,000 --> 00:41:02,000 For example, on this one 886 00:41:02,000 --> 00:41:05,000 as I keep shrinking the population by one 887 00:41:05,000 --> 00:41:07,000 and trying to get the same number of people, 888 00:41:07,000 --> 00:41:10,000 eventually I'll be trying to pick three people out of three, 889 00:41:10,000 --> 00:41:14,000 where I'm trying to pick of K of K remaining. Well, there's only one way to do 890 00:41:14,000 --> 00:41:17,000 that which is to take everyone. 891 00:41:17,000 --> 00:41:18,000 On this one, I'll 892 00:41:18,000 --> 00:41:20,000 eventually keep picking people, 893 00:41:20,000 --> 00:41:23,000 so the K is always less than the N in this case. The 894 00:41:23,000 --> 00:41:26,000 K will eventually kinda bottom out, or I'll say I've 895 00:41:26,000 --> 00:41:30,000 already picked all the people. I've already picked four people. I need to pick zero more. And 896 00:41:30,000 --> 00:41:34,000 at that point, that's also very easy, right? Picking zero out of a population, there's 897 00:41:34,000 --> 00:41:38,000 only one way to do that. 898 00:41:38,000 --> 00:41:41,000 So what we end up with is 899 00:41:41,000 --> 00:41:45,000 a very simple base case of if K equals zero - so I'm not trying to choose anymore. 900 00:41:45,000 --> 00:41:49,000 I've already committed all the slots. Or if K is equal to N 901 00:41:49,000 --> 00:41:50,000 where I've 902 00:41:50,000 --> 00:41:52,000 discarded a whole bunch of people, and now I'm down to where I'm 903 00:41:52,000 --> 00:41:56,000 facing I've gotta get four, and I've got four left. Well, there's only one way to do those things, 904 00:41:56,000 --> 00:41:59,000 and that's to take everybody or to take nobody. 905 00:41:59,000 --> 00:42:00,000 And then otherwise, 906 00:42:00,000 --> 00:42:02,000 I make those two recursive calls 907 00:42:02,000 --> 00:42:05,000 with Bob, without Bob, add them together 908 00:42:05,000 --> 00:42:13,000 to get my whole result. 909 00:42:13,000 --> 00:42:14,000 That's wacky. I'm gonna 910 00:42:14,000 --> 00:42:18,000 read you something, 911 00:42:18,000 --> 00:42:22,000 and then we'll call it a day. I 912 00:42:22,000 --> 00:42:31,000 brought a book with me. I stole this from my children.