Overview

For this assignment, you will use recursion to write some linked list methods. You have to complete all the methods in the Recursion class.

The whole point of this is to give you practice writing recursive methods, so you may not use loops to solve these problems.

Starter code

• Recursion.java
• Tester.java

You can get all these files at once by downloading the file hw03.tar.gz and running tar xzvf hw03.tar.gz

Details

I've written the beginning of a small linked list class Recursion, where each linked list node stores a string. I've included the Node class, as well as methods build and print to help you in debugging and getting started.

You have to complete the implementation of the following methods:

• addSecond(): Adds a new string immediately after the first element in the list. No recursion should be needed for this one.
• printInReverseOrder(): Print out the elements of the list, from last to first. You'll need a helper method.
• longest(): Return (but don't print) the longest string in the list. Helper needed.
• get(int i): Return (not print), the element in the i-th link. Helper needed.
• duplicate(): Make the list twice as long by repeating every element twice.
• remove(String r): Remove any and all occurrences of r in the list. Helper needed.

If you don't remember recursion well, this might take you a while. Please don't wait to start until the night before.

I have made a Tester class with a main method that performs a couple tests, but you should make your own main method to test your solutions as well. I will test on all kinds of weird inputs, and so should you! Like running longest on an empty list, or using an index too large for the list; your program should handle those correctly.

It is not necessary to submit your class with a main method, as I'll use my own for grading; it won't break anything to include it, though. Again keep in mind that I will grade you based on much more than what the Tester class does!