Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 11 of 11

Thread: Recursion Help

  1. #1
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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
    Last edited by copeg; May 23rd, 2011 at 12:50 PM.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,264
    Thanks
    176
    Thanked 821 Times in 764 Posts
    Blog Entries
    5

    Default Re: Recursion Help

    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.

  3. #3
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,141
    Thanks
    48
    Thanked 2,156 Times in 2,129 Posts

    Default 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.

  4. #4
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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.

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,141
    Thanks
    48
    Thanked 2,156 Times in 2,129 Posts

    Default Re: Recursion Help

    Does making getNodeAt recursive make any other method that calls getNodeAt also recursive?
    No, it would not make other methods recursive.

  6. #6
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Recursion Help

    Well, if I implement getNodeAt recursively, I don't understand how I can implement add(E newEntry) recursively.

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,141
    Thanks
    48
    Thanked 2,156 Times in 2,129 Posts

    Default Re: Recursion Help

    Which of the methods that you are writing are supposed to be recursive?

  8. #8
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Recursion Help

    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();

  9. #9
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,141
    Thanks
    48
    Thanked 2,156 Times in 2,129 Posts

    Default 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.

  10. #10
    Junior Member
    Join Date
    May 2011
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: Recursion Help

    It's an assignment I have for class, they must be implemented recursively.

  11. #11
    Forum old-timer
    Join Date
    Nov 2008
    Location
    Faversham, Kent, UK
    Posts
    471
    My Mood
    Mellow
    Thanks
    4
    Thanked 58 Times in 54 Posts

    Default 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...

Similar Threads

  1. [SOLVED] Recursion help
    By Actinistia in forum Java Theory & Questions
    Replies: 3
    Last Post: March 21st, 2011, 12:26 PM
  2. Recursion
    By javapenguin in forum Algorithms & Recursion
    Replies: 12
    Last Post: October 18th, 2010, 03:42 PM
  3. recursion problem, please help
    By nil in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 18th, 2010, 12:59 PM
  4. Recursion Help
    By vmr in forum Algorithms & Recursion
    Replies: 3
    Last Post: April 1st, 2010, 11:27 PM
  5. Recursion help
    By rhoruns in forum Algorithms & Recursion
    Replies: 4
    Last Post: January 8th, 2010, 10:50 PM