Heads up! To view this whole video, sign in with your Courses account or enroll in your free 7-day trial. Sign In Enroll
Well done!
You have completed Introduction to Algorithms!
You have completed Introduction to Algorithms!
Preview
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.
This video doesn't have any notes.
Related Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign upRelated Discussions
Have questions about this video? Start a discussion with the community and Treehouse staff.
Sign up
[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 upYou need to sign up for Treehouse in order to set up Workspace
Sign up