"How to Make a Website" was retired on March 24, 2020. You are now viewing the recommended replacement.
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