Thread: Recursion Help

Hello,

I'm just learning about recursion and I need some help. I am given a class RLList (a Linked List) and told to re-implement these methods:

public void add(E newEntry);
public boolean add(int newPosition, E newEntry);
public E remove(E item);
public E remove(int position);
public boolean replace(int givenPosition, E newEntry);
public E getEntry(int givenPosition);
public boolean contains(E anEntry);
public void reverse();
public String toString();

If someone could show me how to do a couple of these and give a little explanation on how you implemented the recursion, that would really help.

Below is the RLList code:

public class RLList<E> implements ListInterface<E>{
    private Node<E> firstNode; // reference to first node
    private int  length;    // number of entries in list
 
    public RLList(){
       clear();
    } // end default constructor
 
 
 
    public final void clear(){      //any function called in a constructor must be declared final
       firstNode = null;
       length = 0;
    } // end clear
 
 
 
  private class Node<E>{    // private inner class
    private E data;         // data portion
    private Node<E>   next; // link to next node
 
    private Node(E dataPortion){
       data = dataPortion;
       next = null;
    } // end constructor
 
 
 
    private Node(E dataPortion, Node<E> nextNode){
       data = dataPortion;
       next = nextNode;
    } // end constructor
  } // end Node
 
 
 
  public void add(E newEntry){
    Node<E> newNode = new Node<E>(newEntry);
 
    if (isEmpty())
       firstNode = newNode;
    else{                   // add to end of nonempty list
       Node lastNode = getNodeAt(length);
       lastNode.next = newNode; // make last node reference new node
    } // end if
    length++;
  }  // end add
 
 
 
 
 
    public boolean add(int newPosition, E newEntry){
       boolean isSuccessful = true;
 
       if ((newPosition >= 1) && (newPosition <= length+1)){
          Node<E> newNode = new Node<E>(newEntry);
 
          if (isEmpty() || (newPosition == 1)){ // case 1
                newNode.next = firstNode;
                firstNode = newNode;
          }
          else{            // case 2: newPosition > 1, list is not empty
             Node<E> nodeBefore = getNodeAt(newPosition-1);
             Node<E> nodeAfter = nodeBefore.next;
             newNode.next = nodeAfter;
             nodeBefore.next = newNode;
          } // end if
 
          length++;
       }
       else
          isSuccessful = false;
 
       return isSuccessful;
    } // end add
 
 
 
    public E remove(int givenPosition){
       E result = null;             // return value
 
       if (!isEmpty() && (givenPosition >= 1) && (givenPosition <= length)){
          if (givenPosition == 1){        // case 1: remove first entry
             result = firstNode.data;     // save entry to be removed
             firstNode = firstNode.next;
          }
          else{                           // case 2: givenPosition > 1
             Node<E> nodeBefore = getNodeAt(givenPosition-1);
             Node<E> nodeToRemove = nodeBefore.next;
             Node<E> nodeAfter = nodeToRemove.next;
             nodeBefore.next = nodeAfter; // disconnect the node to be removed
             result = nodeToRemove.data;  // save entry to be removed
          }  // end if
 
          length--;
        } // end if
 
        return result;                    // return removed entry, or null
                                    // if operation fails
     }  // end remove
 
     public E remove(E item){
		 return item;
	 }
 
 
     public boolean replace(int givenPosition, E newEntry){
        boolean isSuccessful = true;
 
        if (!isEmpty() && (givenPosition >= 1) && (givenPosition <= length)){
           Node<E> desiredNode = getNodeAt(givenPosition);
           desiredNode.data = newEntry;
        }
        else
           isSuccessful = false;
 
        return isSuccessful;
     } // end replace
 
 
     public E getEntry(int givenPosition){
        E result = null;  // result to return
 
        if (!isEmpty() && (givenPosition >= 1) && (givenPosition <= length))
            result = getNodeAt(givenPosition).data;
 
        return result;
     } // end getEntry
 
 
 
 
     public boolean contains(E anEntry){
        boolean found = false;
        Node<E> currentNode = firstNode;
        while (!found && (currentNode != null)){
           if (anEntry.equals(currentNode.data))
              found = true;
           else
              currentNode = currentNode.next;
        } // end while
 
        return found;
     } // end contains
 
     public void reverse(){
	 }
 
 
     /** Task: Determines whether the list is empty.
      *  @return true if the list is empty, or false if not */
     public boolean isEmpty(){
        return (firstNode == null);
     }
 
 
     /** Task: Displays all entries that are in the list, one per
      *        line, in the order in which they occur in the list. */
     public void display(){
        Node<E> currentNode = firstNode;
        System.out.print("[");
        while(currentNode != null){
           System.out.print(currentNode.data + " ");
           currentNode = currentNode.next;
        }
 
        System.out.println("]");
     }
 
 
     /** Task: Determines whether the list is full.
      *  @return true if the list is full, or false if not */
     public boolean isFull(){
        return false;
     }
 
 
     /** Task: Gets the length of the list.
      *  @return the integer number of entries currently in the list */
     public int getLength(){
        return length;
     }
 
 
 
 
 /* < Implementations of the public methods add, remove, replace, getEntry, contains,
      getLength, isEmpty, isFull, and display go here. > */
 
 // ---------------private!-----------------------------
 
    /** Task: Returns a reference to the node at a given position.
     *  Precondition: List is not empty; 1 <= givenPosition <= length. */
    private Node<E> getNodeAt(int givenPosition){
	       Node<E> currentNode = firstNode;
 
	       for (int counter = 1; counter < givenPosition; counter++)
	          currentNode = currentNode.next;
 
	       return currentNode;
    } // end getNodeAt
 
 
 
 
} // end LList

I recommend taking it one step at a time, and tackle each of those methods.

If someone could show me how to do a couple of these

We are here to help you through this, but not to do it for you. Like I said, break the problem down and give them a try. If you struggle, post back with a precise question about the problem you are having.