CSC 132 Fall 2000

Lab 7

Due: end of today's lab, 2 November 2000

15 points + 10 bonus points

"Curse and Recurse"

You will need files CharLink.java and LinkDriver.java from the eccentric download folder for Lab 7. CharLink.java implements a singly-linked ordered list of "char" values. LinkDriver.java will exercise this class. CharLink.java contains a complete and correct definition of the CharLink class.

CharLink has one inner class: private class Node.

CharLink has one instance variable: private Node head;

CharLink has six public methods. Their specifications are as follows:

// returns: count of values in the sequence
public int size()

// returns: String representation of all values in correct order
public String toString()

// argument: value to insert
// postcondition: value is the last in the ordered sequence
public void insertRear(char value)

// precondition: sequence is not empty
// postcondition: last value is removed from sequence
// returns: char value which was last in the sequence
public char removeRear()

// postcondition: values are stored in reverse sequence
public void reverse()

// returns: true if sequence is empty and false otherwise
public boolean isEmpty()

These methods are all defined and work correctly. Run the test driver if you are not convinced of this. All are implemented using loops except isEmpty(), which is trivial.

Your assignment is to modify CharLinkList.java, to implement these methods using recursion instead of loops! The basic assignment is to do any three (3) of them for 5 points each. You can earn 5 bonus points by doing a fourth one and 10 bonus points for doing all five (isEmpty doesn't count since it doesn't use loops). My recommendations: size() is the easiest because we did it in class, and insertRear() and toString() are pretty straightforward. removeRear() is a little harder, and reverse() is the hardest, don't tackle it until you've gotten the other four.

To get the bonus for reverse(), it must be recursive and must not call insertRear() or removeRear(). Hint: the recursive partner of reverse will need two parameters (to pass two adjacent nodes), and performs its magic on its way back (i.e. after the recursive call).

1. You cannot define any additional instance variables. You can only use head.
2. The specification of these methods must not be changed. This means you will need to define a private recursive partner method for each one, then have the method call its recursive partner. For method blah, the recursive partner should be called blahRecurse.
3. All methods must work correctly in your submitted program! Before starting work on a method, comment out the original code using "/* and "*/", in case you need to restore it later before submitting.
4. Your score will be based on the number of methods you are successfully able to convert to recursive form. I will determine this by inspecting your submitted source code.
5. Documentation is not required.

Follow this strategy: Since these methods all currently work correctly, I strongly suggest you work on one method at a time! This will help isolate potential errors.

Make life easier! When modifying a method to call its recursive partner, the only part that needs to be modified is the code segment containing the loop! For example, removeRear() has special cases for an empty list (head == null) and a list with only one node (head.next == null). You can leave those alone!

Here is correct output from the driver program.

Submit the modified CharLink.java file to your eccentric upload folder.

[ Assignments | CSC 132 | Peter Sanderson | Computer Science | SMSU ]

Peter Sanderson ( PeteSanderson@smsu.edu )