# Recursion Help

• May 23rd, 2011, 11:09 AM
WeaKeN
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 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:
Code java:

```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```
• May 23rd, 2011, 12:52 PM
copeg
Re: Recursion Help
I recommend taking it one step at a time, and tackle each of those methods.
Quote:

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.
• May 23rd, 2011, 01:17 PM
Norm
Re: Recursion Help
With linked lists I often have to use a piece of paper to show how the links connect the nodes and how to move thru the list, find and add nodes.
• May 23rd, 2011, 04:03 PM
WeaKeN
Re: Recursion Help
I'm working on add(E newEntry) now. It seems like for each of the methods that I need to implement recursively, the private getNodeAt method is doing most of the "hard work." I can make getNodeAt recursive. Does making getNodeAt recursive make any other method that calls getNodeAt also recursive? It seems like if I make getNodeAt recursive, there's nothing really left to make the other ones recursive. Sorry if I didn't get the problem across clearly.
• May 23rd, 2011, 04:06 PM
Norm
Re: Recursion Help
Quote:

Does making getNodeAt recursive make any other method that calls getNodeAt also recursive?
No, it would not make other methods recursive.
• May 23rd, 2011, 04:16 PM
WeaKeN
Re: Recursion Help
Well, if I implement getNodeAt recursively, I don't understand how I can implement add(E newEntry) recursively.
• May 23rd, 2011, 04:44 PM
Norm
Re: Recursion Help
Which of the methods that you are writing are supposed to be recursive?
• May 23rd, 2011, 05:15 PM
WeaKeN
Re: Recursion Help
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();
• May 23rd, 2011, 08:42 PM
Norm
Re: Recursion Help
Why do you want to use recursion for all those methods? It doesn't seem to me to be a good way to do it.
• May 23rd, 2011, 09:48 PM
WeaKeN
Re: Recursion Help
It's an assignment I have for class, they must be implemented recursively.
• May 27th, 2011, 08:17 AM
dlorde
Re: Recursion Help
Surely if you have a method that uses recursion and you call it from the other methods that need that functionality, those methods are (indirectly) using recursion? Otherwise, you're going to end up duplicating the same recursive algorithm in every method, which is, frankly, stupid...