[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:08.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:08.00,0:00:11.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:11.00,0:00:15.00,Default,,0000,0000,0000,,This presentation is delivered by the Stanford Center for Professional Development.
Dialogue: 0,0:00:15.00,0:00:24.00,Default,,0000,0000,0000,,
Dialogue: 0,0:00:24.00,0:00:26.00,Default,,0000,0000,0000,,Good afternoon.
Dialogue: 0,0:00:26.00,0:00:29.00,Default,,0000,0000,0000,,You guys are talkative.
Dialogue: 0,0:00:29.00,0:00:32.00,Default,,0000,0000,0000,,So we talked just a little bit about the vocabulary of recursion at the
Dialogue: 0,0:00:32.00,0:00:36.00,Default,,0000,0000,0000,,end of Friday. It was very rushed for time, so I'm
Dialogue: 0,0:00:36.00,0:00:40.00,Default,,0000,0000,0000,,just gonna repeat some of those words to get us thinking about what the
Dialogue: 0,0:00:40.00,0:00:42.00,Default,,0000,0000,0000,,context for solving problems recursively looks like. And then we're gonna go along and
Dialogue: 0,0:00:42.00,0:00:45.00,Default,,0000,0000,0000,,do a lot of examples [cuts out].
Dialogue: 0,0:00:45.00,0:00:48.00,Default,,0000,0000,0000,,So the idea is that a recursive function is one that calls itself.
Dialogue: 0,0:00:48.00,0:00:51.00,Default,,0000,0000,0000,,That's really all it means
Dialogue: 0,0:00:51.00,0:00:54.00,Default,,0000,0000,0000,,at the most trivial level. It says that in the context of writing a
Dialogue: 0,0:00:54.00,0:00:56.00,Default,,0000,0000,0000,,function binky, it's gonna make a call
Dialogue: 0,0:00:56.00,0:01:00.00,Default,,0000,0000,0000,,or one or more calls to binky itself past
Dialogue: 0,0:01:00.00,0:01:03.00,Default,,0000,0000,0000,,an argument as part of solving or doing some task.
Dialogue: 0,0:01:03.00,0:01:04.00,Default,,0000,0000,0000,,The idea is that
Dialogue: 0,0:01:04.00,0:01:08.00,Default,,0000,0000,0000,,we're using that because the problem itself has some self-similarity where the
Dialogue: 0,0:01:08.00,0:01:11.00,Default,,0000,0000,0000,,answer I was seeking - so the idea of surveying the whole campus can actually be thought of as well if
Dialogue: 0,0:01:11.00,0:01:14.00,Default,,0000,0000,0000,,I could get somebody to survey this part of campus and this part of campus,
Dialogue: 0,0:01:14.00,0:01:17.00,Default,,0000,0000,0000,,somebody to survey all the freshmen, somebody to [cuts out]
Dialogue: 0,0:01:17.00,0:01:18.00,Default,,0000,0000,0000,,and whatnot,
Dialogue: 0,0:01:18.00,0:01:21.00,Default,,0000,0000,0000,,that those in a sense are - those surveys are just smaller instances of the same kind
Dialogue: 0,0:01:21.00,0:01:24.00,Default,,0000,0000,0000,,of problem I was originally trying to solve. And
Dialogue: 0,0:01:24.00,0:01:26.00,Default,,0000,0000,0000,,if I could recursively
Dialogue: 0,0:01:26.00,0:01:30.00,Default,,0000,0000,0000,,delegate those things out, and then they themselves may in turn delegate even
Dialogue: 0,0:01:30.00,0:01:32.00,Default,,0000,0000,0000,,further to smaller but same
Dialogue: 0,0:01:32.00,0:01:36.00,Default,,0000,0000,0000,,structured problems to where we could eventually get to something so simple - in
Dialogue: 0,0:01:36.00,0:01:40.00,Default,,0000,0000,0000,,that case of asking ten people for their input
Dialogue: 0,0:01:40.00,0:01:44.00,Default,,0000,0000,0000,,that don't require any further decomposition - we will have worked our way to this base
Dialogue: 0,0:01:44.00,0:01:48.00,Default,,0000,0000,0000,,case that then we can gather back up all the results and solve the whole thing.
Dialogue: 0,0:01:48.00,0:01:51.00,Default,,0000,0000,0000,,This is gonna feel very mysterious at first,
Dialogue: 0,0:01:51.00,0:01:53.00,Default,,0000,0000,0000,,and some of the examples I give you'll say I have
Dialogue: 0,0:01:53.00,0:01:56.00,Default,,0000,0000,0000,,really easy alternatives other than recursion, so it's not gonna seem worth
Dialogue: 0,0:01:56.00,0:01:58.00,Default,,0000,0000,0000,,the pain of trying to get your head around it.
Dialogue: 0,0:01:58.00,0:02:03.00,Default,,0000,0000,0000,,But eventually, we're gonna work our way up to problems where recursion really is the right solution,
Dialogue: 0,0:02:03.00,0:02:06.00,Default,,0000,0000,0000,,and there are no other alternatives that are obvious or simple
Dialogue: 0,0:02:06.00,0:02:07.00,Default,,0000,0000,0000,,to do.
Dialogue: 0,0:02:07.00,0:02:07.00,Default,,0000,0000,0000,,So the
Dialogue: 0,0:02:07.00,0:02:11.00,Default,,0000,0000,0000,,idea throughout this week is actually just a lot of practice. Telling you
Dialogue: 0,0:02:11.00,0:02:13.00,Default,,0000,0000,0000,,what the terms mean I think is not actually gonna help you understand it. I think what you
Dialogue: 0,0:02:13.00,0:02:18.00,Default,,0000,0000,0000,,need to see is examples. So I'm gonna be doing four or five examples today, four or five
Dialogue: 0,0:02:18.00,0:02:20.00,Default,,0000,0000,0000,,examples on Wednesday, and four or five examples on Friday
Dialogue: 0,0:02:20.00,0:02:22.00,Default,,0000,0000,0000,,that each kind of
Dialogue: 0,0:02:22.00,0:02:25.00,Default,,0000,0000,0000,,build on each other, kind of take the ideas
Dialogue: 0,0:02:25.00,0:02:27.00,Default,,0000,0000,0000,,and get a little more sophisticated.
Dialogue: 0,0:02:27.00,0:02:28.00,Default,,0000,0000,0000,,But
Dialogue: 0,0:02:28.00,0:02:31.00,Default,,0000,0000,0000,,by the end of the week, I'm hoping that you're gonna start to see these patterns, and realize
Dialogue: 0,0:02:31.00,0:02:35.00,Default,,0000,0000,0000,,that in some sense the recursive solutions tend to be more alike than different.
Dialogue: 0,0:02:35.00,0:02:37.00,Default,,0000,0000,0000,,Once you have your head around how to solve
Dialogue: 0,0:02:37.00,0:02:41.00,Default,,0000,0000,0000,,one type of problem, you may very well be able to take the exact same technique
Dialogue: 0,0:02:41.00,0:02:43.00,Default,,0000,0000,0000,,and solve several other problems that
Dialogue: 0,0:02:43.00,0:02:46.00,Default,,0000,0000,0000,,may sound different at first glance, but in the end, the recursive structure looks the
Dialogue: 0,0:02:46.00,0:02:47.00,Default,,0000,0000,0000,,same.
Dialogue: 0,0:02:47.00,0:02:54.00,Default,,0000,0000,0000,,So I'd say just hold the discomfort a little bit, and wait to see as
Dialogue: 0,0:02:54.00,0:02:57.00,Default,,0000,0000,0000,,we keep working which example may be the one that kind of sticks out for you to
Dialogue: 0,0:02:57.00,0:02:59.00,Default,,0000,0000,0000,,help you get it through.
Dialogue: 0,0:02:59.00,0:03:02.00,Default,,0000,0000,0000,,So we're gonna start with things that fit in the category of
Dialogue: 0,0:03:02.00,0:03:03.00,Default,,0000,0000,0000,,functional recursion.
Dialogue: 0,0:03:03.00,0:03:05.00,Default,,0000,0000,0000,,The functional in this case just says that
Dialogue: 0,0:03:05.00,0:03:09.00,Default,,0000,0000,0000,,you're writing functions that return some non-void thing, an integer, a string,
Dialogue: 0,0:03:09.00,0:03:10.00,Default,,0000,0000,0000,,some
Dialogue: 0,0:03:10.00,0:03:12.00,Default,,0000,0000,0000,,vector of results, or whatever that is,
Dialogue: 0,0:03:12.00,0:03:14.00,Default,,0000,0000,0000,,and that's all it means to be a functional recursion. It's a recursive
Dialogue: 0,0:03:14.00,0:03:18.00,Default,,0000,0000,0000,,function that has a result to it. And because of the recursive nature, it's gonna
Dialogue: 0,0:03:18.00,0:03:22.00,Default,,0000,0000,0000,,say that the outer problem's result, the answer to the larger problem is gonna be
Dialogue: 0,0:03:22.00,0:03:26.00,Default,,0000,0000,0000,,based on making calls, one or more calls to the function itself to get the answer
Dialogue: 0,0:03:26.00,0:03:30.00,Default,,0000,0000,0000,,to a smaller problem, and then adding them, multiplying them, comparing them to decide
Dialogue: 0,0:03:30.00,0:03:33.00,Default,,0000,0000,0000,,how to formulate the larger answer.
Dialogue: 0,0:03:33.00,0:03:35.00,Default,,0000,0000,0000,,All recursive
Dialogue: 0,0:03:35.00,0:03:35.00,Default,,0000,0000,0000,,code
Dialogue: 0,0:03:35.00,0:03:38.00,Default,,0000,0000,0000,,follows the same decomposition
Dialogue: 0,0:03:38.00,0:03:42.00,Default,,0000,0000,0000,,into two cases. Sometimes there's some subdivisions within there, but two general
Dialogue: 0,0:03:42.00,0:03:43.00,Default,,0000,0000,0000,,cases.
Dialogue: 0,0:03:43.00,0:03:45.00,Default,,0000,0000,0000,,The first thing - this base case.
Dialogue: 0,0:03:45.00,0:03:48.00,Default,,0000,0000,0000,,That's something that the recursion eventually has to stop.
Dialogue: 0,0:03:48.00,0:03:52.00,Default,,0000,0000,0000,,We keep saying take the task and break it down, make it a little smaller,
Dialogue: 0,0:03:52.00,0:03:55.00,Default,,0000,0000,0000,,but at some point we really have to stop doing that. We can't
Dialogue: 0,0:03:55.00,0:03:57.00,Default,,0000,0000,0000,,go on infinitely.
Dialogue: 0,0:03:57.00,0:04:00.00,Default,,0000,0000,0000,,There has to be some base case, the simplest possible version of the problem that
Dialogue: 0,0:04:00.00,0:04:05.00,Default,,0000,0000,0000,,you can directly solve. You don't need to make any further recursive calls. So the idea
Dialogue: 0,0:04:05.00,0:04:10.00,Default,,0000,0000,0000,,is that it kinda bottoms out there, and then allows the recursion to kind of
Dialogue: 0,0:04:10.00,0:04:10.00,Default,,0000,0000,0000,,unwind.
Dialogue: 0,0:04:10.00,0:04:12.00,Default,,0000,0000,0000,,The recursive cases,
Dialogue: 0,0:04:12.00,0:04:15.00,Default,,0000,0000,0000,,and there may be one or more of these, are the cases where it's not that simple, that the
Dialogue: 0,0:04:15.00,0:04:20.00,Default,,0000,0000,0000,,answer isn't directly solvable, but if you had the answer to a smaller, simpler
Dialogue: 0,0:04:20.00,0:04:20.00,Default,,0000,0000,0000,,version, you
Dialogue: 0,0:04:20.00,0:04:24.00,Default,,0000,0000,0000,,would be able to assemble that answer you're looking for
Dialogue: 0,0:04:24.00,0:04:27.00,Default,,0000,0000,0000,,using that information from the recursive call.
Dialogue: 0,0:04:27.00,0:04:31.00,Default,,0000,0000,0000,,So that's the kind of structure that they all look like. If I'm
Dialogue: 0,0:04:31.00,0:04:34.00,Default,,0000,0000,0000,,at the base case, then do the base case and return it.
Dialogue: 0,0:04:34.00,0:04:37.00,Default,,0000,0000,0000,,Otherwise, make some recursive calls, and
Dialogue: 0,0:04:37.00,0:04:43.00,Default,,0000,0000,0000,,use that to return a result from this iteration.
Dialogue: 0,0:04:43.00,0:04:45.00,Default,,0000,0000,0000,,So let's first look at something that
Dialogue: 0,0:04:45.00,0:04:48.00,Default,,0000,0000,0000,,- the first couple examples that I'm gonna show you actually are gonna be so
Dialogue: 0,0:04:48.00,0:04:52.00,Default,,0000,0000,0000,,easy that in some sense they're almost gonna be a little bit counterproductive because they're gonna
Dialogue: 0,0:04:52.00,0:04:54.00,Default,,0000,0000,0000,,teach you that recursion lets you do things that you already
Dialogue: 0,0:04:54.00,0:04:57.00,Default,,0000,0000,0000,,know how to do. And then I'm gonna work my way up to ones that actually
Dialogue: 0,0:04:57.00,0:04:59.00,Default,,0000,0000,0000,,get beyond that.
Dialogue: 0,0:04:59.00,0:05:02.00,Default,,0000,0000,0000,,But let's look at first the raise to power.
Dialogue: 0,0:05:02.00,0:05:05.00,Default,,0000,0000,0000,,C++ has no built-in exponentiation operator. There's nothing that raises
Dialogue: 0,0:05:05.00,0:05:07.00,Default,,0000,0000,0000,,a base to a particular exponent
Dialogue: 0,0:05:07.00,0:05:08.00,Default,,0000,0000,0000,,in the operator set.
Dialogue: 0,0:05:08.00,0:05:12.00,Default,,0000,0000,0000,,So if you want it, you need to write it, or you can use - there's a math library called
Dialogue: 0,0:05:12.00,0:05:15.00,Default,,0000,0000,0000,,pow for raise to power. We're gonna run our own version of it
Dialogue: 0,0:05:15.00,0:05:17.00,Default,,0000,0000,0000,,because it's gonna give us some practice thing about this.
Dialogue: 0,0:05:17.00,0:05:20.00,Default,,0000,0000,0000,,The first one I'm gonna show you is one that should feel very familiar and
Dialogue: 0,0:05:20.00,0:05:24.00,Default,,0000,0000,0000,,very intuitive, which is using an iterative formulation. If I'm
Dialogue: 0,0:05:24.00,0:05:27.00,Default,,0000,0000,0000,,trying to raise the base to the exponent, then that's really simply
Dialogue: 0,0:05:27.00,0:05:30.00,Default,,0000,0000,0000,,multiplying base by itself exponent times.
Dialogue: 0,0:05:30.00,0:05:31.00,Default,,0000,0000,0000,,So this one
Dialogue: 0,0:05:31.00,0:05:32.00,Default,,0000,0000,0000,,uses a for loop
Dialogue: 0,0:05:32.00,0:05:37.00,Default,,0000,0000,0000,,and does so. It starts the result at one, and for
Dialogue: 0,0:05:37.00,0:05:40.00,Default,,0000,0000,0000,,iterations through the number of exponents keeps
Dialogue: 0,0:05:40.00,0:05:46.00,Default,,0000,0000,0000,,multiplying to get there. So
Dialogue: 0,0:05:46.00,0:05:48.00,Default,,0000,0000,0000,,that one's fine, and it will perfectly work.
Dialogue: 0,0:05:48.00,0:05:51.00,Default,,0000,0000,0000,,I'm gonna show you this alternative way
Dialogue: 0,0:05:51.00,0:05:54.00,Default,,0000,0000,0000,,that starts you thinking about what it means to divide a problem up in a
Dialogue: 0,0:05:54.00,0:05:56.00,Default,,0000,0000,0000,,recursive strategy.
Dialogue: 0,0:05:56.00,0:06:00.00,Default,,0000,0000,0000,,Base to the exponent - I wanna raise five to the tenth power. If
Dialogue: 0,0:06:00.00,0:06:05.00,Default,,0000,0000,0000,,I had around some delegate, some
Dialogue: 0,0:06:05.00,0:06:08.00,Default,,0000,0000,0000,,clone of myself that I could dispatch to solve
Dialogue: 0,0:06:08.00,0:06:11.00,Default,,0000,0000,0000,,the slightly smaller problem of computing five to the ninth power,
Dialogue: 0,0:06:11.00,0:06:15.00,Default,,0000,0000,0000,,then all I would need to do is take that answer and multiply it by one more five, and I'd get
Dialogue: 0,0:06:15.00,0:06:17.00,Default,,0000,0000,0000,,five to the tenth.
Dialogue: 0,0:06:17.00,0:06:19.00,Default,,0000,0000,0000,,Okay.
Dialogue: 0,0:06:19.00,0:06:22.00,Default,,0000,0000,0000,,If I write code
Dialogue: 0,0:06:22.00,0:06:25.00,Default,,0000,0000,0000,,that's based on that,
Dialogue: 0,0:06:25.00,0:06:28.00,Default,,0000,0000,0000,,then I end up with something here - and I'm gonna
Dialogue: 0,0:06:28.00,0:06:31.00,Default,,0000,0000,0000,,let these two things go through to show us
Dialogue: 0,0:06:31.00,0:06:32.00,Default,,0000,0000,0000,,that
Dialogue: 0,0:06:32.00,0:06:34.00,Default,,0000,0000,0000,,to compute the answer to five
Dialogue: 0,0:06:34.00,0:06:36.00,Default,,0000,0000,0000,,to the tenth power,
Dialogue: 0,0:06:36.00,0:06:38.00,Default,,0000,0000,0000,,what I really need is the answer to five
Dialogue: 0,0:06:38.00,0:06:42.00,Default,,0000,0000,0000,,to the ninth power, which I do by making a recursive call to the same function I'm in
Dialogue: 0,0:06:42.00,0:06:43.00,Default,,0000,0000,0000,,the middle of writing.
Dialogue: 0,0:06:43.00,0:06:45.00,Default,,0000,0000,0000,,So this is raise that I'm
Dialogue: 0,0:06:45.00,0:06:49.00,Default,,0000,0000,0000,,defining, and in the body of it, it makes a call to raise. That's what is the
Dialogue: 0,0:06:49.00,0:06:51.00,Default,,0000,0000,0000,,mark of a recursive function here. I
Dialogue: 0,0:06:51.00,0:06:55.00,Default,,0000,0000,0000,,pass slightly different arguments. In this case, one smaller exponent
Dialogue: 0,0:06:55.00,0:06:57.00,Default,,0000,0000,0000,,which is getting a little bit closer
Dialogue: 0,0:06:57.00,0:07:00.00,Default,,0000,0000,0000,,to that simplest possible case
Dialogue: 0,0:07:00.00,0:07:02.00,Default,,0000,0000,0000,,that we will eventually terminate at where
Dialogue: 0,0:07:02.00,0:07:07.00,Default,,0000,0000,0000,,we can say I don't need to further dispatch any delegates and any clones out there
Dialogue: 0,0:07:07.00,0:07:08.00,Default,,0000,0000,0000,,to do the work, but if
Dialogue: 0,0:07:08.00,0:07:11.00,Default,,0000,0000,0000,,the exponent I'm raising it to is zero, by
Dialogue: 0,0:07:11.00,0:07:16.00,Default,,0000,0000,0000,,definition anything raised to the exponent of zero is one, I could just stop there.
Dialogue: 0,0:07:16.00,0:07:19.00,Default,,0000,0000,0000,,So when computing five to the tenth, we're gonna
Dialogue: 0,0:07:19.00,0:07:21.00,Default,,0000,0000,0000,,see some recursion at work. Let me
Dialogue: 0,0:07:21.00,0:07:24.00,Default,,0000,0000,0000,,take this code into the compiler
Dialogue: 0,0:07:24.00,0:07:27.00,Default,,0000,0000,0000,,
Dialogue: 0,0:07:27.00,0:07:31.00,Default,,0000,0000,0000,,so that we can see a little bit about how this actually works
Dialogue: 0,0:07:31.00,0:07:32.00,Default,,0000,0000,0000,,in terms of that.
Dialogue: 0,0:07:32.00,0:07:35.00,Default,,0000,0000,0000,,So that's exactly the code I have there, but
Dialogue: 0,0:07:35.00,0:07:42.00,Default,,0000,0000,0000,,I can say
Dialogue: 0,0:07:42.00,0:07:43.00,Default,,0000,0000,0000,,something that I
Dialogue: 0,0:07:43.00,0:07:46.00,Default,,0000,0000,0000,,know the answer to. How about that?
Dialogue: 0,0:07:46.00,0:07:49.00,Default,,0000,0000,0000,,
Dialogue: 0,0:07:49.00,0:07:51.00,Default,,0000,0000,0000,,First, we'll take a look at it
Dialogue: 0,0:07:51.00,0:07:55.00,Default,,0000,0000,0000,,doing its work, so five times five times five should be 125.
Dialogue: 0,0:07:55.00,0:07:57.00,Default,,0000,0000,0000,,So we can test a couple
Dialogue: 0,0:07:57.00,0:07:58.00,Default,,0000,0000,0000,,little
Dialogue: 0,0:07:58.00,0:08:01.00,Default,,0000,0000,0000,,values while we're at it. Two the sixth power, that should be
Dialogue: 0,0:08:01.00,0:08:07.00,Default,,0000,0000,0000,,64, just to see a couple of the cases, just to feel good about what's going on.
Dialogue: 0,0:08:07.00,0:08:10.00,Default,,0000,0000,0000,,And then raising say 23 to the zero power
Dialogue: 0,0:08:10.00,0:08:11.00,Default,,0000,0000,0000,,should be one
Dialogue: 0,0:08:11.00,0:08:14.00,Default,,0000,0000,0000,,as anything raised to the zero power should be.
Dialogue: 0,0:08:14.00,0:08:16.00,Default,,0000,0000,0000,,So a little bit of spot testing
Dialogue: 0,0:08:16.00,0:08:18.00,Default,,0000,0000,0000,,to feel good about what's going on.
Dialogue: 0,0:08:18.00,0:08:22.00,Default,,0000,0000,0000,,Now I'm gonna go back to this idea like two to the sixth.
Dialogue: 0,0:08:22.00,0:08:24.00,Default,,0000,0000,0000,,And I'm gonna set a breakpoint here.
Dialogue: 0,0:08:24.00,0:08:25.00,Default,,0000,0000,0000,,Get my breakpoint out.
Dialogue: 0,0:08:25.00,0:08:36.00,Default,,0000,0000,0000,,And I'm gonna run this guy in the debugger.
Dialogue: 0,0:08:36.00,0:08:39.00,Default,,0000,0000,0000,,Takes a little bit longer to get the debugger up and running,
Dialogue: 0,0:08:39.00,0:08:44.00,Default,,0000,0000,0000,,so I'll have to make a little padder up while we're going here.
Dialogue: 0,0:08:44.00,0:08:47.00,Default,,0000,0000,0000,,And then it tells me right now it's breaking on raise, and
Dialogue: 0,0:08:47.00,0:08:53.00,Default,,0000,0000,0000,,I can look around in the debugger. This is a - did not
Dialogue: 0,0:08:53.00,0:08:56.00,Default,,0000,0000,0000,,pick up my compilation? I think it did not. I
Dialogue: 0,0:08:56.00,0:08:59.00,Default,,0000,0000,0000,,must not have saved it right before I did it because it's actually got the base is 23 and the
Dialogue: 0,0:08:59.00,0:09:00.00,Default,,0000,0000,0000,,exponent is zero. It turns
Dialogue: 0,0:09:00.00,0:09:06.00,Default,,0000,0000,0000,,out I don't wanna see that case, so I'm gonna go back and
Dialogue: 0,0:09:06.00,0:09:08.00,Default,,0000,0000,0000,,try again. I
Dialogue: 0,0:09:08.00,0:09:16.00,Default,,0000,0000,0000,,wanna see it -
Dialogue: 0,0:09:16.00,0:09:24.00,Default,,0000,0000,0000,,no, I did not.
Dialogue: 0,0:09:24.00,0:09:28.00,Default,,0000,0000,0000,,And I'm just interested in knowing a little bit about the mechanics of what's gonna happen in a
Dialogue: 0,0:09:28.00,0:09:29.00,Default,,0000,0000,0000,,recursive situation.
Dialogue: 0,0:09:29.00,0:09:33.00,Default,,0000,0000,0000,,If I look at the first time that I hit my breakpoint,
Dialogue: 0,0:09:33.00,0:09:35.00,Default,,0000,0000,0000,,then I'll see that there's a little bit of the beginnings of the
Dialogue: 0,0:09:35.00,0:09:39.00,Default,,0000,0000,0000,,student main, some stuff behind it. There's a little bit of magic underneath your
Dialogue: 0,0:09:39.00,0:09:43.00,Default,,0000,0000,0000,,stack that you don't really need to know about, but starting from main it went into raise,
Dialogue: 0,0:09:43.00,0:09:46.00,Default,,0000,0000,0000,,and the arguments it has there is the base is two, the exponent is six.
Dialogue: 0,0:09:46.00,0:09:50.00,Default,,0000,0000,0000,,If I continue from here, then you'll notice the stack frame got one deeper.
Dialogue: 0,0:09:50.00,0:09:53.00,Default,,0000,0000,0000,,There's actually another indication of raise, and in fact, they're both active at the
Dialogue: 0,0:09:53.00,0:09:54.00,Default,,0000,0000,0000,,same time.
Dialogue: 0,0:09:54.00,0:09:57.00,Default,,0000,0000,0000,,The previous raise that was trying to compute two to the sixth
Dialogue: 0,0:09:57.00,0:10:01.00,Default,,0000,0000,0000,,is kind of in stasis back there waiting for the answer to come back from
Dialogue: 0,0:10:01.00,0:10:05.00,Default,,0000,0000,0000,,this version, which is looking to raise two to the fifth power. I continue again,
Dialogue: 0,0:10:05.00,0:10:08.00,Default,,0000,0000,0000,,I get two to the fourth. I keep doing this. I'm gonna see these guys kinda stack up,
Dialogue: 0,0:10:08.00,0:10:12.00,Default,,0000,0000,0000,,each one of those kind of waiting for the delegate or the clone
Dialogue: 0,0:10:12.00,0:10:17.00,Default,,0000,0000,0000,,to come back with that answer, so that then it can do its further work
Dialogue: 0,0:10:17.00,0:10:19.00,Default,,0000,0000,0000,,incorporating that result to compute the thing it needed to do.
Dialogue: 0,0:10:19.00,0:10:22.00,Default,,0000,0000,0000,,I get down here to raising
Dialogue: 0,0:10:22.00,0:10:24.00,Default,,0000,0000,0000,,two to the first power,
Dialogue: 0,0:10:24.00,0:10:26.00,Default,,0000,0000,0000,,and then finally I get to two to the zero,
Dialogue: 0,0:10:26.00,0:10:29.00,Default,,0000,0000,0000,,so now I've got these eight or so stacked frames,
Dialogue: 0,0:10:29.00,0:10:30.00,Default,,0000,0000,0000,,six up there.
Dialogue: 0,0:10:30.00,0:10:32.00,Default,,0000,0000,0000,,This one, if I step
Dialogue: 0,0:10:32.00,0:10:34.00,Default,,0000,0000,0000,,from here,
Dialogue: 0,0:10:34.00,0:10:37.00,Default,,0000,0000,0000,,it's gonna hit the base case of returning one,
Dialogue: 0,0:10:37.00,0:10:39.00,Default,,0000,0000,0000,,and then
Dialogue: 0,0:10:39.00,0:10:43.00,Default,,0000,0000,0000,,we will end up kind of working our way back out. So now, we are
Dialogue: 0,0:10:43.00,0:10:46.00,Default,,0000,0000,0000,,at the end of the two to the one case
Dialogue: 0,0:10:46.00,0:10:49.00,Default,,0000,0000,0000,,that's using the answer it got from the other one, multiplying it by two.
Dialogue: 0,0:10:49.00,0:10:53.00,Default,,0000,0000,0000,,Now I'm at the two to the two case, and so each of them's kind of unfolding in the stack is
Dialogue: 0,0:10:53.00,0:10:55.00,Default,,0000,0000,0000,,what's called unwinding. It's popping back off
Dialogue: 0,0:10:55.00,0:10:57.00,Default,,0000,0000,0000,,the stack frames that are there
Dialogue: 0,0:10:57.00,0:11:01.00,Default,,0000,0000,0000,,and kind of revisiting them, each passing up the information it got back,
Dialogue: 0,0:11:01.00,0:11:04.00,Default,,0000,0000,0000,,and eventually telling us that
Dialogue: 0,0:11:04.00,0:11:08.00,Default,,0000,0000,0000,,the answer was 64, so I will let that go.
Dialogue: 0,0:11:08.00,0:11:15.00,Default,,0000,0000,0000,,
Dialogue: 0,0:11:15.00,0:11:17.00,Default,,0000,0000,0000,,So the idea that
Dialogue: 0,0:11:17.00,0:11:21.00,Default,,0000,0000,0000,,all of those stack frames kind of exist at the same time - they're all being maintained
Dialogue: 0,0:11:21.00,0:11:24.00,Default,,0000,0000,0000,,independently, so the idea that the compiler isn't confused by the idea that raise is
Dialogue: 0,0:11:24.00,0:11:26.00,Default,,0000,0000,0000,,invoking raise which is invoking raise,
Dialogue: 0,0:11:26.00,0:11:30.00,Default,,0000,0000,0000,,that each of the raise stack frames is distinct from the other ones, so the
Dialogue: 0,0:11:30.00,0:11:33.00,Default,,0000,0000,0000,,indications are actually kept separate. So one had two to the sixth, the next one had two to
Dialogue: 0,0:11:33.00,0:11:35.00,Default,,0000,0000,0000,,the fifth, and so on.
Dialogue: 0,0:11:35.00,0:11:36.00,Default,,0000,0000,0000,,And then eventually
Dialogue: 0,0:11:36.00,0:11:37.00,Default,,0000,0000,0000,,we
Dialogue: 0,0:11:37.00,0:11:40.00,Default,,0000,0000,0000,,need to make some progress toward that base case, so that we can then
Dialogue: 0,0:11:40.00,0:11:42.00,Default,,0000,0000,0000,,stop that recursion
Dialogue: 0,0:11:42.00,0:11:43.00,Default,,0000,0000,0000,,and unwind.
Dialogue: 0,0:11:43.00,0:11:47.00,Default,,0000,0000,0000,,Let me actually show you something while I'm here, which is one thing that's
Dialogue: 0,0:11:47.00,0:11:48.00,Default,,0000,0000,0000,,a pretty common mistake
Dialogue: 0,0:11:48.00,0:11:51.00,Default,,0000,0000,0000,,to make early on in a recursion is to somehow fail to make progress toward
Dialogue: 0,0:11:51.00,0:11:53.00,Default,,0000,0000,0000,,that base case
Dialogue: 0,0:11:53.00,0:11:57.00,Default,,0000,0000,0000,,or to
Dialogue: 0,0:11:57.00,0:11:58.00,Default,,0000,0000,0000,,-
Dialogue: 0,0:11:58.00,0:12:01.00,Default,,0000,0000,0000,,not all cases make it to the base case. For example, if
Dialogue: 0,0:12:01.00,0:12:03.00,Default,,0000,0000,0000,,I did something where
Dialogue: 0,0:12:03.00,0:12:06.00,Default,,0000,0000,0000,,I forgot to
Dialogue: 0,0:12:06.00,0:12:07.00,Default,,0000,0000,0000,,subtract one [cuts out],
Dialogue: 0,0:12:07.00,0:12:10.00,Default,,0000,0000,0000,,and I said oh yeah, I need to [cuts out]. In this case, I'm passing it exactly the
Dialogue: 0,0:12:10.00,0:12:13.00,Default,,0000,0000,0000,,same arguments I got.
Dialogue: 0,0:12:13.00,0:12:16.00,Default,,0000,0000,0000,,If I do this and I run this guy,
Dialogue: 0,0:12:16.00,0:12:19.00,Default,,0000,0000,0000,,then what's gonna happen is it's gonna go two to the sixth, two to the sixth, two to the sixth,
Dialogue: 0,0:12:19.00,0:12:20.00,Default,,0000,0000,0000,,and I'm gonna
Dialogue: 0,0:12:20.00,0:12:21.00,Default,,0000,0000,0000,,let go of
Dialogue: 0,0:12:21.00,0:12:23.00,Default,,0000,0000,0000,,this breakpoint here because
Dialogue: 0,0:12:23.00,0:12:30.00,Default,,0000,0000,0000,,I don't really wanna watch it all happening.
Dialogue: 0,0:12:30.00,0:12:31.00,Default,,0000,0000,0000,,And there it goes.
Dialogue: 0,0:12:31.00,0:12:35.00,Default,,0000,0000,0000,,Loading 6,493 stack frames, zero percent completed, so
Dialogue: 0,0:12:35.00,0:12:38.00,Default,,0000,0000,0000,,that's gonna take a while as you
Dialogue: 0,0:12:38.00,0:12:41.00,Default,,0000,0000,0000,,can imaging. And usually, once you see this error message, it's your clue to say I
Dialogue: 0,0:12:41.00,0:12:45.00,Default,,0000,0000,0000,,can cancel, I know what happened. The only reason I should've
Dialogue: 0,0:12:45.00,0:12:46.00,Default,,0000,0000,0000,,gotten
Dialogue: 0,0:12:46.00,0:12:50.00,Default,,0000,0000,0000,,6,500 stack frames loaded up is because I made a mistake that
Dialogue: 0,0:12:50.00,0:12:53.00,Default,,0000,0000,0000,,caused the stack to totally overflow.
Dialogue: 0,0:12:53.00,0:12:57.00,Default,,0000,0000,0000,,So the behavior in C++ or C is that when you have
Dialogue: 0,0:12:57.00,0:13:01.00,Default,,0000,0000,0000,,so many of those stack frames, eventually the space that's been allocated or set
Dialogue: 0,0:13:01.00,0:13:03.00,Default,,0000,0000,0000,,aside for the function stack will be exhausted.
Dialogue: 0,0:13:03.00,0:13:05.00,Default,,0000,0000,0000,,It will use all the space it has,
Dialogue: 0,0:13:05.00,0:13:09.00,Default,,0000,0000,0000,,and run up against a boundary, and typically report it in some way that
Dialogue: 0,0:13:09.00,0:13:13.00,Default,,0000,0000,0000,,suggests - sometimes you'll see stack overflow, stack out of memory error.
Dialogue: 0,0:13:13.00,0:13:14.00,Default,,0000,0000,0000,,
Dialogue: 0,0:13:14.00,0:13:15.00,Default,,0000,0000,0000,,In this case, it's showing you the
Dialogue: 0,0:13:15.00,0:13:17.00,Default,,0000,0000,0000,,7,000 stack frames that
Dialogue: 0,0:13:17.00,0:13:20.00,Default,,0000,0000,0000,,are behind you, and then if you were to examine them you would see they all have exactly the
Dialogue: 0,0:13:20.00,0:13:24.00,Default,,0000,0000,0000,,same argument, so they weren't getting anywhere.
Dialogue: 0,0:13:24.00,0:13:27.00,Default,,0000,0000,0000,,I'm not gonna actually let it do that because I'm
Dialogue: 0,0:13:27.00,0:13:28.00,Default,,0000,0000,0000,,too impatient.
Dialogue: 0,0:13:28.00,0:13:29.00,Default,,0000,0000,0000,,Let
Dialogue: 0,0:13:29.00,0:13:30.00,Default,,0000,0000,0000,,me fix this code while I'm here.
Dialogue: 0,0:13:30.00,0:13:33.00,Default,,0000,0000,0000,,But other things like even this code that actually looks correct for
Dialogue: 0,0:13:33.00,0:13:39.00,Default,,0000,0000,0000,,some situations also has a subtle bug in it. Even if
Dialogue: 0,0:13:39.00,0:13:40.00,Default,,0000,0000,0000,,I fixed this, which is
Dialogue: 0,0:13:40.00,0:13:44.00,Default,,0000,0000,0000,,that, right now it assumed that the exponent is positive,
Dialogue: 0,0:13:44.00,0:13:46.00,Default,,0000,0000,0000,,that it's some number
Dialogue: 0,0:13:46.00,0:13:47.00,Default,,0000,0000,0000,,
Dialogue: 0,0:13:47.00,0:13:49.00,Default,,0000,0000,0000,,that I can subtract my way down to zero.
Dialogue: 0,0:13:49.00,0:13:53.00,Default,,0000,0000,0000,,If I actually miscalled raise, and I gave it a negative exponent, it would
Dialogue: 0,0:13:53.00,0:13:57.00,Default,,0000,0000,0000,,go into infinite recursion as well. If you started it
Dialogue: 0,0:13:57.00,0:14:00.00,Default,,0000,0000,0000,,at ten to the negative first power, it would go negative first, negative second, negative
Dialogue: 0,0:14:00.00,0:14:02.00,Default,,0000,0000,0000,,third.
Dialogue: 0,0:14:02.00,0:14:05.00,Default,,0000,0000,0000,,6,500 stack frames later, we'd run out of space.
Dialogue: 0,0:14:05.00,0:14:08.00,Default,,0000,0000,0000,,In this case, since we're only intending to handle those positive powers, we
Dialogue: 0,0:14:08.00,0:14:12.00,Default,,0000,0000,0000,,could just put an error that was like if the exponent is less than zero then
Dialogue: 0,0:14:12.00,0:14:14.00,Default,,0000,0000,0000,,raise an error and don't even
Dialogue: 0,0:14:14.00,0:14:21.00,Default,,0000,0000,0000,,try to do anything with it. Okay. So let
Dialogue: 0,0:14:21.00,0:14:25.00,Default,,0000,0000,0000,,me show you a slightly different way of doing this that's also recursive,
Dialogue: 0,0:14:25.00,0:14:28.00,Default,,0000,0000,0000,,but that actually gets the answer a little bit more efficiently.
Dialogue: 0,0:14:28.00,0:14:31.00,Default,,0000,0000,0000,,This is a different way of dividing it up, but still using a
Dialogue: 0,0:14:31.00,0:14:36.00,Default,,0000,0000,0000,,recursive strategy which is that if I'm trying to compute five to the tenth power,
Dialogue: 0,0:14:36.00,0:14:40.00,Default,,0000,0000,0000,,but if I have the answer not of five to ninth power, but instead I have the
Dialogue: 0,0:14:40.00,0:14:42.00,Default,,0000,0000,0000,,answer of five to the fifth power,
Dialogue: 0,0:14:42.00,0:14:44.00,Default,,0000,0000,0000,,and then I multiply that by itself,
Dialogue: 0,0:14:44.00,0:14:48.00,Default,,0000,0000,0000,,I would get that five to the tenth power that I seek.
Dialogue: 0,0:14:48.00,0:14:51.00,Default,,0000,0000,0000,,And then there's a little bit of a case though of what if the power I was trying to
Dialogue: 0,0:14:51.00,0:14:54.00,Default,,0000,0000,0000,,get was odd, if I was trying to raise it to the eleventh power, I could compute the
Dialogue: 0,0:14:54.00,0:14:58.00,Default,,0000,0000,0000,,half power which get me to the fifth - multiplied by the fifth, but then I need
Dialogue: 0,0:14:58.00,0:14:59.00,Default,,0000,0000,0000,,one more
Dialogue: 0,0:14:59.00,0:15:04.00,Default,,0000,0000,0000,,base multiplied in there to make up for that half. Okay.
Dialogue: 0,0:15:04.00,0:15:05.00,Default,,0000,0000,0000,,And so I can write
Dialogue: 0,0:15:05.00,0:15:08.00,Default,,0000,0000,0000,,another recursive formulation here. Same
Dialogue: 0,0:15:08.00,0:15:11.00,Default,,0000,0000,0000,,sort of base case about
Dialogue: 0,0:15:11.00,0:15:14.00,Default,,0000,0000,0000,,detecting when we've gotten down, but then in this case the recursive call we make is
Dialogue: 0,0:15:14.00,0:15:17.00,Default,,0000,0000,0000,,to base of the exponent divided by two,
Dialogue: 0,0:15:17.00,0:15:19.00,Default,,0000,0000,0000,,and then we use it with an
Dialogue: 0,0:15:19.00,0:15:23.00,Default,,0000,0000,0000,,if else whether the exponent was even or odd, it decided whether to just square
Dialogue: 0,0:15:23.00,0:15:25.00,Default,,0000,0000,0000,,that number or whether to square it and
Dialogue: 0,0:15:25.00,0:15:28.00,Default,,0000,0000,0000,,tack in another power of the base while we're at it.
Dialogue: 0,0:15:28.00,0:15:31.00,Default,,0000,0000,0000,,So this one is gonna be much more quick about getting down to it,
Dialogue: 0,0:15:31.00,0:15:34.00,Default,,0000,0000,0000,,whereas the one we saw was gonna put one stack frame down for every
Dialogue: 0,0:15:34.00,0:15:35.00,Default,,0000,0000,0000,,
Dialogue: 0,0:15:35.00,0:15:39.00,Default,,0000,0000,0000,,successive exponent power. So if you wanted to raise something to the 10th, or 20th,
Dialogue: 0,0:15:39.00,0:15:41.00,Default,,0000,0000,0000,,or 30th power, then you were
Dialogue: 0,0:15:41.00,0:15:43.00,Default,,0000,0000,0000,,giving yourself 10, 20, 30 stack frames.
Dialogue: 0,0:15:43.00,0:15:46.00,Default,,0000,0000,0000,,Something like 30 stack frames is not really something to be worried
Dialogue: 0,0:15:46.00,0:15:48.00,Default,,0000,0000,0000,,about, but if you were really trying to make this work on much larger
Dialogue: 0,0:15:48.00,0:15:49.00,Default,,0000,0000,0000,,numbers,
Dialogue: 0,0:15:49.00,0:15:52.00,Default,,0000,0000,0000,,which would require some other work because exponent
Dialogue: 0,0:15:52.00,0:15:55.00,Default,,0000,0000,0000,,is a very rapidly growing operator and would overflow your integers quickly,
Dialogue: 0,0:15:55.00,0:15:57.00,Default,,0000,0000,0000,,but this way
Dialogue: 0,0:15:57.00,0:16:00.00,Default,,0000,0000,0000,,very quickly divides in half. So it goes from a power of 100, to a power of
Dialogue: 0,0:16:00.00,0:16:05.00,Default,,0000,0000,0000,,50, to 25, to 12, to 6, to 3, to 2, to 1, so
Dialogue: 0,0:16:05.00,0:16:08.00,Default,,0000,0000,0000,,that dividing in half is a much quicker way to work our way down to that base case
Dialogue: 0,0:16:08.00,0:16:12.00,Default,,0000,0000,0000,,and get our answer back, and we're doing a lot fewer calculations
Dialogue: 0,0:16:12.00,0:16:14.00,Default,,0000,0000,0000,,than all those multiplies,
Dialogue: 0,0:16:14.00,0:16:16.00,Default,,0000,0000,0000,,one per
Dialogue: 0,0:16:16.00,0:16:19.00,Default,,0000,0000,0000,,base. So just a little
Dialogue: 0,0:16:19.00,0:16:21.00,Default,,0000,0000,0000,,diversion.
Dialogue: 0,0:16:21.00,0:16:22.00,Default,,0000,0000,0000,,So let me tell you something,
Dialogue: 0,0:16:22.00,0:16:23.00,Default,,0000,0000,0000,,just a little bit about
Dialogue: 0,0:16:23.00,0:16:27.00,Default,,0000,0000,0000,,kind of style as it applies to recursion.
Dialogue: 0,0:16:27.00,0:16:28.00,Default,,0000,0000,0000,,Recursion is
Dialogue: 0,0:16:28.00,0:16:34.00,Default,,0000,0000,0000,,really best when you can express it in the most kind of direct, clear, and
Dialogue: 0,0:16:34.00,0:16:36.00,Default,,0000,0000,0000,,simple code.
Dialogue: 0,0:16:36.00,0:16:38.00,Default,,0000,0000,0000,,It's hard enough to get your head around a recursive formulation
Dialogue: 0,0:16:38.00,0:16:42.00,Default,,0000,0000,0000,,without complicating it by having a bunch of extraneous parts where
Dialogue: 0,0:16:42.00,0:16:43.00,Default,,0000,0000,0000,,you're
Dialogue: 0,0:16:43.00,0:16:47.00,Default,,0000,0000,0000,,doing more work than necessary, or redundantly handling certain things. And
Dialogue: 0,0:16:47.00,0:16:49.00,Default,,0000,0000,0000,,one thing that's actually very easy to fall in the trap of
Dialogue: 0,0:16:49.00,0:16:52.00,Default,,0000,0000,0000,,is thinking about there's lots of other base cases you might be able to
Dialogue: 0,0:16:52.00,0:16:56.00,Default,,0000,0000,0000,,easily handle, so why not just go ahead and call out for them,
Dialogue: 0,0:16:56.00,0:16:57.00,Default,,0000,0000,0000,,test for
Dialogue: 0,0:16:57.00,0:16:59.00,Default,,0000,0000,0000,,- you're at the base case. You're close to the base case.
Dialogue: 0,0:16:59.00,0:17:02.00,Default,,0000,0000,0000,,Checking before you might make a recursive call, if you're gonna hit the base case when you
Dialogue: 0,0:17:02.00,0:17:08.00,Default,,0000,0000,0000,,make that call, then why make the call. I'll just anticipate and get the answer it
Dialogue: 0,0:17:08.00,0:17:09.00,Default,,0000,0000,0000,,would've returned anyway.
Dialogue: 0,0:17:09.00,0:17:13.00,Default,,0000,0000,0000,,It can lead to code that looks a little bit like this before you're done. If the
Dialogue: 0,0:17:13.00,0:17:16.00,Default,,0000,0000,0000,,exponent's zero, that's one. If the exponent's one, then I can just
Dialogue: 0,0:17:16.00,0:17:19.00,Default,,0000,0000,0000,,return the base. If it's two, then I can just multiply the base by itself. If it's
Dialogue: 0,0:17:19.00,0:17:20.00,Default,,0000,0000,0000,,three, I can start doing this.
Dialogue: 0,0:17:20.00,0:17:22.00,Default,,0000,0000,0000,,Certainly, you
Dialogue: 0,0:17:22.00,0:17:25.00,Default,,0000,0000,0000,,can follow this to the point of absurdity, and even for some of the simple
Dialogue: 0,0:17:25.00,0:17:28.00,Default,,0000,0000,0000,,cases, it might seem like you're saving yourself a little bit of extra time. You're like
Dialogue: 0,0:17:28.00,0:17:31.00,Default,,0000,0000,0000,,why go back around and let it make another recursive call. I could stop it right
Dialogue: 0,0:17:31.00,0:17:33.00,Default,,0000,0000,0000,,here. It's easy to know that answer.
Dialogue: 0,0:17:33.00,0:17:36.00,Default,,0000,0000,0000,,But as you do this, it complicates the code. It's a little harder to read. It's
Dialogue: 0,0:17:36.00,0:17:38.00,Default,,0000,0000,0000,,a little harder to
Dialogue: 0,0:17:38.00,0:17:39.00,Default,,0000,0000,0000,,debug.
Dialogue: 0,0:17:39.00,0:17:43.00,Default,,0000,0000,0000,,Really, the expense of making that one extra call, two extra calls
Dialogue: 0,0:17:43.00,0:17:46.00,Default,,0000,0000,0000,,is not the thing to be worried about.
Dialogue: 0,0:17:46.00,0:17:50.00,Default,,0000,0000,0000,,What we really want is the cleanest code that expresses what we do, has the
Dialogue: 0,0:17:50.00,0:17:53.00,Default,,0000,0000,0000,,simplest cases to test, and to examine, and to follow,
Dialogue: 0,0:17:53.00,0:17:56.00,Default,,0000,0000,0000,,and not muck it up with things that in
Dialogue: 0,0:17:56.00,0:17:57.00,Default,,0000,0000,0000,,effect
Dialogue: 0,0:17:57.00,0:18:01.00,Default,,0000,0000,0000,,don't change the computational power of this but just introduce the opportunity for error.
Dialogue: 0,0:18:01.00,0:18:02.00,Default,,0000,0000,0000,,Instead of a
Dialogue: 0,0:18:02.00,0:18:05.00,Default,,0000,0000,0000,,multiply here, I accidentally put a plus.
Dialogue: 0,0:18:05.00,0:18:07.00,Default,,0000,0000,0000,,It might be easy to overlook it
Dialogue: 0,0:18:07.00,0:18:08.00,Default,,0000,0000,0000,,and not realize what I've done,
Dialogue: 0,0:18:08.00,0:18:10.00,Default,,0000,0000,0000,,and then
Dialogue: 0,0:18:10.00,0:18:14.00,Default,,0000,0000,0000,,end up computing the wrong answer when it gets to the base case of two. In fact, if
Dialogue: 0,0:18:14.00,0:18:15.00,Default,,0000,0000,0000,,you do it this
Dialogue: 0,0:18:15.00,0:18:17.00,Default,,0000,0000,0000,,way, most things would stop at three,
Dialogue: 0,0:18:17.00,0:18:20.00,Default,,0000,0000,0000,,but these would suddenly become kind of their own special cases that were only
Dialogue: 0,0:18:20.00,0:18:25.00,Default,,0000,0000,0000,,hit if you directly called them with the two. The recursive cases will all stop earlier. It
Dialogue: 0,0:18:25.00,0:18:28.00,Default,,0000,0000,0000,,just complicates your testing pass now because not everything is going through
Dialogue: 0,0:18:28.00,0:18:31.00,Default,,0000,0000,0000,,the same code.
Dialogue: 0,0:18:31.00,0:18:34.00,Default,,0000,0000,0000,,So we call this arm's length recursion. I put a big X on that
Dialogue: 0,0:18:34.00,0:18:35.00,Default,,0000,0000,0000,,looking ahead,
Dialogue: 0,0:18:35.00,0:18:36.00,Default,,0000,0000,0000,,testing before you get there.
Dialogue: 0,0:18:36.00,0:18:41.00,Default,,0000,0000,0000,,Just let the code fall through.
Dialogue: 0,0:18:41.00,0:18:43.00,Default,,0000,0000,0000,,So
Dialogue: 0,0:18:43.00,0:18:45.00,Default,,0000,0000,0000,,Dan, he's not here today,
Dialogue: 0,0:18:45.00,0:18:48.00,Default,,0000,0000,0000,,but he talked to me at the end of Friday's class, and it made
Dialogue: 0,0:18:48.00,0:18:49.00,Default,,0000,0000,0000,,me
Dialogue: 0,0:18:49.00,0:18:53.00,Default,,0000,0000,0000,,wanna actually just give you a little bit of
Dialogue: 0,0:18:53.00,0:18:54.00,Default,,0000,0000,0000,,insight into
Dialogue: 0,0:18:54.00,0:18:57.00,Default,,0000,0000,0000,,recursion as it relates to
Dialogue: 0,0:18:57.00,0:18:58.00,Default,,0000,0000,0000,,
Dialogue: 0,0:18:58.00,0:19:02.00,Default,,0000,0000,0000,,efficiency. Recursion by itself, just the idea of applying a recursive technique to solving a
Dialogue: 0,0:19:02.00,0:19:06.00,Default,,0000,0000,0000,,problem, does not give you any guarantee that it's gonna be the best solution, the
Dialogue: 0,0:19:06.00,0:19:09.00,Default,,0000,0000,0000,,most efficient solution, or the fact that it's gonna give you a very inefficient solution.
Dialogue: 0,0:19:09.00,0:19:11.00,Default,,0000,0000,0000,,Sometimes people have kind of
Dialogue: 0,0:19:11.00,0:19:11.00,Default,,0000,0000,0000,,a
Dialogue: 0,0:19:11.00,0:19:15.00,Default,,0000,0000,0000,,bad rap on recursion. It's like recursion will definitely be inefficient.
Dialogue: 0,0:19:15.00,0:19:17.00,Default,,0000,0000,0000,,That actually is not guaranteed.
Dialogue: 0,0:19:17.00,0:19:21.00,Default,,0000,0000,0000,,Recursion often requires exactly the same resources as the iterative approach.
Dialogue: 0,0:19:21.00,0:19:24.00,Default,,0000,0000,0000,,It takes the same amount of effort. Surveying the campus - if you're gonna
Dialogue: 0,0:19:24.00,0:19:27.00,Default,,0000,0000,0000,,survey the 10,000 people on campus and get everybody's information back,
Dialogue: 0,0:19:27.00,0:19:30.00,Default,,0000,0000,0000,,whether you're doing it divide and conquer, or whether you're sitting out there in White
Dialogue: 0,0:19:30.00,0:19:30.00,Default,,0000,0000,0000,,Plaza
Dialogue: 0,0:19:30.00,0:19:34.00,Default,,0000,0000,0000,,asking each person one by one, in the end 10,000 people got survey.
Dialogue: 0,0:19:34.00,0:19:36.00,Default,,0000,0000,0000,,The recursion is not
Dialogue: 0,0:19:36.00,0:19:39.00,Default,,0000,0000,0000,,part of what made that longer or shorter. It might actually depending on how you
Dialogue: 0,0:19:39.00,0:19:42.00,Default,,0000,0000,0000,,have resources work out better. Like if you could get a bunch of people in parallel
Dialogue: 0,0:19:42.00,0:19:46.00,Default,,0000,0000,0000,,surveying, you might end up completing the whole thing in less time, but it required
Dialogue: 0,0:19:46.00,0:19:49.00,Default,,0000,0000,0000,,more people, and more clipboards, and more paper
Dialogue: 0,0:19:49.00,0:19:52.00,Default,,0000,0000,0000,,while the process is ongoing than me standing there with one piece of paper and a
Dialogue: 0,0:19:52.00,0:19:57.00,Default,,0000,0000,0000,,clipboard. But then again, it took lots of my time to do it.
Dialogue: 0,0:19:57.00,0:20:00.00,Default,,0000,0000,0000,,So in many situations, it's really no better or no worse
Dialogue: 0,0:20:00.00,0:20:02.00,Default,,0000,0000,0000,,than the alternative. It makes a little bit of some tradeoffs of where the time is
Dialogue: 0,0:20:02.00,0:20:03.00,Default,,0000,0000,0000,,spent.
Dialogue: 0,0:20:03.00,0:20:06.00,Default,,0000,0000,0000,,There are situations though where recursion can actually make something that was
Dialogue: 0,0:20:06.00,0:20:09.00,Default,,0000,0000,0000,,efficient inefficient. There are situations where it can take something that was inefficient and
Dialogue: 0,0:20:09.00,0:20:11.00,Default,,0000,0000,0000,,make it efficient. So
Dialogue: 0,0:20:11.00,0:20:15.00,Default,,0000,0000,0000,,it's more of a case-by-case basis to decide whether recursion is the
Dialogue: 0,0:20:15.00,0:20:18.00,Default,,0000,0000,0000,,right tool if efficiency is one of your primary concerns.
Dialogue: 0,0:20:18.00,0:20:21.00,Default,,0000,0000,0000,,I will say that for problems with simple iterative solutions
Dialogue: 0,0:20:21.00,0:20:24.00,Default,,0000,0000,0000,,that operate relatively efficiently, iteration
Dialogue: 0,0:20:24.00,0:20:26.00,Default,,0000,0000,0000,,is probably the best way to solve it.
Dialogue: 0,0:20:26.00,0:20:27.00,Default,,0000,0000,0000,,So like
Dialogue: 0,0:20:27.00,0:20:31.00,Default,,0000,0000,0000,,the raise to power, yeah you could certainly do that
Dialogue: 0,0:20:31.00,0:20:32.00,Default,,0000,0000,0000,,iteratively. There's not
Dialogue: 0,0:20:32.00,0:20:35.00,Default,,0000,0000,0000,,some huge advantage that recursion is offering. I'm using them here because they're
Dialogue: 0,0:20:35.00,0:20:37.00,Default,,0000,0000,0000,,simple enough to get our head around.
Dialogue: 0,0:20:37.00,0:20:39.00,Default,,0000,0000,0000,,We're gonna work our way toward problems where
Dialogue: 0,0:20:39.00,0:20:42.00,Default,,0000,0000,0000,,we're gonna find things that require recursion, which
Dialogue: 0,0:20:42.00,0:20:45.00,Default,,0000,0000,0000,,is kind of one of the third points I put in. Why do we learn recursion? What's recursion gonna be good
Dialogue: 0,0:20:45.00,0:20:48.00,Default,,0000,0000,0000,,for? First off, recursion is awesome.
Dialogue: 0,0:20:48.00,0:20:52.00,Default,,0000,0000,0000,,There are some problems that you just can't solve using anything but recursion,
Dialogue: 0,0:20:52.00,0:20:55.00,Default,,0000,0000,0000,,so that the alternatives like I'll just write it iteratively won't work.
Dialogue: 0,0:20:55.00,0:20:59.00,Default,,0000,0000,0000,,You'll try, but you'll fail. They inherently have a recursive
Dialogue: 0,0:20:59.00,0:20:59.00,Default,,0000,0000,0000,,structure to them
Dialogue: 0,0:20:59.00,0:21:02.00,Default,,0000,0000,0000,,where recursion is the right tool for the job.
Dialogue: 0,0:21:02.00,0:21:06.00,Default,,0000,0000,0000,,Often, it produces the most beautiful, direct, and clear elegant code.
Dialogue: 0,0:21:06.00,0:21:08.00,Default,,0000,0000,0000,,The next assignment that will go out
Dialogue: 0,0:21:08.00,0:21:11.00,Default,,0000,0000,0000,,has these problems that you do in recursion, and they're each about ten lines
Dialogue: 0,0:21:11.00,0:21:13.00,Default,,0000,0000,0000,,long. Some of them are like five lines long.
Dialogue: 0,0:21:13.00,0:21:18.00,Default,,0000,0000,0000,,They do incredible things in five lines because of the descriptive power of
Dialogue: 0,0:21:18.00,0:21:19.00,Default,,0000,0000,0000,,describing it as
Dialogue: 0,0:21:19.00,0:21:22.00,Default,,0000,0000,0000,,here's a base case, and here's a recursive case, and everything else just follows
Dialogue: 0,0:21:22.00,0:21:23.00,Default,,0000,0000,0000,,from
Dialogue: 0,0:21:23.00,0:21:26.00,Default,,0000,0000,0000,,applying this, and reducing the problem step by step.
Dialogue: 0,0:21:26.00,0:21:28.00,Default,,0000,0000,0000,,So you will see things where
Dialogue: 0,0:21:28.00,0:21:31.00,Default,,0000,0000,0000,,the recursive code is just beautiful, clean, elegant, easy to understand, easy to follow,
Dialogue: 0,0:21:31.00,0:21:32.00,Default,,0000,0000,0000,,easy to test,
Dialogue: 0,0:21:32.00,0:21:34.00,Default,,0000,0000,0000,,solves the recursive problem. And in
Dialogue: 0,0:21:34.00,0:21:37.00,Default,,0000,0000,0000,,those cases, it really is a much better answer than trying to hack up some
Dialogue: 0,0:21:37.00,0:21:39.00,Default,,0000,0000,0000,,other iterative form
Dialogue: 0,0:21:39.00,0:21:41.00,Default,,0000,0000,0000,,that may in the end be
Dialogue: 0,0:21:41.00,0:21:44.00,Default,,0000,0000,0000,,no more efficient. It may be even less efficient. So don't let efficiency be
Dialogue: 0,0:21:44.00,0:21:46.00,Default,,0000,0000,0000,,kind of a big
Dialogue: 0,0:21:46.00,0:21:52.00,Default,,0000,0000,0000,,fear of what recursion is for you. So I'm gonna do more examples.
Dialogue: 0,0:21:52.00,0:21:54.00,Default,,0000,0000,0000,,
Dialogue: 0,0:21:54.00,0:21:56.00,Default,,0000,0000,0000,,I've got three more examples,
Dialogue: 0,0:21:56.00,0:21:58.00,Default,,0000,0000,0000,,or four I think today, so
Dialogue: 0,0:21:58.00,0:22:01.00,Default,,0000,0000,0000,,I will just keep
Dialogue: 0,0:22:01.00,0:22:03.00,Default,,0000,0000,0000,,showing you different things, and hopefully
Dialogue: 0,0:22:03.00,0:22:05.00,Default,,0000,0000,0000,,the patterns will start to kind of
Dialogue: 0,0:22:05.00,0:22:07.00,Default,,0000,0000,0000,,come out of the mist for you.
Dialogue: 0,0:22:07.00,0:22:10.00,Default,,0000,0000,0000,,A palindrome string is one that reads the same forwards and backwards
Dialogue: 0,0:22:10.00,0:22:14.00,Default,,0000,0000,0000,,when reversed. So was it a car or a cat I saw, if you read that
Dialogue: 0,0:22:14.00,0:22:16.00,Default,,0000,0000,0000,,backwards, it turns out
Dialogue: 0,0:22:16.00,0:22:17.00,Default,,0000,0000,0000,,it
Dialogue: 0,0:22:17.00,0:22:21.00,Default,,0000,0000,0000,,says the same thing. Go hang a salami, I'm a lasagna
Dialogue: 0,0:22:21.00,0:22:22.00,Default,,0000,0000,0000,,hog. Also
Dialogue: 0,0:22:22.00,0:22:26.00,Default,,0000,0000,0000,,handy when you need to have a bar bet over what the longest palindrome is
Dialogue: 0,0:22:26.00,0:22:28.00,Default,,0000,0000,0000,,to have these things around.
Dialogue: 0,0:22:28.00,0:22:31.00,Default,,0000,0000,0000,,There are certainly ways to do this iteratively. If you were given a string and you were interested to
Dialogue: 0,0:22:31.00,0:22:33.00,Default,,0000,0000,0000,,know is it a palindrome,
Dialogue: 0,0:22:33.00,0:22:36.00,Default,,0000,0000,0000,,you could kind of do this marching - you're looking outside and kind of marching your way
Dialogue: 0,0:22:36.00,0:22:38.00,Default,,0000,0000,0000,,into the middle.
Dialogue: 0,0:22:38.00,0:22:42.00,Default,,0000,0000,0000,,But we're gonna go ahead and let recursion kinda help us
Dialogue: 0,0:22:42.00,0:22:45.00,Default,,0000,0000,0000,,deal with the subproblem of this,
Dialogue: 0,0:22:45.00,0:22:47.00,Default,,0000,0000,0000,,and imagine that at the simplest possible form - you could say that
Dialogue: 0,0:22:47.00,0:22:49.00,Default,,0000,0000,0000,,a palindrome
Dialogue: 0,0:22:49.00,0:22:51.00,Default,,0000,0000,0000,,consists of
Dialogue: 0,0:22:51.00,0:22:53.00,Default,,0000,0000,0000,,an interior palindrome,
Dialogue: 0,0:22:53.00,0:22:56.00,Default,,0000,0000,0000,,and then the same letter tacked on to the front and the back.
Dialogue: 0,0:22:56.00,0:22:58.00,Default,,0000,0000,0000,,So if you look at was it a car or a cat I saw,
Dialogue: 0,0:22:58.00,0:23:01.00,Default,,0000,0000,0000,,there are two Ws there. It starts and it ends with a W,
Dialogue: 0,0:23:01.00,0:23:04.00,Default,,0000,0000,0000,,so all palindromes must start and end with the same letter. Okay.
Dialogue: 0,0:23:04.00,0:23:05.00,Default,,0000,0000,0000,,Let's check that,
Dialogue: 0,0:23:05.00,0:23:11.00,Default,,0000,0000,0000,,and if that matches, then extract that middle and see if it's a palindrome.
Dialogue: 0,0:23:11.00,0:23:13.00,Default,,0000,0000,0000,,So it feels like I didn't really do anything. It's like
Dialogue: 0,0:23:13.00,0:23:17.00,Default,,0000,0000,0000,,all I did was match two letters, and then I said by the way
Dialogue: 0,0:23:17.00,0:23:19.00,Default,,0000,0000,0000,,delegate this problem
Dialogue: 0,0:23:19.00,0:23:23.00,Default,,0000,0000,0000,,back to myself, making a call to a function I haven't even finished writing
Dialogue: 0,0:23:23.00,0:23:27.00,Default,,0000,0000,0000,,to examine the rest of the letters.
Dialogue: 0,0:23:27.00,0:23:29.00,Default,,0000,0000,0000,,And then I need a base case.
Dialogue: 0,0:23:29.00,0:23:31.00,Default,,0000,0000,0000,,I've got a recursive case, right?
Dialogue: 0,0:23:31.00,0:23:34.00,Default,,0000,0000,0000,,Take off the outer two letters. Make sure they match.
Dialogue: 0,0:23:34.00,0:23:37.00,Default,,0000,0000,0000,,Recur on the inside.
Dialogue: 0,0:23:37.00,0:23:42.00,Default,,0000,0000,0000,,What is the simplest possible palindrome? One letter? One
Dialogue: 0,0:23:42.00,0:23:44.00,Default,,0000,0000,0000,,letter. One letter makes a good palindrome. One letter is by
Dialogue: 0,0:23:44.00,0:23:47.00,Default,,0000,0000,0000,,definition first and last letter are the same letter, so it matches. That's
Dialogue: 0,0:23:47.00,0:23:53.00,Default,,0000,0000,0000,,a great base case. Is it the only base case? [Inaudible]. Two
Dialogue: 0,0:23:53.00,0:23:56.00,Default,,0000,0000,0000,,letters is also kind of important, but there's actually an even
Dialogue: 0,0:23:56.00,0:23:58.00,Default,,0000,0000,0000,,simpler form, right?
Dialogue: 0,0:23:58.00,0:24:02.00,Default,,0000,0000,0000,,It's the empty string. So both the empty string and the single character string are by
Dialogue: 0,0:24:02.00,0:24:05.00,Default,,0000,0000,0000,,definition the world's simplest palindromes. They meet the
Dialogue: 0,0:24:05.00,0:24:08.00,Default,,0000,0000,0000,,requirements that they read the same forward and backwards. Empty string forwards
Dialogue: 0,0:24:08.00,0:24:10.00,Default,,0000,0000,0000,,and backwards is trivially the
Dialogue: 0,0:24:10.00,0:24:14.00,Default,,0000,0000,0000,,same, so that makes it even easier than doing the two-letter case.
Dialogue: 0,0:24:14.00,0:24:17.00,Default,,0000,0000,0000,,So if I write this code to look like that where
Dialogue: 0,0:24:17.00,0:24:19.00,Default,,0000,0000,0000,,if the length of the strength is
Dialogue: 0,0:24:19.00,0:24:24.00,Default,,0000,0000,0000,,one or fewer, so that handles both the zero and the one case, then I return true.
Dialogue: 0,0:24:24.00,0:24:25.00,Default,,0000,0000,0000,,Those are trivial
Dialogue: 0,0:24:25.00,0:24:26.00,Default,,0000,0000,0000,,
Dialogue: 0,0:24:26.00,0:24:28.00,Default,,0000,0000,0000,,palindromes of the easiest
Dialogue: 0,0:24:28.00,0:24:30.00,Default,,0000,0000,0000,,immediate detection.
Dialogue: 0,0:24:30.00,0:24:31.00,Default,,0000,0000,0000,,Otherwise,
Dialogue: 0,0:24:31.00,0:24:33.00,Default,,0000,0000,0000,,I've got a return here that says
Dialogue: 0,0:24:33.00,0:24:35.00,Default,,0000,0000,0000,,if the first character
Dialogue: 0,0:24:35.00,0:24:38.00,Default,,0000,0000,0000,,is the same as the last character,
Dialogue: 0,0:24:38.00,0:24:39.00,Default,,0000,0000,0000,,and the
Dialogue: 0,0:24:39.00,0:24:42.00,Default,,0000,0000,0000,,middle - so the substring starting at Position 1
Dialogue: 0,0:24:42.00,0:24:47.00,Default,,0000,0000,0000,,that goes for length minus two characters that picks up the interior
Dialogue: 0,0:24:47.00,0:24:50.00,Default,,0000,0000,0000,,discarding the first and last characters - if that's also a palindrome, then we've got a
Dialogue: 0,0:24:50.00,0:24:51.00,Default,,0000,0000,0000,,palindrome.
Dialogue: 0,0:24:51.00,0:24:54.00,Default,,0000,0000,0000,,So given the short circuiting nature of the and, if
Dialogue: 0,0:24:54.00,0:24:56.00,Default,,0000,0000,0000,,it looks at the outer two characters and they don't match, it immediately just
Dialogue: 0,0:24:56.00,0:24:58.00,Default,,0000,0000,0000,,stops right there and says false.
Dialogue: 0,0:24:58.00,0:25:01.00,Default,,0000,0000,0000,,If they do match, then it goes on looking
Dialogue: 0,0:25:01.00,0:25:03.00,Default,,0000,0000,0000,,at the next interior pair
Dialogue: 0,0:25:03.00,0:25:07.00,Default,,0000,0000,0000,,which will stack up a recursive call looking at its two things, and eventually we
Dialogue: 0,0:25:07.00,0:25:10.00,Default,,0000,0000,0000,,will either catch a pair that doesn't match,
Dialogue: 0,0:25:10.00,0:25:14.00,Default,,0000,0000,0000,,and then this false will immediately return its way out, or it will keep
Dialogue: 0,0:25:14.00,0:25:17.00,Default,,0000,0000,0000,,going all the way down to that base case, hit a true,
Dialogue: 0,0:25:17.00,0:25:21.00,Default,,0000,0000,0000,,and know that we do have a full palindrome there.
Dialogue: 0,0:25:21.00,0:25:24.00,Default,,0000,0000,0000,,So you could certainly write this with a for loop. Actually, writing
Dialogue: 0,0:25:24.00,0:25:27.00,Default,,0000,0000,0000,,it with a for loop is almost a little bit trickier because you
Dialogue: 0,0:25:27.00,0:25:30.00,Default,,0000,0000,0000,,have to keep track of which part of the string are you on, and what happens when you
Dialogue: 0,0:25:30.00,0:25:34.00,Default,,0000,0000,0000,,get to the middle and things like that. In some sense, the recursive
Dialogue: 0,0:25:34.00,0:25:35.00,Default,,0000,0000,0000,,form really kinda
Dialogue: 0,0:25:35.00,0:25:38.00,Default,,0000,0000,0000,,sidesteps that by really thinking about it in a more holistic way
Dialogue: 0,0:25:38.00,0:25:41.00,Default,,0000,0000,0000,,of like the outer letters plus an inner palindrome
Dialogue: 0,0:25:41.00,0:25:43.00,Default,,0000,0000,0000,,gives me the answer I'm looking for.
Dialogue: 0,0:25:43.00,0:25:46.00,Default,,0000,0000,0000,,So this idea of
Dialogue: 0,0:25:46.00,0:25:49.00,Default,,0000,0000,0000,,taking a function you're in the middle of writing and making a call to it as
Dialogue: 0,0:25:49.00,0:25:50.00,Default,,0000,0000,0000,,though it worked
Dialogue: 0,0:25:50.00,0:25:53.00,Default,,0000,0000,0000,,is something that - they require this idea of the leap of faith.
Dialogue: 0,0:25:53.00,0:25:55.00,Default,,0000,0000,0000,,You haven't even finished describing
Dialogue: 0,0:25:55.00,0:25:58.00,Default,,0000,0000,0000,,how is palindrome operates,
Dialogue: 0,0:25:58.00,0:26:01.00,Default,,0000,0000,0000,,and there you are making a call to it depending on it working in order to get
Dialogue: 0,0:26:01.00,0:26:02.00,Default,,0000,0000,0000,,your
Dialogue: 0,0:26:02.00,0:26:04.00,Default,,0000,0000,0000,,function working. It's a very kind of
Dialogue: 0,0:26:04.00,0:26:06.00,Default,,0000,0000,0000,,wacky thing to get your head around.
Dialogue: 0,0:26:06.00,0:26:08.00,Default,,0000,0000,0000,,It feels a little bit
Dialogue: 0,0:26:08.00,0:26:09.00,Default,,0000,0000,0000,,mystical at first.
Dialogue: 0,0:26:09.00,0:26:11.00,Default,,0000,0000,0000,,
Dialogue: 0,0:26:11.00,0:26:13.00,Default,,0000,0000,0000,,That feeling you feel a little bit
Dialogue: 0,0:26:13.00,0:26:16.00,Default,,0000,0000,0000,,discombobulated about this is probably pretty normal,
Dialogue: 0,0:26:16.00,0:26:17.00,Default,,0000,0000,0000,,but we're gonna
Dialogue: 0,0:26:17.00,0:26:18.00,Default,,0000,0000,0000,,keep seeing examples,
Dialogue: 0,0:26:18.00,0:26:21.00,Default,,0000,0000,0000,,and hope that
Dialogue: 0,0:26:21.00,0:26:23.00,Default,,0000,0000,0000,,it starts to feel a little less unsettling.
Dialogue: 0,0:26:23.00,0:26:26.00,Default,,0000,0000,0000,,Anybody wanna ask a question about this so far? Yeah?
Dialogue: 0,0:26:26.00,0:26:28.00,Default,,0000,0000,0000,,So I guess create your
Dialogue: 0,0:26:28.00,0:26:30.00,Default,,0000,0000,0000,,base case first, then test it? [Inaudible]. That's a great question.
Dialogue: 0,0:26:30.00,0:26:35.00,Default,,0000,0000,0000,,So I would say typically that's a great strategy. Get a base
Dialogue: 0,0:26:35.00,0:26:38.00,Default,,0000,0000,0000,,case and test against the base case, so the one character and the two character
Dialogue: 0,0:26:38.00,0:26:39.00,Default,,0000,0000,0000,,strings.
Dialogue: 0,0:26:39.00,0:26:42.00,Default,,0000,0000,0000,,And then imagine one layer out, things that will make one recursive
Dialogue: 0,0:26:42.00,0:26:46.00,Default,,0000,0000,0000,,call only. So in this case for the palindrome, it's like what's a two-character
Dialogue: 0,0:26:46.00,0:26:47.00,Default,,0000,0000,0000,,string?
Dialogue: 0,0:26:47.00,0:26:50.00,Default,,0000,0000,0000,,One has AB. One has AA. So one that is a palindrome, one that isn't,
Dialogue: 0,0:26:50.00,0:26:52.00,Default,,0000,0000,0000,,and watch it go through.
Dialogue: 0,0:26:52.00,0:26:55.00,Default,,0000,0000,0000,,Then from there you have to almost take that leap and say
Dialogue: 0,0:26:55.00,0:26:58.00,Default,,0000,0000,0000,,it worked for the base case. It worked for one out. And then you have to start
Dialogue: 0,0:26:58.00,0:27:02.00,Default,,0000,0000,0000,,imagining if it worked for a string of length N, it'll work for one of N plus one,
Dialogue: 0,0:27:02.00,0:27:03.00,Default,,0000,0000,0000,,and
Dialogue: 0,0:27:03.00,0:27:07.00,Default,,0000,0000,0000,,that in some sense testing it exhaustively across all strings is
Dialogue: 0,0:27:07.00,0:27:09.00,Default,,0000,0000,0000,,of course impossible, so you have to kind of
Dialogue: 0,0:27:09.00,0:27:12.00,Default,,0000,0000,0000,,move to a sort of larger case where you can't just sit there and trace the whole
Dialogue: 0,0:27:12.00,0:27:15.00,Default,,0000,0000,0000,,thing. You'll have to in some sense take a faith thing that says
Dialogue: 0,0:27:15.00,0:27:18.00,Default,,0000,0000,0000,,if it could have computed whether the interior's a palindrome, then adding two
Dialogue: 0,0:27:18.00,0:27:21.00,Default,,0000,0000,0000,,characters on the outside
Dialogue: 0,0:27:21.00,0:27:21.00,Default,,0000,0000,0000,,
Dialogue: 0,0:27:21.00,0:27:24.00,Default,,0000,0000,0000,,and massaging that with that answer should produce the right thing. So some bigger
Dialogue: 0,0:27:24.00,0:27:26.00,Default,,0000,0000,0000,,tests
Dialogue: 0,0:27:26.00,0:27:28.00,Default,,0000,0000,0000,,that
Dialogue: 0,0:27:28.00,0:27:30.00,Default,,0000,0000,0000,,verify that the recursive case
Dialogue: 0,0:27:30.00,0:27:32.00,Default,,0000,0000,0000,,when exercised does the right thing,
Dialogue: 0,0:27:32.00,0:27:34.00,Default,,0000,0000,0000,,then the pair together - All your code is going through
Dialogue: 0,0:27:34.00,0:27:38.00,Default,,0000,0000,0000,,these same lines. The outer case going down to the recursive case, down
Dialogue: 0,0:27:38.00,0:27:39.00,Default,,0000,0000,0000,,to that base case, and that's
Dialogue: 0,0:27:39.00,0:27:43.00,Default,,0000,0000,0000,,one of the beauty of writing it recursively is that in some sense
Dialogue: 0,0:27:43.00,0:27:46.00,Default,,0000,0000,0000,,once this piece of code works for some simple cases, the idea that setting it to
Dialogue: 0,0:27:46.00,0:27:48.00,Default,,0000,0000,0000,,larger cases
Dialogue: 0,0:27:48.00,0:27:51.00,Default,,0000,0000,0000,,is almost - I don't wanna
Dialogue: 0,0:27:51.00,0:27:54.00,Default,,0000,0000,0000,,say guaranteed. That maybe makes it sound too easy, but in fact, if it
Dialogue: 0,0:27:54.00,0:27:55.00,Default,,0000,0000,0000,,works for
Dialogue: 0,0:27:55.00,0:27:58.00,Default,,0000,0000,0000,,cases of N and then N plus one, then it'll work for 100, and 101, and
Dialogue: 0,0:27:58.00,0:28:02.00,Default,,0000,0000,0000,,6,000, and 6,001, and all the way through all the numbers by
Dialogue: 0,0:28:02.00,0:28:06.00,Default,,0000,0000,0000,,induction. Question?
Dialogue: 0,0:28:06.00,0:28:10.00,Default,,0000,0000,0000,,You have to remove all the [inaudible], all the spaces? Yeah. So definitely like the was it a car to match I should definitely
Dialogue: 0,0:28:10.00,0:28:13.00,Default,,0000,0000,0000,,be taking my spaces out of there to make it right. You
Dialogue: 0,0:28:13.00,0:28:21.00,Default,,0000,0000,0000,,are totally correct on that.
Dialogue: 0,0:28:21.00,0:28:22.00,Default,,0000,0000,0000,,So let me show you
Dialogue: 0,0:28:22.00,0:28:25.00,Default,,0000,0000,0000,,one where recursion is definitely
Dialogue: 0,0:28:25.00,0:28:27.00,Default,,0000,0000,0000,,gonna buy us some real efficiency
Dialogue: 0,0:28:27.00,0:28:30.00,Default,,0000,0000,0000,,and some real clarity in solving a
Dialogue: 0,0:28:30.00,0:28:32.00,Default,,0000,0000,0000,,search problem. I've got a
Dialogue: 0,0:28:32.00,0:28:35.00,Default,,0000,0000,0000,,vector. Let's say it's a vector of strings. It's a vector
Dialogue: 0,0:28:35.00,0:28:37.00,Default,,0000,0000,0000,,of numbers. A vector of anything, it doesn't really matter.
Dialogue: 0,0:28:37.00,0:28:40.00,Default,,0000,0000,0000,,And I wanna see if I can find a particular entry in it. So unlike the
Dialogue: 0,0:28:40.00,0:28:44.00,Default,,0000,0000,0000,,set which can do a fast contains for you, in vector
Dialogue: 0,0:28:44.00,0:28:46.00,Default,,0000,0000,0000,,if I haven't done anything special with it,
Dialogue: 0,0:28:46.00,0:28:49.00,Default,,0000,0000,0000,,then there's no guarantee about where to find something. So if I wanna say
Dialogue: 0,0:28:49.00,0:28:51.00,Default,,0000,0000,0000,,
Dialogue: 0,0:28:51.00,0:28:54.00,Default,,0000,0000,0000,,did somebody score 75 on the exam, then I'm gonna have
Dialogue: 0,0:28:54.00,0:28:56.00,Default,,0000,0000,0000,,to just walk through the vector starting at Slot
Dialogue: 0,0:28:56.00,0:28:59.00,Default,,0000,0000,0000,,0, walk my way to the end, and
Dialogue: 0,0:28:59.00,0:29:02.00,Default,,0000,0000,0000,,compare to see if I find a 75. If I get to the end and I haven't found one, then
Dialogue: 0,0:29:02.00,0:29:04.00,Default,,0000,0000,0000,,I can say no.
Dialogue: 0,0:29:04.00,0:29:05.00,Default,,0000,0000,0000,,So that's what's called linear search. Linear
Dialogue: 0,0:29:05.00,0:29:10.00,Default,,0000,0000,0000,,kind of implies this left to right sequential processing.
Dialogue: 0,0:29:10.00,0:29:11.00,Default,,0000,0000,0000,,And linear search
Dialogue: 0,0:29:11.00,0:29:15.00,Default,,0000,0000,0000,,has the property that as the size of the input grows, the amount of time
Dialogue: 0,0:29:15.00,0:29:18.00,Default,,0000,0000,0000,,taken to search it grows in proportion.
Dialogue: 0,0:29:18.00,0:29:20.00,Default,,0000,0000,0000,,So if you have a 1000 number array,
Dialogue: 0,0:29:20.00,0:29:23.00,Default,,0000,0000,0000,,and you doubled its size, you would expect that doing a linear search on it should take
Dialogue: 0,0:29:23.00,0:29:30.00,Default,,0000,0000,0000,,twice as long for an array that's twice as large.
Dialogue: 0,0:29:30.00,0:29:34.00,Default,,0000,0000,0000,,The strategy we're gonna look at today is binary search
Dialogue: 0,0:29:34.00,0:29:37.00,Default,,0000,0000,0000,,which is gonna try to avoid this looking in every one of those boxes to
Dialogue: 0,0:29:37.00,0:29:38.00,Default,,0000,0000,0000,,find something.
Dialogue: 0,0:29:38.00,0:29:42.00,Default,,0000,0000,0000,,It's gonna take a divide and conquer strategy, and it's gonna require a sorted
Dialogue: 0,0:29:42.00,0:29:42.00,Default,,0000,0000,0000,,vector.
Dialogue: 0,0:29:42.00,0:29:45.00,Default,,0000,0000,0000,,So in order to do an efficient lookup,
Dialogue: 0,0:29:45.00,0:29:48.00,Default,,0000,0000,0000,,it helps if we've done some pre-rearrangement
Dialogue: 0,0:29:48.00,0:29:49.00,Default,,0000,0000,0000,,
Dialogue: 0,0:29:49.00,0:29:51.00,Default,,0000,0000,0000,,of the data. In this case, putting it into sorted order
Dialogue: 0,0:29:51.00,0:29:55.00,Default,,0000,0000,0000,,is gonna make it much easier for us to be able to find something in it because
Dialogue: 0,0:29:55.00,0:29:55.00,Default,,0000,0000,0000,,we have
Dialogue: 0,0:29:55.00,0:29:58.00,Default,,0000,0000,0000,,better information about where to look,
Dialogue: 0,0:29:58.00,0:29:59.00,Default,,0000,0000,0000,,so much faster.
Dialogue: 0,0:29:59.00,0:30:03.00,Default,,0000,0000,0000,,So we'll see that surely there was some cost to that,
Dialogue: 0,0:30:03.00,0:30:05.00,Default,,0000,0000,0000,,but typically binary search is gonna be used when you have an array where you
Dialogue: 0,0:30:05.00,0:30:07.00,Default,,0000,0000,0000,,don't do a lot of changes to it so
Dialogue: 0,0:30:07.00,0:30:11.00,Default,,0000,0000,0000,,that putting it in a sorted order can be done once, and then from that point forward you can
Dialogue: 0,0:30:11.00,0:30:15.00,Default,,0000,0000,0000,,search it many times, getting the benefit of the work you did to put it in
Dialogue: 0,0:30:15.00,0:30:16.00,Default,,0000,0000,0000,,sorted order.
Dialogue: 0,0:30:16.00,0:30:19.00,Default,,0000,0000,0000,,If you plan to sort it just to search it, then in some sense all the time you spent
Dialogue: 0,0:30:19.00,0:30:20.00,Default,,0000,0000,0000,,sorting it
Dialogue: 0,0:30:20.00,0:30:25.00,Default,,0000,0000,0000,,would kind of count against you and unlikely to come out ahead.
Dialogue: 0,0:30:25.00,0:30:28.00,Default,,0000,0000,0000,,So the insight we're gonna use is
Dialogue: 0,0:30:28.00,0:30:32.00,Default,,0000,0000,0000,,that if we have this in sorted order, and
Dialogue: 0,0:30:32.00,0:30:34.00,Default,,0000,0000,0000,,we're trying to search the whole thing - we're looking for let's say the No. 75
Dialogue: 0,0:30:34.00,0:30:36.00,Default,,0000,0000,0000,,-
Dialogue: 0,0:30:36.00,0:30:38.00,Default,,0000,0000,0000,,is that if we just look at the middlemost element,
Dialogue: 0,0:30:38.00,0:30:40.00,Default,,0000,0000,0000,,so we have this idea that we're looking at the whole vector right now from the
Dialogue: 0,0:30:40.00,0:30:42.00,Default,,0000,0000,0000,,start to the end,
Dialogue: 0,0:30:42.00,0:30:45.00,Default,,0000,0000,0000,,and I look at the middle element, and I say it's a 54. I can say
Dialogue: 0,0:30:45.00,0:30:49.00,Default,,0000,0000,0000,,if 75 is in this vector because it's in sorted order,
Dialogue: 0,0:30:49.00,0:30:51.00,Default,,0000,0000,0000,,it can't be
Dialogue: 0,0:30:51.00,0:30:52.00,Default,,0000,0000,0000,,anywhere over here.
Dialogue: 0,0:30:52.00,0:30:55.00,Default,,0000,0000,0000,,If 54's right there, everything to the left of 54
Dialogue: 0,0:30:55.00,0:30:57.00,Default,,0000,0000,0000,,must be less than that,
Dialogue: 0,0:30:57.00,0:30:59.00,Default,,0000,0000,0000,,and 75 wouldn't be over there.
Dialogue: 0,0:30:59.00,0:31:00.00,Default,,0000,0000,0000,,So that means I can
Dialogue: 0,0:31:00.00,0:31:03.00,Default,,0000,0000,0000,,just discard that half of the
Dialogue: 0,0:31:03.00,0:31:06.00,Default,,0000,0000,0000,,vector from further consideration.
Dialogue: 0,0:31:06.00,0:31:07.00,Default,,0000,0000,0000,,So now I have this half
Dialogue: 0,0:31:07.00,0:31:10.00,Default,,0000,0000,0000,,to continue looking at which is the things that
Dialogue: 0,0:31:10.00,0:31:13.00,Default,,0000,0000,0000,,are the right of 54 all the way to the end.
Dialogue: 0,0:31:13.00,0:31:17.00,Default,,0000,0000,0000,,I use the same strategy again. I say if I'm searching a vector - so
Dialogue: 0,0:31:17.00,0:31:19.00,Default,,0000,0000,0000,,last time I was searching a vector that had 25 elements. Now I've got one that's got
Dialogue: 0,0:31:19.00,0:31:21.00,Default,,0000,0000,0000,,just 12.
Dialogue: 0,0:31:21.00,0:31:24.00,Default,,0000,0000,0000,,Again, I use the same strategy. Look at the one in the middle.
Dialogue: 0,0:31:24.00,0:31:26.00,Default,,0000,0000,0000,,I say oh, it's an 80,
Dialogue: 0,0:31:26.00,0:31:29.00,Default,,0000,0000,0000,,and then I say well the number I'm looking for is 75.
Dialogue: 0,0:31:29.00,0:31:30.00,Default,,0000,0000,0000,,It can't be
Dialogue: 0,0:31:30.00,0:31:35.00,Default,,0000,0000,0000,,to the right of the 80. It must be to the left of it.
Dialogue: 0,0:31:35.00,0:31:36.00,Default,,0000,0000,0000,,And then that lets me
Dialogue: 0,0:31:36.00,0:31:40.00,Default,,0000,0000,0000,,get rid of another quarter of the vector. If I keep doing this, I get rid of
Dialogue: 0,0:31:40.00,0:31:43.00,Default,,0000,0000,0000,,half, and then a quarter, and then an eighth, and
Dialogue: 0,0:31:43.00,0:31:47.00,Default,,0000,0000,0000,,then a 16th. Very quickly, I will narrow in on the position where if 75 is in
Dialogue: 0,0:31:47.00,0:31:53.00,Default,,0000,0000,0000,,this vector, it has to be. Or I'll be able to conclude it wasn't there at all. Then I kind of
Dialogue: 0,0:31:53.00,0:31:55.00,Default,,0000,0000,0000,,work on my in, and
Dialogue: 0,0:31:55.00,0:31:59.00,Default,,0000,0000,0000,,I found a 74 and a 76 over there, then I'm done.
Dialogue: 0,0:31:59.00,0:32:02.00,Default,,0000,0000,0000,,That base case comes when I have
Dialogue: 0,0:32:02.00,0:32:04.00,Default,,0000,0000,0000,,such a small little vector there
Dialogue: 0,0:32:04.00,0:32:05.00,Default,,0000,0000,0000,,where
Dialogue: 0,0:32:05.00,0:32:09.00,Default,,0000,0000,0000,,my bounds have crossed in such a way that I can say I never found what I
Dialogue: 0,0:32:09.00,0:32:16.00,Default,,0000,0000,0000,,was looking for.
Dialogue: 0,0:32:16.00,0:32:19.00,Default,,0000,0000,0000,,So let's walk through
Dialogue: 0,0:32:19.00,0:32:21.00,Default,,0000,0000,0000,,this
Dialogue: 0,0:32:21.00,0:32:22.00,Default,,0000,0000,0000,,
Dialogue: 0,0:32:22.00,0:32:25.00,Default,,0000,0000,0000,,bit of code that kind of puts into C++ the thing I just described here.
Dialogue: 0,0:32:25.00,0:32:29.00,Default,,0000,0000,0000,,I've got a vector. In this case, I'm using a vector that's containing strings.
Dialogue: 0,0:32:29.00,0:32:32.00,Default,,0000,0000,0000,,It could be ints. It could be anything. It doesn't really matter.
Dialogue: 0,0:32:32.00,0:32:36.00,Default,,0000,0000,0000,,I've got a start and a stop, which I identify the sub-portion of the vector
Dialogue: 0,0:32:36.00,0:32:40.00,Default,,0000,0000,0000,,that we're interested in. So the start is the first index to consider. The stop is the
Dialogue: 0,0:32:40.00,0:32:41.00,Default,,0000,0000,0000,,last index to consider.
Dialogue: 0,0:32:41.00,0:32:46.00,Default,,0000,0000,0000,,So the very first call to this will have start set to zero and stop set to the vector's
Dialogue: 0,0:32:46.00,0:32:48.00,Default,,0000,0000,0000,,size minus one. I
Dialogue: 0,0:32:48.00,0:32:51.00,Default,,0000,0000,0000,,compute the midpoint index
Dialogue: 0,0:32:51.00,0:32:54.00,Default,,0000,0000,0000,,which is just the sum of the start and stop divided by two,
Dialogue: 0,0:32:54.00,0:32:56.00,Default,,0000,0000,0000,,and then I compare
Dialogue: 0,0:32:56.00,0:32:58.00,Default,,0000,0000,0000,,the key that I'm looking for to
Dialogue: 0,0:32:58.00,0:33:02.00,Default,,0000,0000,0000,,the value at that index. I'm looking right in the middle. If it happens to match,
Dialogue: 0,0:33:02.00,0:33:06.00,Default,,0000,0000,0000,,then I return that. The goal of binary search in this case is to return the index of a
Dialogue: 0,0:33:06.00,0:33:08.00,Default,,0000,0000,0000,,matching element within the vector,
Dialogue: 0,0:33:08.00,0:33:11.00,Default,,0000,0000,0000,,or to return this not found negative one constant
Dialogue: 0,0:33:11.00,0:33:14.00,Default,,0000,0000,0000,,if it was unable to find any match anywhere.
Dialogue: 0,0:33:14.00,0:33:16.00,Default,,0000,0000,0000,,So when we do find it
Dialogue: 0,0:33:16.00,0:33:20.00,Default,,0000,0000,0000,,at whatever the level the recursion is, we can just immediately return that. We're done.
Dialogue: 0,0:33:20.00,0:33:21.00,Default,,0000,0000,0000,,We found it. It's good.
Dialogue: 0,0:33:21.00,0:33:24.00,Default,,0000,0000,0000,,Otherwise, we're gonna make this recursive call
Dialogue: 0,0:33:24.00,0:33:28.00,Default,,0000,0000,0000,,that looks at either the left half or the right half based on if key is
Dialogue: 0,0:33:28.00,0:33:28.00,Default,,0000,0000,0000,,less than
Dialogue: 0,0:33:28.00,0:33:30.00,Default,,0000,0000,0000,,the value we found at the midpoint,
Dialogue: 0,0:33:30.00,0:33:32.00,Default,,0000,0000,0000,,then the place we're searching is -
Dialogue: 0,0:33:32.00,0:33:34.00,Default,,0000,0000,0000,,still has the same start position,
Dialogue: 0,0:33:34.00,0:33:36.00,Default,,0000,0000,0000,,but is now capped
Dialogue: 0,0:33:36.00,0:33:38.00,Default,,0000,0000,0000,,by the
Dialogue: 0,0:33:38.00,0:33:40.00,Default,,0000,0000,0000,,element exactly to the left of the midpoint,
Dialogue: 0,0:33:40.00,0:33:43.00,Default,,0000,0000,0000,,and then the right one,
Dialogue: 0,0:33:43.00,0:33:45.00,Default,,0000,0000,0000,,the inversion of that,
Dialogue: 0,0:33:45.00,0:33:47.00,Default,,0000,0000,0000,,one to the right of the midpoint
Dialogue: 0,0:33:47.00,0:33:49.00,Default,,0000,0000,0000,,and the stop unchanged.
Dialogue: 0,0:33:49.00,0:33:53.00,Default,,0000,0000,0000,,So taking off half of the elements under consideration at each stage,
Dialogue: 0,0:33:53.00,0:33:54.00,Default,,0000,0000,0000,,eventually
Dialogue: 0,0:33:54.00,0:33:58.00,Default,,0000,0000,0000,,I will get down to the simplest possible case. And the simplest possible case isn't that I have a one-element
Dialogue: 0,0:33:58.00,0:34:02.00,Default,,0000,0000,0000,,vector and I found it or not. The really simple case is actually that I have zero
Dialogue: 0,0:34:02.00,0:34:03.00,Default,,0000,0000,0000,,elements in my vector
Dialogue: 0,0:34:03.00,0:34:04.00,Default,,0000,0000,0000,,that I just kept
Dialogue: 0,0:34:04.00,0:34:06.00,Default,,0000,0000,0000,,moving in the
Dialogue: 0,0:34:06.00,0:34:09.00,Default,,0000,0000,0000,,upper and lower bound point until they crossed,
Dialogue: 0,0:34:09.00,0:34:12.00,Default,,0000,0000,0000,,which meant that I ran out of elements to check.
Dialogue: 0,0:34:12.00,0:34:15.00,Default,,0000,0000,0000,,And that happens when the start index is greater than the stop index. So the start
Dialogue: 0,0:34:15.00,0:34:19.00,Default,,0000,0000,0000,,and the stop if they're equal to each other mean that you have a one element vector left
Dialogue: 0,0:34:19.00,0:34:20.00,Default,,0000,0000,0000,,to search,
Dialogue: 0,0:34:20.00,0:34:22.00,Default,,0000,0000,0000,,but if you - For
Dialogue: 0,0:34:22.00,0:34:24.00,Default,,0000,0000,0000,,example, if you got to that case where you have that one element vector left to search, you'll look
Dialogue: 0,0:34:24.00,0:34:28.00,Default,,0000,0000,0000,,at that one, and if it matches, you'll be done. Otherwise, you'll end up
Dialogue: 0,0:34:28.00,0:34:30.00,Default,,0000,0000,0000,,either decrementing the stop
Dialogue: 0,0:34:30.00,0:34:33.00,Default,,0000,0000,0000,,to move past the start, or incrementing the start to move past the
Dialogue: 0,0:34:33.00,0:34:34.00,Default,,0000,0000,0000,,stop.
Dialogue: 0,0:34:34.00,0:34:36.00,Default,,0000,0000,0000,,And then that next iteration will hit this base case that said
Dialogue: 0,0:34:36.00,0:34:40.00,Default,,0000,0000,0000,,I looked at the element in a one-element vector. It didn't work
Dialogue: 0,0:34:40.00,0:34:40.00,Default,,0000,0000,0000,,out.
Dialogue: 0,0:34:40.00,0:34:43.00,Default,,0000,0000,0000,,I can tell you for sure it's not found.
Dialogue: 0,0:34:43.00,0:34:45.00,Default,,0000,0000,0000,,If it had been here, I would've seen it.
Dialogue: 0,0:34:45.00,0:34:47.00,Default,,0000,0000,0000,,And this is looking at just one element
Dialogue: 0,0:34:47.00,0:34:49.00,Default,,0000,0000,0000,,each
Dialogue: 0,0:34:49.00,0:34:50.00,Default,,0000,0000,0000,,recursive call,
Dialogue: 0,0:34:50.00,0:34:55.00,Default,,0000,0000,0000,,and the recursive calls in this case stack up to a depth
Dialogue: 0,0:34:55.00,0:34:57.00,Default,,0000,0000,0000,,based on the logarithm of the size
Dialogue: 0,0:34:57.00,0:34:59.00,Default,,0000,0000,0000,,to the power of two,
Dialogue: 0,0:34:59.00,0:35:02.00,Default,,0000,0000,0000,,so that if you have 1000 elements,
Dialogue: 0,0:35:02.00,0:35:06.00,Default,,0000,0000,0000,,you look at one, and now you have a 500-element collection to look
Dialogue: 0,0:35:06.00,0:35:09.00,Default,,0000,0000,0000,,at again. You look at one, you have
Dialogue: 0,0:35:09.00,0:35:12.00,Default,,0000,0000,0000,,a 250 element, 125, 60, 30,
Dialogue: 0,0:35:12.00,0:35:12.00,Default,,0000,0000,0000,,15.
Dialogue: 0,0:35:12.00,0:35:14.00,Default,,0000,0000,0000,,So at each stage
Dialogue: 0,0:35:14.00,0:35:15.00,Default,,0000,0000,0000,,half of them
Dialogue: 0,0:35:15.00,0:35:19.00,Default,,0000,0000,0000,,remain for the further call, and the number of times you can do that
Dialogue: 0,0:35:19.00,0:35:22.00,Default,,0000,0000,0000,,for 1000 is the number of times you can divide 1000 by two, which is
Dialogue: 0,0:35:22.00,0:35:24.00,Default,,0000,0000,0000,,the log based two of that,
Dialogue: 0,0:35:24.00,0:35:26.00,Default,,0000,0000,0000,,which is roughly ten.
Dialogue: 0,0:35:26.00,0:35:29.00,Default,,0000,0000,0000,,So if you were looking at 1000 number array, if it's in sorted order,
Dialogue: 0,0:35:29.00,0:35:32.00,Default,,0000,0000,0000,,it takes you ten comparisons
Dialogue: 0,0:35:32.00,0:35:34.00,Default,,0000,0000,0000,,to conclusively determine
Dialogue: 0,0:35:34.00,0:35:38.00,Default,,0000,0000,0000,,where an element is if it's in there, or that it doesn't exist in the array at
Dialogue: 0,0:35:38.00,0:35:39.00,Default,,0000,0000,0000,,all.
Dialogue: 0,0:35:39.00,0:35:41.00,Default,,0000,0000,0000,,If you take that 1000 element array,
Dialogue: 0,0:35:41.00,0:35:43.00,Default,,0000,0000,0000,,and you make it twice as big,
Dialogue: 0,0:35:43.00,0:35:46.00,Default,,0000,0000,0000,,so now I have a 2000
Dialogue: 0,0:35:46.00,0:35:50.00,Default,,0000,0000,0000,,number array, how much longer does it take? One more step.
Dialogue: 0,0:35:50.00,0:35:51.00,Default,,0000,0000,0000,,One more step.
Dialogue: 0,0:35:51.00,0:35:55.00,Default,,0000,0000,0000,,Just one, right? You look at one, and you have a 1000 number array, so however long it took
Dialogue: 0,0:35:55.00,0:35:56.00,Default,,0000,0000,0000,,you to do that 1000 number array,
Dialogue: 0,0:35:56.00,0:36:00.00,Default,,0000,0000,0000,,it takes one additional comparison, kinda one stack frame on top of that
Dialogue: 0,0:36:00.00,0:36:01.00,Default,,0000,0000,0000,,to get its way down.
Dialogue: 0,0:36:01.00,0:36:04.00,Default,,0000,0000,0000,,So this means actually this is super efficient.
Dialogue: 0,0:36:04.00,0:36:06.00,Default,,0000,0000,0000,,That you can search so for example
Dialogue: 0,0:36:06.00,0:36:09.00,Default,,0000,0000,0000,,a million is roughly two the 20th power.
Dialogue: 0,0:36:09.00,0:36:12.00,Default,,0000,0000,0000,,So you have a million entry
Dialogue: 0,0:36:12.00,0:36:16.00,Default,,0000,0000,0000,,collection to search, it will take you 20 comparisons to say for sure
Dialogue: 0,0:36:16.00,0:36:17.00,Default,,0000,0000,0000,,it's here or not,
Dialogue: 0,0:36:17.00,0:36:18.00,Default,,0000,0000,0000,,and here's where I found it,
Dialogue: 0,0:36:18.00,0:36:20.00,Default,,0000,0000,0000,,just 20.
Dialogue: 0,0:36:20.00,0:36:22.00,Default,,0000,0000,0000,,You go up to two million, it takes
Dialogue: 0,0:36:22.00,0:36:24.00,Default,,0000,0000,0000,,21. The
Dialogue: 0,0:36:24.00,0:36:27.00,Default,,0000,0000,0000,,very slow growing function, that logarithm function, so that tells you
Dialogue: 0,0:36:27.00,0:36:28.00,Default,,0000,0000,0000,,
Dialogue: 0,0:36:28.00,0:36:31.00,Default,,0000,0000,0000,,that this is gonna be a very efficient way of searching a sorted array. A
Dialogue: 0,0:36:31.00,0:36:34.00,Default,,0000,0000,0000,,category
Dialogue: 0,0:36:34.00,0:36:37.00,Default,,0000,0000,0000,,thing called the divide and conquer that
Dialogue: 0,0:36:37.00,0:36:39.00,Default,,0000,0000,0000,,take a problem,
Dialogue: 0,0:36:39.00,0:36:42.00,Default,,0000,0000,0000,,divide it typically in half, but sometimes in thirds or some other
Dialogue: 0,0:36:42.00,0:36:45.00,Default,,0000,0000,0000,,way, and then kind of - in this case
Dialogue: 0,0:36:45.00,0:36:49.00,Default,,0000,0000,0000,,it's particularly handy that we can throw away some part of the problem, so we
Dialogue: 0,0:36:49.00,0:36:56.00,Default,,0000,0000,0000,,divide and focus on just one part to solve the problem.
Dialogue: 0,0:36:56.00,0:36:58.00,Default,,0000,0000,0000,,All right. So this is the first one
Dialogue: 0,0:36:58.00,0:37:02.00,Default,,0000,0000,0000,,that's gonna start to
Dialogue: 0,0:37:02.00,0:37:04.00,Default,,0000,0000,0000,,really inspire you for how recursion can help you solve problems
Dialogue: 0,0:37:04.00,0:37:05.00,Default,,0000,0000,0000,,that you might
Dialogue: 0,0:37:05.00,0:37:08.00,Default,,0000,0000,0000,,have no idea how to approach any other way
Dialogue: 0,0:37:08.00,0:37:10.00,Default,,0000,0000,0000,,than using a recursive formulation.
Dialogue: 0,0:37:10.00,0:37:13.00,Default,,0000,0000,0000,,So this is an exercise that comes out of the reader in Chapter 4,
Dialogue: 0,0:37:13.00,0:37:16.00,Default,,0000,0000,0000,,and the
Dialogue: 0,0:37:16.00,0:37:18.00,Default,,0000,0000,0000,,context of it is you have N things,
Dialogue: 0,0:37:18.00,0:37:22.00,Default,,0000,0000,0000,,so maybe it's N people in a dorm, 60 people in a dorm,
Dialogue: 0,0:37:22.00,0:37:26.00,Default,,0000,0000,0000,,and you would like to choose K of them. Let's K a real number, four
Dialogue: 0,0:37:26.00,0:37:29.00,Default,,0000,0000,0000,,- four people to go together to Flicks.
Dialogue: 0,0:37:29.00,0:37:32.00,Default,,0000,0000,0000,,So of your 60 dorm mates, how many different ways could you
Dialogue: 0,0:37:32.00,0:37:33.00,Default,,0000,0000,0000,,pick a subset
Dialogue: 0,0:37:33.00,0:37:35.00,Default,,0000,0000,0000,,of size four
Dialogue: 0,0:37:35.00,0:37:38.00,Default,,0000,0000,0000,,that doesn't repeat any of the others? So you can pick the
Dialogue: 0,0:37:38.00,0:37:41.00,Default,,0000,0000,0000,,two people from the first floor, one person from the middle floor, one person
Dialogue: 0,0:37:41.00,0:37:44.00,Default,,0000,0000,0000,,from the top floor, but then you can kind of shuffle it up. What if you took all the people from the
Dialogue: 0,0:37:44.00,0:37:45.00,Default,,0000,0000,0000,,first floor, or
Dialogue: 0,0:37:45.00,0:37:48.00,Default,,0000,0000,0000,,these people from that room, and whatnot? You can imagine there's a lot of kind of
Dialogue: 0,0:37:48.00,0:37:50.00,Default,,0000,0000,0000,,machinations
Dialogue: 0,0:37:50.00,0:37:53.00,Default,,0000,0000,0000,,that could be present here,
Dialogue: 0,0:37:53.00,0:37:57.00,Default,,0000,0000,0000,,and counting them, it's not quite obvious
Dialogue: 0,0:37:57.00,0:37:59.00,Default,,0000,0000,0000,,unless you kinda go back to start working on your real math
Dialogue: 0,0:37:59.00,0:38:01.00,Default,,0000,0000,0000,,skills
Dialogue: 0,0:38:01.00,0:38:05.00,Default,,0000,0000,0000,,how it is that you can write a formula for this.
Dialogue: 0,0:38:05.00,0:38:07.00,Default,,0000,0000,0000,,So what I'm gonna give you is
Dialogue: 0,0:38:07.00,0:38:11.00,Default,,0000,0000,0000,,a recursive way of thinking about this problem.
Dialogue: 0,0:38:11.00,0:38:12.00,Default,,0000,0000,0000,,So I drew
Dialogue: 0,0:38:12.00,0:38:15.00,Default,,0000,0000,0000,,a set of the things we're looking at?
Dialogue: 0,0:38:15.00,0:38:18.00,Default,,0000,0000,0000,,So there are N things that we're trying to choose K out
Dialogue: 0,0:38:18.00,0:38:21.00,Default,,0000,0000,0000,,of. So right now, I've got
Dialogue: 0,0:38:21.00,0:38:23.00,Default,,0000,0000,0000,,12 or so
Dialogue: 0,0:38:23.00,0:38:24.00,Default,,0000,0000,0000,,people, or
Dialogue: 0,0:38:24.00,0:38:26.00,Default,,0000,0000,0000,,items, whatever it is.
Dialogue: 0,0:38:26.00,0:38:29.00,Default,,0000,0000,0000,,What I'm gonna do is I'm gonna imagine just designating one
Dialogue: 0,0:38:29.00,0:38:30.00,Default,,0000,0000,0000,,totally at random.
Dialogue: 0,0:38:30.00,0:38:33.00,Default,,0000,0000,0000,,So pick Bob.
Dialogue: 0,0:38:33.00,0:38:35.00,Default,,0000,0000,0000,,Bob is one of the people in the dorm. I'm gonna kind of separate him from
Dialogue: 0,0:38:35.00,0:38:39.00,Default,,0000,0000,0000,,everybody else mentally in my mind, and draw this line, and kinda mark him with a red flag
Dialogue: 0,0:38:39.00,0:38:41.00,Default,,0000,0000,0000,,that says that's Bob.
Dialogue: 0,0:38:41.00,0:38:45.00,Default,,0000,0000,0000,,So Bob might go to Flicks or might not go to Flicks. Some of the subsets for
Dialogue: 0,0:38:45.00,0:38:52.00,Default,,0000,0000,0000,,going to Flicks will include Bob, and some will not.
Dialogue: 0,0:38:52.00,0:38:53.00,Default,,0000,0000,0000,,Okay.
Dialogue: 0,0:38:53.00,0:38:57.00,Default,,0000,0000,0000,,So what I'd like to think about is how many different subsets can I make that will
Dialogue: 0,0:38:57.00,0:38:58.00,Default,,0000,0000,0000,,include Bob,
Dialogue: 0,0:38:58.00,0:39:01.00,Default,,0000,0000,0000,,and how many different subsets can I make that don't include Bob. And
Dialogue: 0,0:39:01.00,0:39:05.00,Default,,0000,0000,0000,,if I added those together, then that should be the total number of subsets I can make
Dialogue: 0,0:39:05.00,0:39:08.00,Default,,0000,0000,0000,,from this collection.
Dialogue: 0,0:39:08.00,0:39:11.00,Default,,0000,0000,0000,,Okay, so the subsets that include Bob -
Dialogue: 0,0:39:11.00,0:39:15.00,Default,,0000,0000,0000,,so once I've committed to Bob being in the set, and let's say I'm trying to pick four
Dialogue: 0,0:39:15.00,0:39:16.00,Default,,0000,0000,0000,,members out of here,
Dialogue: 0,0:39:16.00,0:39:18.00,Default,,0000,0000,0000,,then I have Bob
Dialogue: 0,0:39:18.00,0:39:22.00,Default,,0000,0000,0000,,and I have to figure out how many ways can I pick three people to accompany Bob to
Dialogue: 0,0:39:22.00,0:39:24.00,Default,,0000,0000,0000,,the Flicks.
Dialogue: 0,0:39:24.00,0:39:28.00,Default,,0000,0000,0000,,So I'm picking from a slightly smaller population. The population went down by one,
Dialogue: 0,0:39:28.00,0:39:31.00,Default,,0000,0000,0000,,and the number I'm seeking went down by one,
Dialogue: 0,0:39:31.00,0:39:34.00,Default,,0000,0000,0000,,and that tells me all the ways I can pick three people to go with Bob.
Dialogue: 0,0:39:34.00,0:39:38.00,Default,,0000,0000,0000,,The ones that don't include Bob, and Bob's just out of the running,
Dialogue: 0,0:39:38.00,0:39:42.00,Default,,0000,0000,0000,,I look at the remaining population which is still one smaller, everybody but Bob, and I
Dialogue: 0,0:39:42.00,0:39:47.00,Default,,0000,0000,0000,,look for the ways I can still pick four people from there.
Dialogue: 0,0:39:47.00,0:39:51.00,Default,,0000,0000,0000,,So what I have here is trying to compute C of NK
Dialogue: 0,0:39:51.00,0:39:56.00,Default,,0000,0000,0000,,is trying to compute C of N minus one K minus one and add it to C of N minus one K.
Dialogue: 0,0:39:56.00,0:39:58.00,Default,,0000,0000,0000,,So this is
Dialogue: 0,0:39:58.00,0:39:59.00,Default,,0000,0000,0000,,picking
Dialogue: 0,0:39:59.00,0:40:02.00,Default,,0000,0000,0000,,friends to accompany Bob. This is picking people without Bob.
Dialogue: 0,0:40:02.00,0:40:03.00,Default,,0000,0000,0000,,Add those together,
Dialogue: 0,0:40:03.00,0:40:08.00,Default,,0000,0000,0000,,and I will have the total number of ways I can pick K things out of N.
Dialogue: 0,0:40:08.00,0:40:13.00,Default,,0000,0000,0000,,So we're very much relying on this recursive idea of if I had the answer
Dialogue: 0,0:40:13.00,0:40:16.00,Default,,0000,0000,0000,,- I don't feel smart enough to know the answer directly,
Dialogue: 0,0:40:16.00,0:40:20.00,Default,,0000,0000,0000,,but if I could defer it to someone who was actually willing to do more
Dialogue: 0,0:40:20.00,0:40:23.00,Default,,0000,0000,0000,,scrutiny into this thing, if you could tell me how many groups of three you can
Dialogue: 0,0:40:23.00,0:40:28.00,Default,,0000,0000,0000,,join with Bob, and how many groups of four you can pick without Bob, I can tell you
Dialogue: 0,0:40:28.00,0:40:30.00,Default,,0000,0000,0000,,what the total answer is.
Dialogue: 0,0:40:30.00,0:40:33.00,Default,,0000,0000,0000,,The simplest possible base case
Dialogue: 0,0:40:33.00,0:40:38.00,Default,,0000,0000,0000,,we're gonna work our way down to are when there are just no choices remaining at all.
Dialogue: 0,0:40:38.00,0:40:40.00,Default,,0000,0000,0000,,So if you look back at my
Dialogue: 0,0:40:40.00,0:40:43.00,Default,,0000,0000,0000,,things that are here, in
Dialogue: 0,0:40:43.00,0:40:46.00,Default,,0000,0000,0000,,both cases the population is getting smaller,
Dialogue: 0,0:40:46.00,0:40:50.00,Default,,0000,0000,0000,,and in one of the recursive calls, the number of things I'm trying to
Dialogue: 0,0:40:50.00,0:40:52.00,Default,,0000,0000,0000,,pick is also getting smaller.
Dialogue: 0,0:40:52.00,0:40:55.00,Default,,0000,0000,0000,,So they're both making progress toward kind of shrinking those down to where
Dialogue: 0,0:40:55.00,0:40:56.00,Default,,0000,0000,0000,,there's kind of
Dialogue: 0,0:40:56.00,0:40:59.00,Default,,0000,0000,0000,,more and more constraints on what I have to choose.
Dialogue: 0,0:40:59.00,0:41:02.00,Default,,0000,0000,0000,,For example, on this one
Dialogue: 0,0:41:02.00,0:41:05.00,Default,,0000,0000,0000,,as I keep shrinking the population by one
Dialogue: 0,0:41:05.00,0:41:07.00,Default,,0000,0000,0000,,and trying to get the same number of people,
Dialogue: 0,0:41:07.00,0:41:10.00,Default,,0000,0000,0000,,eventually I'll be trying to pick three people out of three,
Dialogue: 0,0:41:10.00,0:41:14.00,Default,,0000,0000,0000,,where I'm trying to pick of K of K remaining. Well, there's only one way to do
Dialogue: 0,0:41:14.00,0:41:17.00,Default,,0000,0000,0000,,that which is to take everyone.
Dialogue: 0,0:41:17.00,0:41:18.00,Default,,0000,0000,0000,,On this one, I'll
Dialogue: 0,0:41:18.00,0:41:20.00,Default,,0000,0000,0000,,eventually keep picking people,
Dialogue: 0,0:41:20.00,0:41:23.00,Default,,0000,0000,0000,,so the K is always less than the N in this case. The
Dialogue: 0,0:41:23.00,0:41:26.00,Default,,0000,0000,0000,,K will eventually kinda bottom out, or I'll say I've
Dialogue: 0,0:41:26.00,0:41:30.00,Default,,0000,0000,0000,,already picked all the people. I've already picked four people. I need to pick zero more. And
Dialogue: 0,0:41:30.00,0:41:34.00,Default,,0000,0000,0000,,at that point, that's also very easy, right? Picking zero out of a population, there's
Dialogue: 0,0:41:34.00,0:41:38.00,Default,,0000,0000,0000,,only one way to do that.
Dialogue: 0,0:41:38.00,0:41:41.00,Default,,0000,0000,0000,,So what we end up with is
Dialogue: 0,0:41:41.00,0:41:45.00,Default,,0000,0000,0000,,a very simple base case of if K equals zero - so I'm not trying to choose anymore.
Dialogue: 0,0:41:45.00,0:41:49.00,Default,,0000,0000,0000,,I've already committed all the slots. Or if K is equal to N
Dialogue: 0,0:41:49.00,0:41:50.00,Default,,0000,0000,0000,,where I've
Dialogue: 0,0:41:50.00,0:41:52.00,Default,,0000,0000,0000,,discarded a whole bunch of people, and now I'm down to where I'm
Dialogue: 0,0:41:52.00,0:41:56.00,Default,,0000,0000,0000,,facing I've gotta get four, and I've got four left. Well, there's only one way to do those things,
Dialogue: 0,0:41:56.00,0:41:59.00,Default,,0000,0000,0000,,and that's to take everybody or to take nobody.
Dialogue: 0,0:41:59.00,0:42:00.00,Default,,0000,0000,0000,,And then otherwise,
Dialogue: 0,0:42:00.00,0:42:02.00,Default,,0000,0000,0000,,I make those two recursive calls
Dialogue: 0,0:42:02.00,0:42:05.00,Default,,0000,0000,0000,,with Bob, without Bob, add them together
Dialogue: 0,0:42:05.00,0:42:13.00,Default,,0000,0000,0000,,to get my whole result.
Dialogue: 0,0:42:13.00,0:42:14.00,Default,,0000,0000,0000,,That's wacky. I'm gonna
Dialogue: 0,0:42:14.00,0:42:18.00,Default,,0000,0000,0000,,read you something,
Dialogue: 0,0:42:18.00,0:42:22.00,Default,,0000,0000,0000,,and then we'll call it a day. I
Dialogue: 0,0:42:22.00,0:42:31.00,Default,,0000,0000,0000,,brought a book with me. I stole this from my children.