1 00:00:00,000 --> 00:00:03,637 [MUSIC] 2 00:00:03,637 --> 00:00:05,004 In the last video, 3 00:00:05,004 --> 00:00:10,307 we wrote a version of binary search that uses a concept called Recursion. 4 00:00:10,307 --> 00:00:13,030 Recursion might be a new concept for you. 5 00:00:13,030 --> 00:00:15,455 So let's formalize how we use it. 6 00:00:15,455 --> 00:00:20,150 A recursive function is one that calls itself. 7 00:00:20,150 --> 00:00:25,096 In our example the recursive binary search function called itself inside the body 8 00:00:25,096 --> 00:00:26,178 of the function. 9 00:00:26,178 --> 00:00:31,642 When writing a recursive function you always need a stopping condition. 10 00:00:31,642 --> 00:00:36,592 And typically we start the body of the recursive function with this stopping 11 00:00:36,592 --> 00:00:37,453 condition. 12 00:00:37,453 --> 00:00:41,260 It's common to call this stopping condition the base case. 13 00:00:41,260 --> 00:00:46,381 In our recursive binary search function, we had two stopping conditions. 14 00:00:46,381 --> 00:00:52,162 The first was what the function should return if an empty list is passed in. 15 00:00:52,162 --> 00:00:55,246 It seems weird to evaluate an empty list, 16 00:00:55,246 --> 00:00:59,751 because you wouldn't expect to run search on an empty list. 17 00:00:59,751 --> 00:01:02,096 But if you look at how a function works, 18 00:01:02,096 --> 00:01:05,023 recursive binary search keeps calling itself. 19 00:01:05,023 --> 00:01:09,259 And with each call to itself, the size of the list is cut in half. 20 00:01:09,259 --> 00:01:13,119 If we searched for a target, that didn't exist in the list, 21 00:01:13,119 --> 00:01:17,904 then the function would keep having itself, until it got to an empty list. 22 00:01:17,904 --> 00:01:22,306 Consider a three element list, with numbers, 1, 2, 3, 23 00:01:22,306 --> 00:01:25,367 where we're searching for a target of 4. 24 00:01:25,367 --> 00:01:28,000 On the first path, the midpoint is 2, so 25 00:01:28,000 --> 00:01:31,174 the function would call itself with the least 3. 26 00:01:31,174 --> 00:01:35,767 On the next pass the midpoint is 0 and the target is still greater so 27 00:01:35,767 --> 00:01:40,360 the function would call itself, this time passing in an empty list 28 00:01:40,360 --> 00:01:45,055 because an index of 0 + 1 in a single element list doesn't exist. 29 00:01:45,055 --> 00:01:50,006 When we have an empty list, this means that after searching through the list, 30 00:01:50,006 --> 00:01:51,667 the value wasn't found. 31 00:01:51,667 --> 00:01:55,554 This is why we define an empty list as a stopping condition or 32 00:01:55,554 --> 00:01:57,667 a base case that returns false. 33 00:01:57,667 --> 00:01:59,152 If it's not an empty list, 34 00:01:59,152 --> 00:02:03,235 then we have an entirely different set if instructions we want to execute. 35 00:02:03,235 --> 00:02:07,742 First, we obtain the mid point of the list, once we have the mid point, 36 00:02:07,742 --> 00:02:11,515 we can introduce our next base case or stopping condition. 37 00:02:11,515 --> 00:02:16,547 If the value at the midpoint is the same as the target the we'll return true. 38 00:02:16,547 --> 00:02:21,333 With these two stopping conditions we've covered all possible paths of 39 00:02:21,333 --> 00:02:23,854 logic through the search algorithm. 40 00:02:23,854 --> 00:02:26,766 You can either find the value or you don't. 41 00:02:26,766 --> 00:02:28,605 Once you have the base cases, 42 00:02:28,605 --> 00:02:33,538 the rest of the implementation of the recursive function is to call the function 43 00:02:33,538 --> 00:02:37,164 on smallest sum lists until we hit one of these base cases. 44 00:02:37,164 --> 00:02:41,598 Going back to our visualization for a second, [SOUND] we see that recursive 45 00:02:41,598 --> 00:02:46,405 binary search calls itself a first time, [SOUND] which then calls itself again. 46 00:02:46,405 --> 00:02:48,669 For the initial list we started with, 47 00:02:48,669 --> 00:02:53,634 the function only calls itself a few times before a stopping condition is reached. 48 00:02:53,634 --> 00:02:59,205 The number of times a recursive functions calls itself is called Recursive Depth. 49 00:02:59,205 --> 00:03:03,558 And the reason I bring all of this up is because, if after you start learning 50 00:03:03,558 --> 00:03:07,930 about algorithms, you decided you want to go off and do your own research. 51 00:03:07,930 --> 00:03:12,875 You may start to see a lot of algorithms implemented using recursion. 52 00:03:12,875 --> 00:03:16,724 The way we implemented binary search the first time is called 53 00:03:16,724 --> 00:03:18,318 an Iterative Solution. 54 00:03:18,318 --> 00:03:22,587 Now, when you see the word iterative, it generally means the solution 55 00:03:22,587 --> 00:03:25,805 was implemented using a loop structure of some kind. 56 00:03:25,805 --> 00:03:29,710 A recursive solution on the other hand is one that involves a set 57 00:03:29,710 --> 00:03:33,331 of stopping conditions and a function that calls itself. 58 00:03:33,331 --> 00:03:38,210 Computer scientists and computer science textbooks, particularly from back in 59 00:03:38,210 --> 00:03:42,601 the day, favor and are written in what are called Functional Languages. 60 00:03:42,601 --> 00:03:47,819 In functional languages, we try to avoid changing data that is given to a function. 61 00:03:47,819 --> 00:03:52,929 In our first version of binary search, we created first and last variables using 62 00:03:52,929 --> 00:03:57,829 the list and then modified first and last as we needed to arrive at a solution. 63 00:03:57,829 --> 00:04:00,539 Functional languages don't like to do this, 64 00:04:00,539 --> 00:04:04,990 all this modification of variables and prefer a solution using recursion. 65 00:04:04,990 --> 00:04:09,857 And a language like Python, which is what we're using, is the opposite, 66 00:04:09,857 --> 00:04:11,877 and doesn't like recursion. 67 00:04:11,877 --> 00:04:15,101 In fact, Python has a maximum recursion depth, 68 00:04:15,101 --> 00:04:18,257 after which our function will halt execution. 69 00:04:18,257 --> 00:04:21,082 Python prefers an iterative solution. 70 00:04:21,082 --> 00:04:23,542 Now, I mention all of this for two reasons. 71 00:04:23,542 --> 00:04:28,535 If you decide that you want to learn how to implement the algorithm in a language 72 00:04:28,535 --> 00:04:30,814 of your choice that's not Python. 73 00:04:30,814 --> 00:04:35,661 Then you might see a recursive solution as the best implementation in that 74 00:04:35,661 --> 00:04:37,233 particular language. 75 00:04:37,233 --> 00:04:41,501 I'm an iOS developer, for example, and I work with a language called Swift. 76 00:04:41,501 --> 00:04:46,019 Swift is different than Python, it doesn't care about recursion depth and does some 77 00:04:46,019 --> 00:04:50,553 neat tricks where it doesn't even matter how many times your function calls itself. 78 00:04:50,553 --> 00:04:55,086 So if you want to see this is Swift code, then you need to know how recursion works. 79 00:04:55,086 --> 00:04:57,328 Well, and now, you have some idea. 80 00:04:57,328 --> 00:05:00,774 And the second reason I bring it up is actually way more important. 81 00:05:00,774 --> 00:05:03,124 And to find out, on to the next video.