CSC300: Linked Mutators using Recursion

now that you know how to mutate a linked list let's think about how to do that recursively and some interesting opportunities arise with the extra power of recursion that aren't available with loops let's start by looking at our loop code and reminding ourselves what it does we'll start here at line 12 attempting to insert 31 into the list shown here the test on line 12 will return false because first is not null it's a pointer to a node and first that item is 11 which is not greater than or equal to 31 so control will move to line 15 where a new variable is going to be declared as an alias to the first node so this first will be stored in a new variable called X we then enter our loop while X next is not null and the X next item that's not the item X is pointing to but the next one is smaller than the parameter we'll continue to loop note here that it's very important that we know that X is not null before executing line 19 we've already checked that first is not null we've assigned X to first so we can assume that X is not null at this point since the condition of the while loop is satisfied we'll advance the pointer on line 20 and go back around to check the condition again again X next is not null it's indeed this node with item 41 but in this case the item of X next which is 41 is not less than our prayer therefore we'll exit the loop and go on to line 22 here we create a new node and the constructor will return back to us that new node with item 31 and next pointer referring to X next after the constructor returns we will then update X next so that X next is no longer referring to the node with 41 but instead referring to the new node so this object with 31 is going to get pasted in between and we're done with our loop anything we can do with a loop we can do with a recursive function and so I can mindlessly apply my algorithm for converting loops into helper functions and I'll arrive at the following here's a direct translation of my while loop as a recursive helper function instead of starting the loop I start the helper function the loop has two variables that it mentions these are X and item and therefore these are the two parameters of my helper I'll initialize them appropriately first is the initial value of X and therefore I will pass in first to the helper to kick it off in my loop I was checking the bound repeatedly and advancing X in my recursive function I check the bound once and recur updating X in the recursive call in the base case here once I've finished with my loop I'm going to update X likewise here the base case when I'm finished with my loop I'm going to update X next you can see that this code has two similar looking box the first block in the starter function handles the case that I might insert at the first position in the list and the helper function here handles the case that I might insert somewhere else let's look at examples of both of these cases so suppose I want to insert item 11 into the list that begins with 21 31 41 51 in this case at line 12 the condition will be true first is not null but first item is greater than my parameter and therefore I will execute line 13 calling the constructor to create a new node the constructor will return the new node with item 11 and next pointing to the current value of first so note we're going through this first we're gonna copy that value into the nodes next field then I'm going to update the first variable and so this item is gonna be stitched in between the playground object and node and therefore it becomes the first item on the list now let's look at what happens if I'm inserting a node somewhere further down the list to do this I'm gonna translate the code just slightly to make it look a bit more natural Here I am checking the loop bound and then recurring it's more typical in a recursive function to check for the base case in which case my code looks like this note that with this rewrite the code on line 19 is now almost identical to the code on line 12 the only thing that's different on line 12 I'm checking first and first item on line 19 I'm checking X next an X next item but note that the code is no different from what I had before all I've done is swap the two cases of the condition so I'm replacing the and with an or where both of the two are negated now let's look at an example where I'm attempting to insert 31 into the list with 11 21 41 51 in this case line 12 will be false and therefore will jump to line 15 and start our helper function our helper functions going to be kicked off with X at this first and the item being the same as the parameter that was passed in on line 19 the condition will be false although X next is not null it is the case that X next item is 21 and 21 is not greater than our parameter 31 therefore we'll go to the else branch and execute line 22 this causes a recursive call in the recursive call X is bound to our former X next call number 3 has X set to the node with item 11 the next call number 4 will have X bound to X dot next from the previous so we've advanced X in the recursive call will again check the termination condition in this case again X next is not null it's the item with 41 but in this case X next item 41 is indeed greater than the parameter 31 therefore we'll move to line 20 we'll create a new node with the item 31 and its next pointer is set to the current value of x next so note that X next in this invocation is referring to the object that holds 41 and so we'll set the next field of the new object to refer to the object with value 41 on line 20 then we're going to stitch this item in between so we'll update X next that's the pointer of the object with 21 to refer to the object with 31 so we stitch it in and now it's in place at this point our functions can return note that on return they do nothing this is computing going forward all of the work of this recursion happens going forward and we have a single call in this case it's call number for which both creates a node and then puts it in the correct place so call number four here is really doing all the work everything else is just getting us there this is a non nullable recursion because the parameter X is never allowed to be null in this code note that if we ever called insert H with X equal to null we would get a null pointer exception when we try to access X dot next this recursive function behaves just like a loop it does all of its work going forward and in one iteration of the loop we create a node and put it in its place recursion is more general than looping so it opens up new opportunities that aren't available in loops rather than creating a node and putting in its place in a single call as I'm doing here I can split this work between two invocations of the method I can have my helper function return a node that it's created and then the caller can put the object in its correct place this is what this looks like I have a node being created in my recursive function then that node is returned to the caller there's two ways the helper function may be called first it may be called by the starter method in which case I may be introducing a new first item or it may be it called by the helper method itself in which case I may be updating X dot next let's walk through this in the case that we are actually inserting something at the beginning of the list so if I'm trying to insert xi into this list what's going to happen well we start here at line 15 by immediately calling the helper function note that I haven't done a null check here so it could be null we don't know but in this case X is pointing to a node with item 21 that's larger than my parameter item therefore the condition is true and will execute line 20 line 20 calls the constructor which will return a new node with item equal to the parameter and with a next pointer equal to X whatever that happens to be so X here is a pointer to the node 21 therefore the next for this new node will point to the node with item 21 then after finishing the creation we don't immediately put this in its place note we're going to return back to the calling function on line 15 we'll then take the return value we've been given that's this new node and we'll actually put it to be the new first so note that when I update this first I'm going to update it so that 11 now or the node with 11 is the new first and note that that's going to be fine it's going to get my list in the right order there we are backing up to the where the helper function returned we can see the helper function here as returned the item and we're about to put that in place there are two separate function calls involved in this creation the sender actually creates the new note that was call number 3 in this case and the receiver puts it in place that's call number 2 note that the receiver is not necessarily always from the same method in this case the receiver is actually the starter function but as we'll see in our next example the receiver might also be a call to the helper function itself let's look at what happens when we try to put 31 into the list with 11 21 etc in this case again we're immediately going to start our helper function on line 19 we'll check whether X is null that's false we also check if the item referenced by X that's in this case 11 is greater than or equal to the parameter you'll see here that's false and so we'll go to line 22 line 22 is going to do a recursive call when we do the recursive call the value of x here in call number 4 is going to be the item 22 note that the value of x in call 3 was the node with item 11 in call number 4 will again check for the nobody of x and do a comparison and you'll see here that what we're comparing to is not X next item we're looking at X itself we're comparing 31 to X item which is 21 and the comparison fails so we'll go on and do yet another recursive call in call number 5 X is pointing to the node with item 41 and in this case the comparison on line 19 is going to succeed and we will go ahead and execute line 20 because at this point the item we're looking at is actually greater or equal to the item that we have as a parameter and so we'll create that new node and the new node is going to have the item parameter 31 and the current value of X note note again that I'm not looking at X next I'm looking at the current value of x this new node is then returned back to the previous call this is something I can't do in a loop but it's very easy to do in a recursive function here call number 5 is going to return back to call number 4 and what call number 4 is going to do is to stitch that item in place once we've got the item in place now our functions can all return note however there is a wrinkle our functions called the helper without knowing whether or not a new object would be created and therefore it's necessary to copy references as we go back it's important that this function actually returns something back to its caller so on line 23 call number 4 will return its value of X back to the caller this is a way of calling number four saying to call number 3 hey nothing changed keep me in my place in this case we're sending the same node back to the receiver that the receiver had in the first place so that receiver had as X next this node with item 21 and we're simply going to pass that same node back so what happens here is line 22 doesn't actually do anything likewise when we go back to the original starter function will tell the starter function what's the value of first because it might have changed in this case it didn't so we'll simply pass back the old value of first but the starter function doesn't know what it's getting and it will simply put that in place in this case again this line has no effect this style of coding is very powerful and very general and as you can see it allows me to avoid a lot of duplication that I had in my non nullable version of the code it's worth studying the differences between these two styles first note that the function calls themselves haven't really changed that much on line 15 I'm calling insert on first and I'm doing the same thing here the only difference is that I'm storing the resulting value as well so in the non nullable version my helper function just returns nothing in the nullable version my helper function is returning a note and I need to store that back the same thing is true for the recursive call in the helper the recursive call and the helper looks pretty much the same the arguments haven't changed the only difference is that I'm going to save back the result that I'm given in addition I need to return the current state back to my caller so that my caller can update their node on line 22 when they get there the main change then is at line 19 you can see in the nullable version I'm of course checking whether or not X is null whereas in the non knowable version I'm checking whether X dot next is null similarly in the nullable version I'm looking at X dot item whereas in the non nullable version I'm looking 1 ahead you can see this entire non nullable recursive code is always looking one step ahead and this is because of the basic structure of a linked list you have pointers going forward but in this case there's no pointers going back so you need to wait back so that you can modify the previous pointer when you get to the node you need there's no need to wait back in the knowable version I simply am going to barrel forward and then at the point that I need to create something I'll return that back to the caller in this pattern I'm actually going backwards not using a back reference in the list but using a recursion I'm able to send data back to the caller who's at the previous node in the list whenever there's more than one way to do something it's important to know which one you're using a very common error for beginning programmers is to loop on the nullity of X rather than the nullity of X dot next that's true both in the non nillable recursion and in the looping version very common for students to look at X and X item rather than looking at X next and X next item it's important to know when you're going through a link structure that you need to hang back one link in order to update what's in front of you once you understand the knowable recursion pattern it's actually the easiest of these to write because it has the least amount of code but there's common mistakes here as well the most common mistakes have to do with updating links for example forgetting to update first as the result in the starter function forgetting to update X next with the result in the helper function forgetting to return X using this pattern to mutate lists is quite powerful and you'll see it again in next quarter when you're looking at balanced trees the main power here lies in the fact that we're doing computation both going forward looking for the place to do something potentially creating the thing when we need it and then we're also doing computation going back in this particular example the computation going back is trivial we may either put something in its place or we're simply copying the links that we had before in the case of balanced search trees which you'll see next quarter the computation going backwards is much more complex because we want to maintain a balanced structure in a tree where we have potentially two children therefore as we go back up the tree we may need to change the structure going backwards by mastering this pattern now you'll be well prepared for dealing with balanced tree algorithms next quarter