Recursive Functions5:03 with Pasan Premaratne
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