943,733 Members | Top Members by Rank

Ad:
  • Java Discussion Thread
  • Marked Solved
  • Views: 622
  • Java RSS
Dec 3rd, 2008
0

Recursion Problem

Expand Post »
	public static boolean member(Integer obj,SimpleList<Integer> l);
	// returns true if obj is a member of l, false otherwise
	{
	
	}

the question is how could I use recursion to show that there is a member of a list?

I thought that maybe
if (l.isEmpty())
{return false}
else
?

thanks
Similar Threads
Reputation Points: 10
Solved Threads: 1
Newbie Poster
VirusTalker is offline Offline
6 posts
since Nov 2007
Dec 3rd, 2008
0

Re: Recursion Problem

Could you detail a bit more.
Last edited by verruckt24; Dec 3rd, 2008 at 12:20 pm.
Reputation Points: 485
Solved Threads: 89
Posting Shark
verruckt24 is offline Offline
944 posts
since Nov 2008
Dec 3rd, 2008
0

Re: Recursion Problem

Click to Expand / Collapse  Quote originally posted by verruckt24 ...
Could you detail a bit more.
Basically I have objects in the SimpleList Routines. I need to manipulate them using recursion. Here is the code for SimpleList

public class SimpleList<E> {
    private ListNode<E> list;
    /**
      Constructs an empty list.
     */
    public SimpleList(){
        list = null;
    }
    /**
      Constructs a single-item list containing x.
     */
    public SimpleList(E x) {
        list = new ListNode<E>(x,null);
    }
    /**
      Constructs a list with head x and tail l.
    */
    public SimpleList(E x, SimpleList<E> l) {
        list = new ListNode<E>(x, copyNodes(l.list));
    }
    /**
      Constructs a list containing node n. Used to create a
      SimpleList from a list of ListNodes.
     */
    public SimpleList(ListNode<E> n) {
        list = copyNodes(n);
    }
    /**
      Used to extract the head of a list.
      @throws Exceptions.ItemNotFound if the list is empty
      @return the head of the list
    */
    public E head() throws ItemNotFound { 
        if (isEmpty())
            throw new ItemNotFound("empty list");
        return list.element;
    }
    /**
      Used to extract the tail of a list. 
      @throws Exceptions.ItemNotFound if the list is empty.
      @return the tail of the list
    */
    public SimpleList<E> tail() throws ItemNotFound {
        if (isEmpty())
            throw new ItemNotFound("empty list");
        else 
            // note that the list copy is in 
            // the constructor
            return new SimpleList<E>(list.next);
    }
    private ListNode<E> copyNodes(ListNode<E> l) {
        if (l == null)
            return null;
        else 
            return new ListNode<E>(l.element, copyNodes(l.next));
    }
    /**
     * Test if the list is logically empty.
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty(){ return list == null; }
    /**
     * Make the list logically empty.
     */
    public void makeEmpty() { list = null; }
    /**
      @return A String representation of the list
     */
    public String toString() {
        String s = "[";
        try{
            if (!this.isEmpty())
                s += getString(this.head()) +
                    this.tail().toString_Nodes();
        } catch (ItemNotFound e) {};
        return s + "]";
    }
    private String toString_Nodes(){
        String s = "";
        try{
            if (!this.isEmpty())
                s += "," + getString(this.head()) + 
                    this.tail().toString_Nodes();
        } catch (ItemNotFound e) {};
        return s;
    }
    private String getString(Object obj) {
        return (obj == null ? "null" : obj.toString());
    }
    //=============================================
     private class ListNode<E> {

        E element;
        ListNode<E> next;

        ListNode( E theElement ) {
            this( theElement, null );
        }

        ListNode( E theElement, ListNode<E> n ) {
            element = theElement;
            next    = n;
        }
    }

}

///////////////////////////////////////////////

class ItemNotFound extends RuntimeException {

    public ItemNotFound( String message ) {
        super( message );
    }

}
What I have so far is:
	public static boolean member(Integer obj,SimpleList<Integer> l);
	// returns true if obj is a member of l, false otherwise
	{
		if(l.isEmpty());
			return false;
		else ()
	}
I figured since if the list is empty then it would not have obj as a member. However Im having a hard time trying to understand the logic of this and how to use it in recursion.
Last edited by VirusTalker; Dec 3rd, 2008 at 7:43 pm.
Reputation Points: 10
Solved Threads: 1
Newbie Poster
VirusTalker is offline Offline
6 posts
since Nov 2007
Dec 3rd, 2008
0

Re: Recursion Problem

Generally when you are doing recursion on any kind of collection of items (lists, arrays, even strings) you want to solve the problem for the first element of the collection, then recurse on the remaining part of the collection.

For this example you can look at the first element of the list, check if that is the object you are looking for. If it is, then you are done. If it's not, you recurse on the rest of the list (without that first element).

Now, because your function is only taking the list and search object as a parameter, you have no way of sending a portion of a list to recurse on. What you will have to do is create a second recursive function (often called the auxiliary recursive function) that takes an additional parameter of the location in the list to start searching from. When someone calls your original function, you just call the auxiliary function with the location as 0.

Try coding that up and if you have problems, post both functions.
Reputation Points: 33
Solved Threads: 18
Junior Poster in Training
mahlerfive is offline Offline
77 posts
since Aug 2008
Dec 4th, 2008
0

Re: Recursion Problem

That really helped my thought process. I figured it out! lol took me a while but i finally got what you where saying. I did it with a try catch block and it worked out perfectly. Thanks again!
Reputation Points: 10
Solved Threads: 1
Newbie Poster
VirusTalker is offline Offline
6 posts
since Nov 2007

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Java Forum Timeline: help with login applet.
Next Thread in Java Forum Timeline: ReplaceAll Method





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC