Generating Linked Lists Recursively - A tutorial and strategy for constructing recursive structures.

when writing programs that involve recursive data structures such as linked lists or trees you'll often find it's useful to be able to write a function that can produce such a data structure using a recursive process and in this video we're going to take a look at some common strategies for attacking these problems we're going to extend the strategies we learned in the earlier lessons where we were working through a linked list recursively here we're going to be producing a linked list recursively and the function we're going to implement is one where we're going to be given two numbers as inputs and try and produce a sequence of nodes in a linked list that increase from our first argument to up to but not including our second so we're going to write a function that can produce a sequence of lists of linked lists nodes all right so let's imagine our goal is sequence right so seq and let's say we have something like one and as our input arguments and we're hoping that this returns a list where 1 is followed by 2 is followed by 3 and it's not followed by 4 it's followed by none right so 1 2 3 none right and that's sort of the goal of this function we're trying to write a function that produces a sequence of nodes on our behalf and we'd like to be able to do this recursively so if we apply the strategies that we thought about before rather than thinking about a complex case like this we should start simple start lazy start with the easiest thing we can imagine so the easiest thing we can imagine is probably something like sequence of 4 4 all right where uh you know this is probably the the easiest case we can address because we're going to return none right we're starting from our low argument and going up to the high argument not inclusive of it so our job is done here we have no more work to do when our first argument we provided the first parameter of this function is equal to in this case we're going to return none and say that there's there's no more sequence for us to produce right there's no sequence here and okay well what's another case well another kind of edge case that we can imagine that's related to this one is well what if we did 5 4 and for simplification purposes of this lesson we're just going to assume that that's also going to return none and so these are going to be the base cases of the sequence function that we're going to write together all right now we need to start thinking about well what's the next simplest case we can imagine okay if it's not 4 4 well you know we i'm not even going to draw our number line because it's so straightforward the next most simple case is not 4 but 3 4 right or 4 5 i suppose we could have done but let's keep our high at 4 to keep this example consistent so okay if 4 4 is going to return none and that's a base case well what's the next step that you can imagine being the next easiest thing to take on and that's sequence from three to four right and we know what we ultimately want this to produce right we ultimately want this to produce three followed by none right well this the key tip of trying to write a function that can produce a recursive structure is don't worry about what comes after right we're going to leave that problem to the recursive process what your focus is on solving and implementing a recursive process that produces a recursive structure is just figure out what you need to do with the current sub problem and then leave the rest to recursion so in this case what we're hoping to do is say okay we're saying we're going to result in the current value of our low parameter which is 3 followed by whatever the recursive result is of sequence 4 4 right so the next step that we're going to make here or we could have said low plus one which in this case would have been four right and ultimately we know like we've already solved that sub problem before we know that's going to give us none and if if sequence 4 4 results in none then then we've correctly solved this right well what's the next most challenging case we can imagine well you can imagine what sequence of 2 3 right or sorry 2 4. let's let's keep the 4 the same well again our focus is what is the the way that we can solve the front of this problem that we're currently on or the current subproblem and that's going to be 2 right and what's 2 going to be followed by 2 is going to be followed by recursion right and so we're going to recur and say okay the sequence of 3 4 right that's what we want the next what comes after 2 is the result of the sequence of 3 4 which we know having just done that right that's actually going to result in a value of a node whose value is 3 followed by none okay so now that we have a feel for this and these are our recursive cases and i should point out that you know we didn't actually do anything different between these two cases we just did this for illustrative purposes but notice both of them did the exact same thing they said let's solve the problem for the current sub problem and then leave the rest of the problem to recursion all right so this was our our sub problem and this is our recursive step for the rest of the problem right and this is going to be a general technique that we can apply in many different places okay so now that we've got a an overview of how we might do this let's let's take a look in vs code of how we might solve it so we're going to continue on from the node class that we set up in the previous examples and let's go ahead and write a skeleton for this sequence function all right so i'm going to define a function name sequence and the first value here is going to be the low parameter and it's going to be an integer value and the second parameter is the high value that's also an integer parameter and it's going to return and what is it going to return well let's think about this we wanted to return nodes but notice here in our base cases we ultimately need to be able to return none so if we're either going to return a node or none we need this to be an optional node return value type right so let's take a look at that so this will return an optional node okay and what was our base case well our base case was uh when the low parameter right so if we think about this is our low parameter and our high perimeter when our low is uh equal to or greater than or greater than or equal to is the way we like to think about this when we're programming if our low parameter is greater than or equal to hi then what we're going to do is we're going to return none right this is our base case and i should have added a doc comment here for this to be a good skeleton function and another extra line there okay so our documentation here is return sequence of nodes between low and high not inclusive of high all right okay so we've returned none in our base case and now we have our recursive case right and we're going to break this recursive case down into a few important steps ultimately we could simplify these into one single line of code when we're done and we'll take a look at that but i'm going to encourage you before worrying about conciseness to worry about clarity first and so for clarity purposes we're going to say what is our sub problem right so our sub problem is what is the integer of the current node that we're working on that we're trying to produce right so the sub problem that we're trying to work on here is low right so that's the the current value of our low parameter and if we want to remind ourselves why this might be okay uh so in the case where our base cases are handled so we know that our low parameter has to be less than or high parameters so let's imagine this simple case where three is three and four our sub problem is thinking about what's the thing that we need to do to solve just this one step of the problem right and we're thinking about the number three here because we're using that low parameter in this instance to be the the current solution to the current subproblem we're working on okay well now we need to think about what's the recursive step for the rest of the problem and that's going to be sequence where we take our current low which was 3 and add 1 to it right so um i'm going to set up one more variable here that's thinking about the rest of the problem and this is going to be an optional node right because it might be empty it might be the empty list in this case if we think about just the very first time we call this worth three and four when we make this recursive call to sex so sec plus uh is low plus one for our first argument and high for the second we're going to keep high the same all right so we solve our sub problem and in this case it's a very simple we're not actually doing much processing we're just saying all right this is our counter low is our counter parameter and then for the rest of the problem we are going to leave that to and hand it off to recursion and let recursion take the wheel right so here we're being sure that we're changing something about our arguments to ensure that we're moving closer and closer to our base case right so we're increasing our low parameter by one ultimately it's going to become greater than or equal to high at some point right okay so we've done that and now how do we form our return value so our return value is going to be a node right we want to produce a node where what is the value inside of our node well that's the solution to our sub problem and what is the next node in our list it's going to be the rest of the list right and so here we're recurring and we're saying okay go solve the next sub problem go solve the next sub problem until you reach the base case and if we were to trace through this with an environment diagram and we were look at okay once we reach our base case we know that we were many frames deep into this recursive problem and as we start returning our way out our list starts becoming built up where each time we return we're returning a node who's connected to the rest of the list that came after it all right we'll try illustrating that in just a second let's go ahead and convince ourselves that this is actually going to work so i set up python and from exercises.exe dot linked list i'm going to import everything right and oops i spelled something wrong i forgot a d okay and now what we can do is try sequence from let's try the simple case four to five right and notice uh we have four to none and actually if we want to carry the same example we were using we were using three to four and i have an extra parenthesis there three followed by none that seems correct well are we actually doing this correctly for uh a longer list two three none that seems like it's working right so what about zero to four each time we solve one sub-problem we go and we figure out what's the rest of the list as a recursive step in the process all right so if we were to try and think about how to i'm going to clear this part of my screen out really quickly what do the sequence of steps look like to get us from where we started to where we ended up and all the way returned back from the first call to sequence so let's imagine a call like let me switch colors here it's a little hard to read let's imagine a sequence call that's something to the effect of 2 4 right what is sequence of 2 4 going to do well we're not going to hit the base case here right sequence of 2 4 is going to result in low being 2 right and the next part of that being sequence of low plus 1 which would be 3 4 right and so okay well now we need to go figure out what is a sequence of 3 4. that is going to be it's not the base case right so our sub problem is that's going to be 3 and that's going to be followed by the sequence of 4 4. all right and uh so when we get to the sequence of 4 4 what's that going to be well that actually is our base case right so that's where we are going to hit low greater than equal to high and that's going to be none right so once we uh know what one of these values is in our uh once we've hit a base case we start returning that right so sequence of 4 4 is actually none okay well what does that mean if uh sequence of uh 4 4 is actually none that means sequence of 3 4 is going to return a node where we're taking our sub problem right and we're connecting it to the rest which was uh of of this list right so now sequence of 3 4 just evaluated to you know this list right so when we get back to the frame where we're trying to figure out what is sequence of 2 4 well sub problem is going to be 2 right and rest is going to be 3 followed by none so this would be when we create the node it's going to be 2 3 and then none right and i would encourage you to try tracing this process out in a recursive environment diagram frame by frame if if that sort of intuitive high level explanation doesn't quite make sense the key idea as is one more brief illustration is if we imagine okay so 2 4 and then 3 4 and then 4 4. right if we think about what is the the the end of this when we actually return none here so this is none so that call returns none right and when we are at 3 4 we're saying we're going to return a node where we're saying 3 and the rest was what came before it and that's going to be returned back to you know the problem where we're saying okay 2 is going to be connected to what came before it because of the way that we are structuring this uh this this return value more generally what we're saying is when building a list recursively construct a new list where the current sub-problem is followed by the rest of the problem processed recursively right and i mentioned that we could rewrite this to simplify it just a little bit right so notice that these two lines i might even just comment them out so comment comment we're returning the current sub problem this the current solution to our subproblem which in this case we're just counting up right so low is always the current solution to the sub problem of counting up because each time we make our recursive step we're going to increase that parameter followed by sequence of low plus 1 and high right so we actually could have written those two lines above it as a single return statement where we're constructing a new node where the current solution to our subproblem is followed by the rest of the problem processed recursively right this being said i think when you're getting used to thinking in this way setting up some explicit variables like we did to begin with is probably more helpful than trying to be terse right and trying to make your force yourself to think about okay what is what is my current sub problem and how do i know whether what what to do next all right so this was a quick look at constructing recursive structures using recursion and this strategy of process the first thing and then construct a new node and a new list where that's attached to the front of whatever comes after that process recursively will ultimately bring you down to a base case and build up a list or a recursive structure programmatically and you could do this with trees and other data structures as well

Channel: Kris Jordan

Views: 2,228

Keywords:

Id: eLxg0RMZ8K8

Length: 16min 58sec (1018 seconds)

Published: Thu Nov 12 2020