Lecture 8 | Programming Abstractions (Stanford)

Lecture 8 by Julie Zelenski for the Programming Abstractions Course (CS106B) in the Stanford Computer Science Department.

Julie talks about solving problems recursively. She covers functional recursion with the simple example of writing an exponential function using recursion. From the simple program performing as an exponential function Julie continues to show a more efficient recursion code. The next example she covers is that of binary search and how recursion is used in this instance.

Complete Playlist for the Course:
http://www.youtube.com/view_play_list?p=FE6E58F856038C69

CS 106B Course Website:
http://cs106b.stanford.edu

Stanford Center for Professional Development:
http://scpd.stanford.edu/

Stanford University:
http://www.stanford.edu/

Stanford University Channel on YouTube:
http://www.youtube.com/stanforduniversity/

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.