**Heads up!** To view this whole video, sign in with your Courses account or enroll in your free 7-day trial.
Sign In
Enroll

Preview

Start a free Courses trial

to watch this video

In the last video we wrote a version of binary search that uses a concept called recursion. Recursion might be a new concept for you so let's formalize how we use it.

[MUSIC]
0:00

In the last video,
0:03

we wrote a version of binary search
that uses a concept called Recursion.
0:05

Recursion might be a new concept for you.
0:10

So let's formalize how we use it.
0:13

A recursive function is
one that calls itself.
0:15

In our example the recursive binary search
function called itself inside the body
0:20

of the function.
0:25

When writing a recursive function you
always need a stopping condition.
0:26

And typically we start the body of
the recursive function with this stopping
0:31

condition.
0:36

It's common to call this
stopping condition the base case.
0:37

In our recursive binary search function,
we had two stopping conditions.
0:41

The first was what the function should
return if an empty list is passed in.
0:46

It seems weird to evaluate an empty list,
0:52

because you wouldn't expect to
run search on an empty list.
0:55

But if you look at how a function works,
0:59

recursive binary search
keeps calling itself.
1:02

And with each call to itself,
the size of the list is cut in half.
1:05

If we searched for a target,
that didn't exist in the list,
1:09

then the function would keep having
itself, until it got to an empty list.
1:13

Consider a three element list,
with numbers, 1, 2, 3,
1:17

where we're searching for a target of 4.
1:22

On the first path, the midpoint is 2, so
1:25

the function would call
itself with the least 3.
1:28

On the next pass the midpoint is 0 and
the target is still greater so
1:31

the function would call itself,
this time passing in an empty list
1:35

because an index of 0 + 1 in
a single element list doesn't exist.
1:40

When we have an empty list, this means
that after searching through the list,
1:45

the value wasn't found.
1:50

This is why we define an empty
list as a stopping condition or
1:51

a base case that returns false.
1:55

If it's not an empty list,
1:57

then we have an entirely different set
if instructions we want to execute.
1:59

First, we obtain the mid point of
the list, once we have the mid point,
2:03

we can introduce our next base case or
stopping condition.
2:07

If the value at the midpoint is the same
as the target the we'll return true.
2:11

With these two stopping conditions
we've covered all possible paths of
2:16

logic through the search algorithm.
2:21

You can either find the value or
you don't.
2:23

Once you have the base cases,
2:26

the rest of the implementation of the
recursive function is to call the function
2:28

on smallest sum lists until we
hit one of these base cases.
2:33

Going back to our visualization for
a second, [SOUND] we see that recursive
2:37

binary search calls itself a first time,
[SOUND] which then calls itself again.
2:41

For the initial list we started with,
2:46

the function only calls itself a few times
before a stopping condition is reached.
2:48

The number of times a recursive functions
calls itself is called Recursive Depth.
2:53

And the reason I bring all of this up
is because, if after you start learning
2:59

about algorithms, you decided you want
to go off and do your own research.
3:03

You may start to see a lot of
algorithms implemented using recursion.
3:07

The way we implemented binary
search the first time is called
3:12

an Iterative Solution.
3:16

Now, when you see the word iterative,
it generally means the solution
3:18

was implemented using a loop
structure of some kind.
3:22

A recursive solution on the other
hand is one that involves a set
3:25

of stopping conditions and
a function that calls itself.
3:29

Computer scientists and computer science
textbooks, particularly from back in
3:33

the day, favor and are written in
what are called Functional Languages.
3:38

In functional languages, we try to avoid
changing data that is given to a function.
3:42

In our first version of binary search,
we created first and last variables using
3:47

the list and then modified first and
last as we needed to arrive at a solution.
3:52

Functional languages
don't like to do this,
3:57

all this modification of variables and
prefer a solution using recursion.
4:00

And a language like Python, which is
what we're using, is the opposite,
4:04

and doesn't like recursion.
4:09

In fact,
Python has a maximum recursion depth,
4:11

after which our function
will halt execution.
4:15

Python prefers an iterative solution.
4:18

Now, I mention all of this for
two reasons.
4:21

If you decide that you want to learn how
to implement the algorithm in a language
4:23

of your choice that's not Python.
4:28

Then you might see a recursive solution
as the best implementation in that
4:30

particular language.
4:35

I'm an iOS developer, for example, and
I work with a language called Swift.
4:37

Swift is different than Python, it doesn't
care about recursion depth and does some
4:41

neat tricks where it doesn't even matter
how many times your function calls itself.
4:46

So if you want to see this is Swift code,
then you need to know how recursion works.
4:50

Well, and now, you have some idea.
4:55

And the second reason I bring it
up is actually way more important.
4:57

And to find out, on to the next video.
5:00

You need to sign up for Treehouse in order to download course files.

Sign up