Recursion Practice & Strategies in Python: A Tutorial on Solving Recursive Problems and Algorithms

developing recursive solutions to the problems that you're trying to solve isn't a skill that comes naturally to many people and i know this because it didn't come naturally to me but using one cool trick that we're going to reveal in today's lesson will hopefully give you a light bulb moment the same way that it did me in reframing the way that you think about these problems and giving you a much more approachable way to go about solving recursive challenges so let's get started by thinking about recursive structures and what we mean by this well we're talking about in this sequence a the simplest recursive data structure we can imagine which is a singly linked list and we can imagine a singly linked list where each of our node objects has some values associated with them so say 110 and 210 just some numbers out of the blue and then our lists are terminated with none not node none each of these are node objects so i might label these as my haystack we're going to be implementing a search algorithm here and we're going to be searching in a haystack so this will be our haystack of node objects all right so this is our linked list okay and if we're going to get some practice thinking about a recursive algorithm we need some problem to solve so we're going to be asking does this list include 210 does any node in this list include a value such as 210 in it right and if we want to come up with a recursive solution to this problem we're going to need to think a little bit differently than we would if we were thinking imperatively about this and so before we get into a recursive solution let's think about if if we were trying to think of a an imperative solution to this problem and when i use the word imperative i tend to mean loops right and this is what it classically means so imperative we're thinking about looping through a problem so we would start at the front and for each node in my list or check and see whether or not it's what i'm looking for and then we're done with it right so in an imperative solution to a problem often we think about like okay we're going to start at the very front and we're going to keep looping until we reach the end and if in the middle of that process we we find what we're looking for we'll go ahead and return if we get all the way to the end and then at the very last step would be well we didn't find it right and so this is a very um natural way of describing and coming up with a solution to a problem uh often for many people with recursion the trick that we're going to learn is to actually flip the script on that process entirely and try and think about well how do we solve this from the back of our problem or from the end of our problem from the simplest type of problem we can imagine and work our way back out of it so let's imagine what this might look like first our goal is to have a function that has a signature that looks something like this includes is going to be the name of our function and we're going to have two parameters right a haystack that's what we're searching through that's going to be our list of nodes and a needle all right so we're looking for a needle in a haystack and this should return a boolean right true fault and what we're writing out here is very much just pseudo code thinking about this problem in a very abstract hand wavy sense all right so what is the simplest problem we could solve here like what is the the easiest haystack we could imagine to to work through to know whether or not we found uh the needle that we're looking for well the empty list right the when there's nothing to search we know that sure enough there's no uh we haven't found the needle right so we can imagine one case that should be pretty easy to solve so it includes and if we're looking for you know our list is none or the empty list and we're looking for a needle like 210 right we would expect that to result in a false value right we haven't found 210 and 210 is not included in the empty list none right and so we would think of this as a base case and the strategy that we're learning here is to start by thinking about your base cases start with the simplest problems you can imagine what are the ways that that you know that you've sort of completed your job with the least amount of work possible this is a very lazy approach to thinking about solving a problem right well yeah of course like this is this would be easy to implement if you give me none i'm going to give you back false and and my job is done well what's the next most challenging list we could imagine solving or next most challenging haystack we can imagine let's say we're includes and what about a list where uh the haystack that we're given is just the head node of some list is going to be you know say the node 210 and i'm just going to draw an arrow to nothing we don't know what comes after this based on one invocation of this function right we're just given one node at a time and we're going to be trying to think about one node at a time that's going to be one of the key strategies involved in in this in this process and we're looking for 210. and this feels like a pretty easy solution too right like sure you give me 210 as as the first node in my haystack and i'm going to give you back true like because that's what you're looking for i know that we found it right so this would be another base case right we know uh exactly what to return we we can completely solve the problem that we were trying to solve at this point there's not you know i've seen enough right we haven't we don't have any more work to do well what's the next most challenging thing we could do so notice we're we're working our way from the simplest problem that we could solve to slightly more challenging slightly more challenging and uh the the key strategy we're gonna employ here is well if we don't know how to solve the problem with the current position we're at in this in this list we're going to do what we need to do with the current node and then leave the rest to recursion we're going to say oh you know recursive function calls that's your problem to go to go worry about right and so if we imagine okay well what about includes and we're going to use i'm just going to reference haystack as the variable that references you know the node 110 hey stack and 210 is what we're looking for and what is this going to result in well we're going to be lazy here we're going to say you know what we can't solve this but we know that you know the node you're looking for the value you're looking for isn't the the top of the haystack isn't the head of the haystack so i mean you know go do this again but on the rest of the list right and go go go leave the rest to the recursion right we're gonna we're gonna be lazy here and say okay uh we'll maybe check the next list using the exact same pro the next value in the list using the exact same process so it includes and then hey stack.next and i'm going to run out of space here so i'm just going to wrap around and say hey stack.next and 210 right so check the rest of the list for the value 210 and uh this is our recursive case okay so this is our recursive case and if the next value is going to be 210 then we would return true if it's going to be none then we know we've reached the end of our list and we're we've our job is complete otherwise if it's neither of those cases if it's neither of our base cases then we're going to try again on the next node right but notice we're sort of working our way from the back of the problem from the simplest case possible towards the recursive case that's going to move through each item recursively so now that we've got this general strategy down let's try implementing this in some code all right so in vs code i've got the starting point some of the starting code from our current exercise exercise six where we're implementing some linked list algorithms and i'm going to continue on in this file and i would encourage you to go ahead and set up exercise 6 to be sure you're ready to start on it and you can follow along with the video once you're there if you otherwise want to just jot down this code in a scratch file somewhere that would be totally fine too there's no more code than this for this particular exercise so pause the video here and be ready to continue coding and resume once you're done so let's take a look at what you're seeing here this class node is a node in a linked list it has two attributes a data attribute that's storing the number of a node and then next which is importantly an optional next node meaning it's either going to be a node or it's going to be none when we've reached the end of our list we've got a constructor that we've talked through before and then there's this magic method that's special because of these double underscores named repper and we're going to talk explicitly about repper in a video coming up right but for now i'm going to shorthand leave it to the documentation to say this is produces a string representation of a linked list and we can get a feel for this in just a moment once we are testing our data out but basically it's going to automatically create a string representation of a linked list so it's like 110 and then an arrow and then 210 and then an arrow and then none is what we would expect given our previous example so let's go ahead and set up a skeleton for the function we're trying to implement so def includes and we have our haystack which is a parameter and what is the type of haystack going to be well we need to be able to support an empty list but we also need to be able to support you know a node or some start of a node some head so we can use optional node as the parameter type and we need the thing that we're looking for that's going to be our needle which is an integer and it's a function that returns a boolean value and for documentation purposes we might just write okay return or just let's just form this in terms of a question because this is what we would call a predicate does is needle included is needle in the haystack right okay well we've previously you know applied our new strategy and technique for solving a recursive function so let's go take a look at what we had we had a base case where if haystack is none we're going to return false alright so let's go try and add that case to our code so if hey stack is none we've reached the end of our list so we can return false right our job is done there's no more for us to see here and you didn't find what you were looking for in this list else what we can do and actually let's just do this as an alif alif haystack.data is equal to needle then what are we going to do well this is the case where we found the needle in the haystack right and we're going to return true finally we have an else clause and this is going to be our recursive case so we've covered our two base cases and we can remind ourselves of those really quickly so we've covered the case where we found what we're looking for that's the second base case we found the case where we reached the end we didn't find what we were looking for that's that's the first base case and now we're saying in the recursive case well we don't know let's leave the rest of the problem to the beauty of recursion to to figure it out and process the rest of the list recursively by applying the same process recursively all right so let's try and express that in a little bit of python code otherwise we're going to return includes haystack.next so process the next to the list and with the same needle right and that's a pretty straight translation from trying to conceptualize a a solution to this problem by working our way out from the back and by thinking about how we solve the simplest problem possible and then making it slightly more complex slightly more complex and so let's try this out so i'm going to open up a repl and i'm going to say python to start a reply and from in my file is exercises dot x6 dot linked list import and i'm going to use the asterisk secure to bring in all of the names includes a node in one go if we wanted to i could you know we could also do it like this node and includes but generally you can use the asterisk if you want to to bring in all that matches all of the names in in a given file all right so now if we wanted to we can set up our list so our our our courses are going to be a node and the first node was 110 and it was followed by the next node is another node which is 210 and that was followed by none right so that was the end of our list so we've got two nodes and when we evaluate this we say well what is courses this is going to be where that wrapper method that magic method comes to be and we notice we get a really nice string representation 110 followed by 210 followed by none okay that's what we ultimately want to get to but how might we test includes um with something a little bit simpler and to test our base cases right so maybe we try uh calling includes first with a haystack of none and a needle of 210 right and this should hit our base case where haystack is none and return faults sure enough it does right we could try includes with the other base case where we have node of 210 followed by none and 210 and that's going to return true just as we expected right so those are two simple cases and the next thing we can test is includes courses of 110 right so courses remember is 110 followed by 210 followed by none and that worked and that required the recursive step we can make this list even longer if we wanted to test whether or not it works but i i assure you uh there's not many places for this solution to go wrong and it won't um the other thing we could test is what about testing the other base case where what we're searching for doesn't exist oh and i should have actually made this 210 here so let's let's be sure we we matched 110 which was our first base case actually in courses because that would have hit the lf before any recursive calls but 210 means we can test the recursive step where it's going to have to recur once and sure enough it worked i had too many parentheses when i tried to run it before and then if we were to try includes courses and then something that doesn't exist 999 that's when we would recur twice to hit the base case and return faults right if we wanted to we could just convince ourselves that this was working as we expected and we could print say the needle each time our uh oops sorry let's let's print the needle would be the same each time let's print hey stack.data so this would be like the first uh actually let's print haystack right and this will tell us what is the the list we're processing as we move through this problem all right and so if we wanted to actually import this we would need to quit out start again and from exercises ex06 that linked list import i'm going to use the star here and be lazy and now i could say includes and i'll just write out these courses directly so 110 node 210 followed by none and one parentheses match two parentheses match all right we're good uh and then we we're searching for say uh 210. and notice that the haystack when the first recursive function call to includes or when the first caller includes was made this wasn't a recursive call it's 110 and then in the first recursive call it's 210 and that ultimately evaluated to true but if we tried searching for something that didn't exist like 9999 you'll notice that we search through the enti the haystack where we are given the 110 and then the next time includes is called the head node or the haystack is a node that's 210 and then the last time it's none so we're moving one by one through each node in our list right and so the general strategy here that is the important takeaway in this mode of thinking is to try and make your life easy right get some easy wins in the bag get your base cases figured out first and then once you have your base cases you want to think about what's the smallest step i can take from where a base case is to working towards a base case in a recursive step right and this is actually great life advice too like get some easy wins first before you try and come up with a complete solution to a really difficult problem try and solve the easiest cases before you worry about all the complexities that might happen otherwise and the really neat thing about recursion when you start becoming more comfortable thinking in this way is that you'll realize that many times the recursive solution to a problem can be very simple and beautiful and once you see it it's like wow how did i not recognize when i first started looking at this problem that there would be something such a simple solution to it but it takes practice and it takes getting comfortable with thinking about the problem from the back end first rather than the very start of it and hopefully with this one cool trick some of these solutions to the recursive problems that you're trying to solve will be much easier to attack from the back to the front

Channel: Kris Jordan

Views: 26,187

Keywords:

Id: aj8f5NPAeTY

Length: 18min 20sec (1100 seconds)

Published: Thu Nov 12 2020