Bummer! This is just a preview. You need to be signed in with a Basic account to view the entire video.
Start a free Basic 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.

0:00
[MUSIC]

0:03
In the last video,

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

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

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

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

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

0:25
of the function.

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

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

0:36
condition.

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

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

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

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

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

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

1:02
recursive binary search keeps calling itself.

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

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

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

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

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

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

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

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

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

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

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

1:50
the value wasn't found.

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

1:55
a base case that returns false.

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

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

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

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

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

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

2:21
logic through the search algorithm.

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

2:26
Once you have the base cases,

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

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

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

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

2:46
For the initial list we started with,

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

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

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

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

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

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

3:16
an Iterative Solution.

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

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

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

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

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

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

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

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

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

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

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

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

4:09
and doesn't like recursion.

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

4:15
after which our function will halt execution.

4:18
Python prefers an iterative solution.

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

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

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

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

4:35
particular language.

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

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

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

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

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

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

5:00
And to find out, on to the next video.
You need to sign up for Treehouse in order to download course files.
Sign up