this presentation is delivered by the Stanford center for professional development good afternoon all right you guys are talkative so just we talk just a little bit about the vocabulary recursion at the end of Friday it was a very rushed for time so I mean it's going to repeat some of those words to get us thinking about what the context for solving problems recursively looks like and then we go on and do a lot sample so the idea is that a recursive focus is one that calls itself that's really all it means right at the at the most trivial level that says that in the context of writing a function binky it's going to make a call or one or more calls to binky itself passed an argument as part of solving or doing some task the idea is that we're using that because the problem itself has some self similarity where the answer I was seeking so the idea of surveying the whole campus can actually be thought of as well like it gets ready to survey this part of campus and this part of campus somebody to survey all the freshmen some buddies and whatnot that those in a sense are those surveys are just smaller instances of the same kind of problem I was originally trying to solve that if I can recursively delegate those things out and then they themselves may in turn delegate even further to smaller but same structured problems to where we could eventually get to something so simple in that case of like well asking 10 people for their input that don't require any further decomposition we will have worked our way to this base case if then we can gather back up those results and solve the whole thing this is going to feel very mysterious at first and some of the examples I give you'll say well I have really easy alternatives other than recursion so it's gone up not going to seem even worth the pain of trying to get your head around it but eventually I'm going to work away at the problems where recursion really is the right solution and there are no other alternatives that are obvious or simple to do so the idea throughout this week is actually just a lot of practice that telling you what the terms mean I think is not after going to help you understand it I think what you need to see is examples and so I'm going to be doing you know four or five examples today four or five examples on Wednesday and for five example on Friday that each kind of build on each other kind of take the ideas and get a little more sophisticated but by the end of the week I'm hoping that you're going to start to see these patterns and realize that in some sense the recursive solutions tend to be more alike than different that once you have your head around how to solve one type of problem you may very well be able to take the exact same technique and solve several other problems that that may sound different at first glance but in the end the recursive structure looks the same so I'd say just just hold the the discomfort a little bit and stand and wait to see as we keep working which example may it be the one that kind of sticks out for you to help you get it through so we're going to start with things that fit in the category of functional recursion the functional in this case just says that you're running functions that return some non-void thing an integer a string and you know some vector of results or whatever that is and that's all it means to be a functional recursion it's a recursive function that has a result to it and because of the recursive nature it's going to say that the outer problems result the answer to the larger problem is going to be based on making calls one or more calls to the function itself to get the answer to a smaller problem and then adding them multiply them comparing them to decide how to formulate the larger answer all recursive code follows the same decomposition into two cases sometimes there's some subdivisions within there but two general cases the first being this base case that's something that the recursion eventually has to stop right that we keep saying take the task and break it down make it a little smaller but at some point right we really have to KITT stop doing that right we can't go on infinitely there has to be some base case the simplest possible version of the problem that you can directly solve you don't need to make any further recursive calls so the idea is that kind of bottoms out there and then allows the recursion to unwind the recursive cases and there may be one or more of these right in the case where it's not that simple but the answer isn't directly solvable but if you had the answer to a smaller simpler version you would be able to assemble that answer you're looking for using that information from the recursive call so that's the kind of structure that they all look like some sort of test if I'm at the base case then do the base case thing and return it otherwise make some recursive calls and use that to return a result from this iteration so let's first look at something that the first couple examples I'm going to show you actually are going to be so easy that in some sense they're almost going to be a little bit counterproductive because I going to teach you that well recursion is doesn't let you do things you already know how to do and I'm gonna work my way up the ones that actually get beyond that but let's look at first the raised to power c po plus has no built in exponentiation operator there's nothing that raises a base to a particular exponent in the operator set so if you want it you need to write it or you can use there's a math library called pal 4 raised to power we're going to write our own version of it because it's going to give us some practice thinking about this and the first one I'm going to show you is one that should feel very familiar and very intuitive right which is using an iterative formulation if I'm trying to reface the exponent that's really simply multiplying baits by itself exponent times so this one uses a for loop and does so right starts the result at 1 and for iterations the number exponents right keeps multiplying right to get there now so that one's fine and it will perfectly work I'm going to show you this alternative way that starts you thinking about what it means to divide a problem up in a recursive strategy base to the exponent I want to raise you know five to the tenth power if I had around some delegate right some clone of myself that I could dispatch to solve the slightly smaller problem of computing five to the ninth power then all I would need to do is take that answer and multiply it by one more five I get five to the tenth okay if I write code that's based on that then I end up with something here and I'm going to let these two things go through to show us that to compute the answer to you know 5 to the 10th power what I really need is the answer to five to the ninth power which I do by making a recursive call to the same function I'm in the middle of writing so this is rays that I'm defining and in the body of it makes a call to raise that's what what is the mark of a recursive function here I passed slightly different arguments in this case write one smaller exponent which is getting a little bit closer to that simplest possible case write that we will eventually terminate at where we can say well I don't need to further dispatch any delegates and any clones out there to do the work but if the exponent I'm raising it to is zero by definition anything raise the exponent 0 is 1 I could just stop there so in computing five to the tenth right I want to see some recursion at work let me take this code into the compiler so that we can see a little bit about how this actually works in terms of that so that's exactly the code I have there and I can say you know something that I can I know the answer to how about that we'll take a look at it do when it's work so 5 times 5 times 5 325 so we can test a couple little values while we're at it right 2 to the sixth power that should be 64 just to see a couple of the cases just feel good about what's going on and then raising let's say 23 to the 0 power should be 1 as anything raised to the 0 power speak it's a little bit of spot testing to feel good about what's going on now I'm going to go back to this idea like 2 to the 6th and I'm going to set a breakpoint here take that right point out and I'll run this guy in the debugger takes a little bit longer to get the debugger up and running so I'll have to make a little patter up while we're going here and then it tells me right now it's breaking on rays and I can look around in the de butter and this is a that did it not pick up my compilation I think it did not I must not have saved it right before I did it because it's actually got the basis 23 and the expo 2-0 turns out I don't want to see that case I'm going to go back and try again want to see it oops oh I do not what about her and I'm just interested in knowing a little bit about the mechanics of what's going to happen in a recursive situation that if I look at the first time I hit my breakpoint then I'll see that there's a little bit of the you know the beginnings of the student main some some stuff behind it there's a little bit of magic underneath your stack that you don't really need to know about but starting from main it went into Ray's and the arguments it has there's the basis to the exponent is six if I continue from here then you'll notice the stack frame got one deeper there's actually another indication of rays and in fact they're both active at the same time that the previous Ray's that was trying to compute two to the sixth is kind of in stasis back there waiting for the answer to come back from this version right which is looking to raise two to the fifth power if I continue again I get to the fourth I keep doing this right I'm going to see these guys kind of stack up each one of those kind of waiting for the delegate or the clone to come back with that answer so that then it can do its further work incorporating that result to compute the thing it needed to do I get down here to raising two to the first power and then finally I get to the two to the zero and so now I've got these you know a torso stack frame six six up there this one if I step from here all right it's going to hit the base case of returning one and then we will end up kind of working our way back out so now we are at the end of the two to the one case right that's using the answer it got from the other one multiplying it by two now I'm at the two to the two case and so each of them is kind of unfolding and the stack is what's called unwinding it's popping back off the stack frames that are there and kind of revisiting them each passing up the information it got back and eventually you know telling us that the answer was sixty-four so we'll let that go so the idea that all those stack frames kind of exist at the same time right they're all being maintained independently so the idea that the compiler isn't confused by the idea that raises invoking raise which is invoking raise that each of the raised stack frames is distinct from the other ones so the implications are actually kept separated so one head to the sixth the next one had two to the fifth and so on and then eventually we need to get some make progress toward that base case so that we can then stop that recursion and unwind let me actually show you something while I'm here which is that one thing that's a pretty common mistake to make early on in a recursion is to somehow fail to make progress toward that base case or to not all cases make it to the base case for example if I I did something here where I I forgot to subtract one up on it and I said oh yeah I need to as you know in this case I'm passing it exactly the same arguments I got if I do this and I run this guy then what's going to happen is it's going to go to the 6 to the 6 to this X right and I'm going to let go of this this break point here because I don't really want to watch it all happening and there it goes loading six thousand four hundred and ninety three that phrase take a while as you can imagine and usually once you see this error message it's your clue to say yeah I can cancel I know what happened right there was the only reason right I should have gotten you know sixty five hundred snack frames right load it up is because I made a mistake right that's causing the stack to totally overflow and so the behavior right on in C++ or C rate is that when you have so many of those stack frames eventually the space that's been allocated or set aside for the function stack will be exhausted it will use all the space it has and run up against a boundary and typically report it in some way that suggests sometimes you'll see stack overflow stack out of memory error in this case showing you that you know seven thousand stack frames right that are behind you and then if you were to examine them you can see oh they all have exactly the same arguments and they weren't getting anywhere I'm not going to actually let it do that because I'm too impatient they fix this code along here but other things write that even this code that that actually looks correct for some situations also has a subtle bug in it even after I fix this right which is that right now it assumes that the exponent is positive right then it's some number you know that I can subtract my way down to zero if I actually miss cauldre's and I gave it a negative exponent right it would go into infinite recursion as well right if you started it it you know ten to the negative first power right it would go negative first- second- third you know 6,500 stack frames later right we'd run out of space in the case of this right since whittling and tending to handle those positive powers we could just put an arrow in there there's like that if the exponent is less than zero then raise an error and don't even try to do anything with it so let me show you just a slightly different way of doing this that's also recursive but that actually gets the answer a little bit more efficiently and this is a different way of dividing it up but still using a recursive strategy which is that if I'm trying to compute you know five to the tenth power that if I had the answer not of you know five to the ninth power but instead I had the answer of five to the fifth power and then I multiply that by itself I would get that five to the tenth power that I seek and then there's a little bit of the case though of like well what if the power I was trying to get was odd if I were trying to raise it to the eleventh power right I can compute the 1/2 power right which get me to the fifth 2 multiplied by the fifth but then I need one more base multiplied in there to make up for that half ok and so I can write another recursive formulation here same sort of base case right about detecting when we've gotten down but then in this case the recursive call we make is to base of the exponent divided by two and then we use it with the if else on whether the exponent was even or odd to decide whether to just square that number or to square it and tack in another power of the base while we're at it so this one right is going to be much more quick about getting down to it whereas the one we saw right was going to put one stack frame down for every successive exponent power so if you wanted to raise something to the 10th or 20th the thirtieth power right then you were giving yourself ten twenty thirty stack frames something like that you know thirty-five frames is not really something to be worried about but if you're really trying to make this work on much much larger numbers which would require some other work because exponent is a very rapidly growing operator and overflow your integer quickly but this way right very quickly divides in half so it goes from a power to 100 to a power of 50 to 25 to 12 you know to 6 to 3 to 2 to 1 so that dividing in half is a much quicker way to work our way down to that base case and get our answer back and we're doing a lot fewer calculations then all those multiplies one per base so just a little diversion so let me tell you something that just a little bit about a kind of style as it applies to recursion that recursion is really best when you can express it in the most kind of direct in a clear and simple code it's hard enough to get your head around a recursive formulation without complicating it by kind of having a bunch of extraneous parts right where you're doing more work than necessary or redundantly handling certain things and one thing that's actually very easy to fall in the trap of is is thinking about well there's lots of other base cases you might be able to easily hand so why not just go ahead and call out for them test for your getting your at the base case you're close to the base case you know checking before you might make a recursive call if you're going to hit the base case when you make that call well then why make the call I'll just anticipate it and get the answer it would have returned anyway and it can lead to code that looks a little bit like this before you're done you're like oh well the exponent 0 that's one well if it's you know that X 1 is 1 Y can just return the base well if it's 2 I can just multiply base by itself and if it's 3 I can start doing this you that this you know certainly you can follow this to the point of absurdity and even for some simple cases that might seem like well you're saving yourself a little bit of extra time or like why go back around and let it make another recursive call right I can stop it right here it's easy to know that answer but as you do this right it complicates the code right it's a little harder to read it's a little hard to bug and really the expense of making that one extra call to extra calls you know is not the thing to be worried about what we really want is the cleanest code right that expresses what we do that has the simplest cases to test and examine and to follow and not muck it up with things that in effect right don't change the computational power of this but just introduce the opportunity for error like instead of a multiply here I accidentally put a plus right it might be easy to overlook it right and not realize what I've done and then end up you know computing the wrong answer based on when it gets to the base case of two in fact if you do it this way right you know it's like most things would stop at 3 but then these would suddenly become kind of their own special cases that were only hit if you directly call them with the to the recursive cases will all stop earlier it just makes it complicate your testing path now because not everything is going through the same code so we call this arm's length recursion I put a big X on that looking ahead testing before you get there just let the code fall through so a Dan who's not here day but he talked to me at the end of Friday's class and it made me want to actually just give you a little bit of a insight into recursion as it relates to efficiency that recursion by itself just the idea of applying a recursive technique to solving a problem does not give you any guarantee if it's going to be the best Ellucian the most efficient solution or the fact that's going to give you a very inefficient solution I think sometimes people have kind of a bad rap on recursions like oh well it will definitely be inefficient that actually is not guaranteed recursion often requires exactly the same resources as the iterative approach that it takes the same amount of effort right surveying the campus if you're going to survey the ten thousand people on campus and get everybody's information back whether you're doing a divide-and-conquer whether you're sitting out there white Plaza asking each person one by one in the end ten thousand people got surveyed that the recursion is not part of what made that longer or shorter it might actually depending on kind of how you have resources work out better like you could get a bunch of people in parallel surveying you might end up completing the whole thing in less time but it required kind of more people and more clipboards and more paper while the process was ongoing than me standing there with one piece of paper to clipboard but then again it took lots of my time right to do it so in many situations it's really no better or no worse than the alternative it makes a little bit of some trade-offs of where the time is spent there are situations though where recursion can actually make something that was efficient inefficient there's situations where it can take something that was inefficient and make it efficient so it's it's more of a case-by-case basis right to decide whether recursion is the right tool if efficiency is one of your primary concerns I will say that for problems with simple iterative solutions that you know that that operate relatively efficiently iteration is probably the best way to solve it so the you know raised to power it's like yeah you can certainly do that iteratively you know there's not some huge advantage that recursion is offering I'm using them here because they're simple enough to get our head around we're going to work our way toward problems where we're going to find things that that require recursion just kind of one of the third points I put are well then why do we model belittle recursion what's recursion is going to be good for first off recursion is awesome there are some problems right that you just can't solve using anything but recursion so that the alternative is like Walt is write it iteratively won't work right you'll try but you'll fail right they inherently have a recursive structure to them where recursion is the right tool for the job often it produces the most beautiful direct and clear elegant code the next assignment that will go out has these problems that you do in recursion and they're each about you know 10 lines long some of them you know five lines long they do incredible things in five lines because of the descriptive power of describing it as here's a base case and here's a recursive case and everything else right just follows from applying this and reducing the problem step by step so you will see things that where the recursive code is just beautiful clean elegant easy to understand easy to follow easy to test solves a recursive problem and in those cases it really is a much better answer than trying to hack up some other iterative form that may in the end be just no more efficient maybe even less efficient so don't don't let efficiency be kind of a big fear of what recursion is for you okay someone do more examples I got like three more examples so or four I think today so I will just keep showing you different things and hopefully the patterns will start to kind of come out of the mist for you a pound roll string is one that reads the same forwards and backwards when reversed right you know so was it a car or a cat I saw all right if you read that backwards it turns out says the same thing go hang a salami I'm a lasagna hog also right handy when you need to have like a bar bet over what the longest palindrome is to have these things around there's certainly ways to do this iteratively if you were given a string and you're interested in oh well is it a palindrome that you could kind of do this marching where you're looking outside and kind of marching your way into the middle but we're going to go ahead and let recursion kind of help us deal with the the subproblem of this and imagine that at the simplest possible format you'd say well a palindrome consists of an interior palindrome and then the same letter tacked on the front in the back so if you look at was it a car a cat i saw there are two w's there it starts and it ends with a w so all palindromes must start and end with the same letter okay let's check that and if that matches then extract that middle and see if it's a palindrome okay so it feels like I didn't really do anything right it's like all I did was match two letters and then I said okay and then by the way delegate you know this this problem back to myself making a call to a function I haven't even finished writing to examine the rest of the letters okay and then I need a base case I got a recursive case right take off the outer two letters make sure they match recur on the inside what our this is the simplest possible palindrome one letter one letter makes a good palindrome right one letter right is like by definition right first and last letter or the same letter so it matches that's a great base case is it the only base case two letters yet two letters is also kind of important but like there's actually an even simpler form right it's the empty string right so so both the empty string and a single gary string are by definition right the world's simplest palindromes right they meet the requirements right that they read the same forward and backwards empty string forwards and backwards as trivially they say and so that makes it even easier than doing the two letter case so if i write this code to look like that where if the length of the string is 1 or fewer so that handles both the 0 and the 1 case then I return true right those are trivial palindromes right of the easiest you know immediate detection otherwise right I've got a return here that says if the first character is the same as the last character and the middle so the substring starting at position 1 that goes for length minus two characters that picks out the interior discarding the first and last characters if that's also palindrome then we've got a palindrome and so given the short-circuiting nature of the and if it looks at the outer two characters and they don't match it immediately just stops right there and says false if they do match then it goes on looking you know at the next interior pair which will stack up a recursive call looking at its two things and eventually we will either catch a pair that doesn't match and then this false will immediately kind of return its way out or we'll keep going all the way down to that base case hit it true and know that we we do have a full palindrome there so you could certainly write this with a for loop it's actually writing over the for loop is I think almost a little bit trickier because you have to keep track of kind of which part of the string are you on what happens when you get to the middle and things like that that in some sense that the recursive form really kind of sidesteps that by really thinking about it in a more holistic way like well the outer letters plus an inner palindrome gives me the answer I'm looking for so this idea of taking a function here in the middle of writing and making a call to it as though it worked it's something they require this this idea of the leap of faith like you haven't even finished describing how is palindrome operates and there you are making a call to it depending on it working in order to get your function working is a very kind of whacky thing to get your head around it feels a little bit mystical at first so that that that feeling you feel a little bit sort of discombobulated about this is probably pretty normal but we're going to keep seeing examples and hope that it starts to feel a little less unsettling anybody want to ask a question about this so far so I guess create your base case first then test it so that's a great question so I would say typically that that's a great strategies right is get a base case and test against to the base case it in the one character that the two character strings and then imagine kind of one layer out things that will make one recursive call only right and so in this case for the pound rubs it's like well what's a two character string right one that has a B one has a a right so one that is a palindrome one that is it and watch it go through then from there you have to almost take that leap and say you know it worked for the base case it worked for one out and then you have to start imagining well if it works for a string of length n it'll work for one of n plus one and that in some sense you testing and exhaustively write across all strings is of course impossible so you have to kind of move to sort of a larger case where you can't just hit their trace the whole thing you'll have to and sometimes take a faith thing that says if it could have computed whether the interior is a palindrome then adding two characters on the outside right and and massaging that with that answer should produce the right thing it's just a bigger test right that that verify that the recursive case right when exercise does the right thing then the pair together write all your code is going through you know these same lines right the outer case going down to the recursive case and down to that base case and that that's one of the beauty of writing it recursively right is that in some sense once this piece of code works for some simple cases the endings extending it to larger cases right is is almost I want to say guarantee that movie makes it sound too easy but in fact right if it works for cases of n and then n plus one then it will work for a hundred and one hundred and one and six thousand six thousand and want to cut all the way through all the numbers by induction yeah so and definitely like though was it a car right - I definitely would should be taking my spaces out of there make it right so you are totally correct about that okay so let me show you one where recursion is going to definitely buy us some some real efficiency and some real clarity and solving a search problem I've got a vector let's say it's a vector strings factor numbers vector of anything that's really matter and I want to see if I can find a particular entry in it right so unlike the set which can do a fast contains for you right in vector right if I haven't done anything special with it then there's no guarantee about where to find something and so if I want to say well is you know there did somebody score 75 on the exam well then I'm going to have to just walk through the vector starting it slot 0 walk my way to the end and compare to see if I find in 75 if I get to the end I haven't found one that I can say no so that's what's called linear search linear kind of implies this kind of left-to-right sequential processing and linear search has the property right that as the size of the input grows right the amount of time taken to search it kind of grows in proportion so if you had a thousand member array and you doubled its size you would expect that doing a linear search on it to take twice as long for an array that's twice as large okay the strategy we're going to look at today is binary search which is going to try to avoid this looking and every one of those boxes to find something it's going to take a divide and conquer strategy and it's going to require a sorted vector so in order to do an efficient lookup it helps if we've done some pre rearrangement of the data in this case right putting it into sorted order is going to make it much easier for us to be able to find something in it because we have better information about where to look so much much faster so we'll see that that certainly there was some cost to that but typically binary search is going to be used when you have an array where you don't do a lot of changes to it so that putting it in a sorted order can be done once and then from that point forward you can search it many many many times getting the benefit of the work you did to put it in sorted order if you plan to sort it just to search it then in some sense all the time you spent sorting it would kind of count against you and unlikely to come out ahead so the the insight we're going to use is that if we have this in sorted order right that and we're trying to search the whole thing we're looking for let's say the number 75 is that if we just look at the middlemost element so we have this idea that we're looking at the whole vector right now from the start to the end and I look at the middle element I say it's a 54 and I can say well if 75 is in this vector because it's in sorted order it can't be anywhere over here right if 50 54 is right there everything to the left of 54 must be less than that common 70 5 wouldn't be over there so that means that I can just discard that half of the vector and from further consideration and so now I have this half to continue looking at which is the things that are to the right of 54 all the way to the end I use the same strategy again I say well if I'm searching a vector so last time I was searching a vector that had 25 elements now I've got one that's got just 12 again I use the same strategy look at the one in the middle I say oh it's an 80 and then I say well the number I'm looking for is 75 it can't be to the right of the 80 it must be to the left of it and then that lets me get rid of another quarter of the vector if I keep doing this right I get rid of half and then a quarter and then an eighth and then a sixteenth that very quickly right I will narrow in on the position where if 75 is in this vector it has to be or I'll be able to conclude it wasn't there at all that I kind of worked my way in and I found a 74 over here - 76 over there then I'm done and so that base case comes when I have such a small little vector there where my bounds have kind of crossed in such a way that I can say well I never found what I was looking for okay so let's walk through this bit of code that kind of puts into C++ the thing I just described here I've got a vector in this case I'm using a vector that's containing strings it could be in Syd could be anything it doesn't really matter I've got a start and a stop which I identify the sub for SHINee of the vector that we're interested in so the start is the first index to consider the stop is the last index to consider so the very first call to this will have start set to zero and stop set to the vectors size minus one i compute the midpoint index which is just the sum of the start and stop divided by two and then I compared the key that I'm looking for to the value of that index of looking R in the middle if it happens to match then I return that so the goal of binary search in this case is to return the index of a matching element within the vector or to return this not found negative one constant if it was unable to find any match anywhere so when we do find it at whatever level the recursion is we just can immediately return that yeah we're done we found it it's good otherwise right we're going to make this recursive call that looks at either the left half of the right half based on if key is less than the value we found at the midpoint then the place we're searching is still has the same start position but is now capped by the element exactly to the left of the midpoint and then the right one the inversion of that right one to the right of the midpoint and the stop unchanged so taking off half of the elements under consideration at each stage eventually right I will get down to the simplest possible case in the simplest possible case isn't that I have a one element vector and I found it or not the really simple case is actually I have zero elements of my vector that I just kept you know moving in the upper and lower bound point until they crossed which meant that I ran out of elements to check and that happens when the start index is greater than the stop index or the start and the stop if they're equal to each other mean that you have a one element vector left to search but once you if for example if you got to that case we have that one element vector left to search you'll look at that one and if you if it matches you done otherwise right you'll end up either decrementing this stop to move past the start or incrementing the start to move past the stop and then that next iteration will hit this base case it said I looked at the last element in a one element vector it didn't work out I can tell you for sure it's not found if it had been here I would have seen it and this is looking at just one element each recursive call and the recursive calls in this case stack up to a depth right based on the logarithm of the size to the power two so that if you have a thousand elements right that you look at one and now you have a 500 element collection look at again you look at one you have a 250 element 125 60 you know 30 15 so at each stage right half of them remain for the further call and the number of times you can do that right for a thousand is the number of times you can divide a thousand by two which is the log base two of that which is roughly 10 so if you were looking at a thousand number array if it's in sorted order it takes you ten comparisons to conclusively determine where an element is if it's in there or that it doesn't exist in the end the array at all if you take that thousand element array and you make it twice as big so now I have a two thousand member array how much longer does it take one more step just one right if you look at one and now you have a thousand member a so however long it took you to do that thousand member array it takes one additional comparison kind of one stack frame on top of that to get its way down so this means actually this is super efficient that you can search so for example a million is roughly 2 to the 20th power so you have a million entry a collection of search it will take you 20 comparisons right to say for sure it's here or not and here's where I found it just 20 you go up to you know two million takes 21 right that the very very slow-growing function right that longer than function so that tells you that that this is going to be a very efficient way of searching a sorted array it's a category thing called the divide-and-conquer right that take a problem divide it you know and typically in half but sometimes in thirds or some other way and then kind of in this case it's particularly handy that we can throw away some part of the problem so we divide and focus on just one part to solve the problem all right so this is the first one that that's going to start to really inspire you for how recursion can help you solve problems that you might have no idea how to approach any other way than using a recursive formulation so this is an exercise that comes out of the reader in chapter 4 and the context of it is you have n things so maybe it's n people in a dorm 60 people at a dorm and you would like to choose K of them let's make a real number for for people to go together with flicks ticker clicks so of your $60 mates how many different ways can you pick a subset of size 4 that doesn't repeat any of the others so you can pick the two people you know from the first floor one person from the middle floor one person for the top floor then you can kind of shuffle it up but what if you took all people from the first floor these people from that room and what not you can imagine there's a lot of kind of machination x' right that be present here and counting them it's not quite obvious unless you kind of go back to start working on your real math skills how it is that you can write a formula for this so what I'm going to give you is a recursive way of thinking about this problem so I drew a a set of the things we're looking at so there n things that we're trying to choose k out of so right now I've got you know 12 or so people or you know items whatever it is what I'm going to do is I'm gonna Majan just designating one totally at random right so pick Bob right Bob is one of the people in the dorm I'm going to kind of separate him from everybody else mentally in my mind and draw this line and kind of marking with a red flag that says that spot okay so Bob might go to flix or might not go to flex some of the subsets right for going to flex will include Bob and some will not okay so what I'd like to think about well as well how many different subsets can I make that include Bob and how many different subs it's going to make that don't include Bob and if I added those together then that should be the total number of subsets I can make from this collection okay so the subsets that include Bob so once I've committed to Bob being in the set and let's say I'm trying to pick four members out of here then I have Bob then I have to figure out how many ways can I pick three people to accompany Bob to the flicks and so I'm picking from a slightly smaller population or the population went down by one and the number I'm seeking went down by one and that tells me all the ways I can pick three people to go with Bob the ones that don't include Bob and Bob's just out of the running I look at the remaining population which is still one smaller everybody but Bob and I look for the ways I can still pick four people from there so what I have here is trying to compute C of NK is trying to compute C of n minus 1 K minus 1 and add it to C of n minus 1 K so this is picking friends to accompany Bob this is picking people without Bob and those together and I will have the total number of ways I can pick K things at an N so very much relying on this recursive idea of well if I had the answer you know I don't feel smart enough to know the answer of you know directly but if I could defer it to someone who was actually willing to kind of do more you know scrutiny into this thing well if you could tell me how many you know groups of 3 you can join with Bob and how many groups before you can pick without Bob I can tell you what the total answer is the simplest possible base case right we're going to work our way down to is when there are just no choices remaining at all so if you look back at my things that are here in both cases right the population is getting smaller and in one of the recursive calls right the number of things I'm trying to pick is also getting smaller so they're both making progress toward kind of shrinking those down to where there's kind of more and more constraints on what I have to choose for example on this one as I keep shrinking the population by one and trying to get the same number of people eventually I'll be stuck trying to pick three people out of three right where I'm trying to pick K of K remaining well there's only one way to do that which is to take everyone on this one I'll eventually keep picking people so the K is always less than the N in this case that the K will eventually kind of bottom out raw say well I've already picked all the people I've already picked for people I need to pick zero more and at that point that's also very easy right picking zero out of a population there's only one way to do that so what we end up with is a very very simple base case of if k equals zero so I'm not trying to choose anymore I've already committed all the slots or if K is equal to n where I've discarded a whole bunch of people and now I'm down to where I'm facing okay I got to get four and I've got four left well there's only one way to do those things and that's to take everybody or take nobody and then otherwise I make those two recursive calls with Bob without Bob add them together to get my whole result that's wacky I'm going to read you something and then we'll call it a day I brought a book with me I stole this for my children