In this lab, you will implement a few recursive routines that manipulate linked lists. You have already implemented similar or idential routines iteratively, but this time around you will implement this recursively.
After completing this lab, you should:
You may work with a partner for this lab. If you choose a partner, both members must contribute to the same work. That is, you cannot simply divide the lab in half, as everyone is responsible for all the content. Instead, you should use a pair programming style. In pair programming, one person acts as a driver, who takes control of the keyboard. The other person acts as a navigator, who reviews what the driver writes and offers advice. Oftentimes, the driver is occupied with details of the problem (e.g., variables, control flow, etc.), whereas the navigator is concerned with bigger-picture problems (e.g., functions, design, interactions). This works well for problems which are simply too large to fit into one person's head. If you're unfamiliar with the concept of pair programming, you may wish to watch this video on the topic.
With pair programming, oftentimes it works best if both participants are of approximately the same skill level. Generally, if the disparity in skill is large, the end result is frustrating for both parties - it really only works when both parties operate at approximately the same speed. With this in mind, you should select someone of approximately the same skill level.
countOccurrencesMoreThan-bash-4.2$ cd -bash-4.2$ pwd /cs/student/yourusername -bash-4.2$ cd cs24 -bash-4.2$ pwd /cs/student/yourusername/cs24 -bash-4.2$ mkdir lab7 -bash-4.2$ cd lab7 -bash-4.2$ pwd /cs/student/yourusername/cs24/lab7
Now copy over the files for this week.
They are kept in the directory: /cs/student/kyledewey/cs24/labs/7
-bash-4.2$ cp /cs/student/kyledewey/cs24/labs/7/* .
Note that there is a '.' at the end of that line. cp means copy.
/cs/student/kyledewey/cs24/labs/7/* means all of the files contained
in the directory /cs/student/kyledewey/cs24/labs/7. The '.' means to
copy from that location to the current location.
Now check to make sure the copy worked correctly:
-bash-4.2$ ls
You should see a set of files listed that will be used for this warm-up.
countOccurrencesMoreThan
Last lab, you wrote a recursive function counting the how many numbers
were more than 7 in an array. This lab, you will write a recursive
function counting the number of values greater than the input value m
in a linked list, where m is an integer. I have added the public
method to LinkedList.h and a skeleton to LinkedList.cpp, but you need to
add the private method that will be called for recursion.
First, figure out the base case, smaller case, and general case for this code. That is your best way for understanding what the code should be. In this tutorial, though, I am also going to show you how to look at the iterative code and see how it relates to the recursive code.
Write the base case from your recursive design you just completed.
This will be added to the method countOccurrencesMoreThanRec. I have provided
the iterative (loop-based) version in countOccurrencesMoreThan.
Compare your base case to the terminating condition in the for loop.
Notice that the base case check
is exactly opposite what the check is inside the for loop. The for loop
asks the question of when do I keep looping, whereas the if statement asks
the questions when do I stop. Therefore, they are almost identical questions
- just opposite. Now look at what value you are returning. That value was
also the initialization value for the sum in the iterative version.
Second, you need to call the recursive method to get the result from the
smaller problem. Notice that this call is almost identical to the "update"
step of the for loop. The assignment happens within the function call rather
than with an = sign modifying the same variable.
Finally, write the code that takes the answer from the smaller problem and adjusts it to be your answer. Notice that is very similar to the code in the for loop that updates the sum variable.
Hopefully, at this point, you have not only written code based on your design, but you see that it has a one-to-one correspondence to the iterative code - just with the code in different places.
Compile, test, and you're done! To compile:
-bash-4.2$ g++ main.cpp LinkedList.cpp
removeNextToLastRec
It is more challenging to perform a complex method recursively. You
should look closely at the iterative version for this. Notice that it is
not just one simple loop like the last one. Instead, there are some checks
before we reach the loop. These are additional base cases that are checked
even before the recursive method is called. In this method, we remove the
second to last node and return the value in the node. If the list is empty or has only
one node, return 0 (imperfect - maybe someone put 0 in the list.
This is why exceptions, which you will learn about later, are useful).
Make sure you update the tail pointer.
As always, you should write out your base cases and smaller case.
The first step is to identify the base cases that do not require recursion. You can see these in the original iterative code - they are the checks that happen before the loop. Take those and place them into the public method (that is not recursive). Perform those checks and the related work before you call the recursive method.
Then, only call
the recursive method if you did not encounter one of those error base cases.
Just as before,
the call to the recursive method should start with the value that was used
to initialize the variable in the for loop (typically head).
Now you need to figure out what the base case is for the recursive method.
We do NOT want to go to the end of the list, as we did for the inspection
method. You solve this just like the iterative ones. Draw a before and
after picture, then place a tmp pointer where it needs to go in order to
make the changes. The job of the recursive function is to stop when h points
to that node.
You can then write the if statement that checks for being in that location.
It should be exactly opposite the check inside the for loop in the
iterative version. The for loop's check is the check that makes it keep
going, whereas the recursive if statement is a check to see when it stops.
Once you have figured out when to stop, you need to know what to do when you stop. Write that code. As another check, that code is contained after the loop in this iterative example, possibly with different variable names.
Finally, you need to write the recursive call. Look at the for loop for how it updates the pointer. That will be what you put into the recursive call.
Compile, test, and you're done! To compile:
-bash-4.2$ g++ main.cpp LinkedList.cpp
removeNth
You may have noticed that later in the lab, you will have to implement
removeNth, which can remove an arbitrary item from a list.
With this in mind, removeNextToLast could be implemented
in terms of this. If so desired, you may implement
removeNextToLast in terms of removeNth,
but you must call the recursive version, not the iterative version.
As an aside, it's not recommended to take this approach for implementation;
removeNextToLast is intended to be a simpler form
of removeNth which allows you to work out some of the
details of removeNth before actually tackling
removeNth, so it is much harder to bypass
removeNextToLast entirely and jump to removeNextToLast.
addNthRec
This method inserts a new node at index n in the list. If the
length of the list is <=n, then the new node is inserted at the end of the list.
If the index is smaller than 0, then do nothing.
You should write the iterative version first, fully debugging that before you move on to the recursive version. Then you can tell if any bugs are due to your general design / understanding of the problem or your understanding of recursion. For full credit, you must implement both versions, though the recursive version will be worth more.
If you have trouble, look back at the warmup for more complete explanations of how to attack problems like these. When in doubt, draw it out.
Don't forget to compile and test as you go. Do not implement the entire project and then begin to test it. Compile it once you complete one part, and test it once you have something minimal working.
removeNthRec
This method removes node at index n, shortening the list by one. Don't forget
to delete the node! This also returns the value contained in the node. If
there is no node at index n (n >= list length),
then return 0. If n is less than 0, also do nothing and return 0.
You should write the iterative version first, fully debugging that before you move on to the recursive version. Then you can tell if any bugs are due to your general design / understanding of the problem or your understanding of recursion. For full credit, you must implement both versions, though the recursive version will be worth more.
If you have trouble, look back at the first two parts for more complete explanations of how to attack problems like these. When in doubt, draw it out.
While we have provided some tests in main.cpp, these are
hardly complete. There are a variety of edge cases that we don't cover,
and removeNthRec isn't tested at all. Be sure to test
all your code!
First, fill out the required fields in the provided README.txt file.
Once you have filled this in, you may submit everything with the following command:
-bash-4.2$ turnin lab7@cs24 README.txt LinkedList.cpp LinkedList.h Node.h main.cpp
All content was graciously provided by Professor Diana Franklin, with slight formatting-related adaptation.