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