List Functions - problems with recursion

Need some advice regarding how to tackle recursion

Page 1 of 1

5 Replies - 1232 Views - Last Post: 03 April 2010 - 02:54 PM Rate Topic: -----

#1 Guest_Roger*


Reputation:

List Functions - problems with recursion

Posted 02 April 2010 - 05:42 PM

Hi all,

Ive been having a problem for the past few days..as ive got an assignment set making a list with methods such as reverse,append and length.

Im having issues with a method im trying to create which is insert, inserting into a sorted list.


Main class

class week8_easy
{     //method i am having problems with to work recursively.
	static seblist <String> insert (String x, seblist <String> m) {
		// Initiate following variables so we do not get a non-destructive method
		seblist <String> a=m;
		seblist <String> b=null;
		//insert and sort checking first characters of string using index 0
		String s=x;	
			if(s.charAt(0)> a.head().charAt(0)){			
				//b = new sebcons(m.head().toString()+","+s,a.tail());	
		}
			else {
				
				//b = new sebcons(s+","+a.head().toString(),a.tail());
				
			}	
			int aa=0;

			for(int i=1;i<a.length()-1;i++){
				
				if(x.charAt(0)>m.tail().elementAt(i).toString().charAt(0)){
	                      insert(b.head().toString(),B)/>; 
				}
			}
		
		return b;
	}

//	static seblist <String> sort (seblist <String> m){}

	public static void main (String []args)
	{
	
		seblist <String> m= new sebcons("hello",new sebcons("goodbye",new sebnil()));	
		seblist <String> n= new sebcons("hesdfllo",new sebcons("gooasdfye",new sebnil()));	
		System.out.println("reverse of " +m+" is");
		System.out.println(m.reverse());
		System.out.println(m.length());
		System.out.println(insert("pple",m));

		

		  
	}



}





Heres the following classes if needed.

public class sebcons <T> extends seblist <T>
{
	public T h;
	seblist <T> t;

	public sebcons(T o1, seblist m1)
	{h=o1;t=m1;}

        public boolean isnil()
        {return false;}

		public String commasBetween()
        { if (t.isnil()) return h.toString();
          else return h.toString() +","+ t.commasBetween();}
	 
	public int length()
	{	return 1+t.length();}        
	
	public  T head()
	{
	       return h;
	 }
	
	public seblist <T> tail()        
	{
	       return t;
	 }
	
	public T  elementAt(int n)        
	{
	  if (n==0) return h;
	  else return t.elementAt(n-1);
	}
	
	public seblist <T>  append(seblist <T> m)        
	{
		return new sebcons(h,t.append(m));
	}
	public seblist <T>  reverse()        
	{
		return t.reverse().append(new sebcons(h,new sebnil()));
	}




	
       
}




public abstract class seblist <T>  
{
        public  abstract boolean isnil();
	
	public String toString()
	{
	  return "[" + commasBetween() + "]";
	
	}
  	 
	public abstract int length();        
	
	public abstract T head();        
	
	public abstract seblist <T> tail();        
	
	public abstract T  elementAt(int n);        
	
	public abstract seblist <T>  append(seblist <T> m);        
	
	public abstract seblist <T>  reverse();  
	

	
	public abstract String commasBetween();
	
         	

}



public class sebnil <T> extends seblist <T>
{
       

	public boolean isnil()
        {return true;
	}

	 
	public String commasBetween()
        { return "";}
	 
        public int length()
	{	return 0;}        
	
	public  T head()
	{
	 throw new IllegalArgumentException("Can't do head of empty list");
	}
	
	public seblist <T> tail()        
	{
	 throw new IllegalArgumentException("Can't do tail of empty list");
	
	}
	public T  elementAt(int n)        
	{
	 throw new IllegalArgumentException("Empty list has no elements");
		
	}
	
	public seblist <T>  append(seblist <T> m)        
	{
		return m;
	}
	public seblist <T>  reverse()        
	{
		return new sebnil();
	}

	

}




Any help would be appreciated. thanks.

Is This A Good Question/Topic? 0

Replies To: List Functions - problems with recursion

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10695
  • View blog
  • Posts: 39,790
  • Joined: 27-December 08

Re: List Functions - problems with recursion

Posted 02 April 2010 - 06:03 PM

It looks like you are trying to implement a Linked List. For example, below, why do you have an element as your Head, and the abstract class as your tail? You should be using Nodes to store your data and point to other Nodes.
public T h; 
seblist <T> t;



Wait, I see what you're doing. You are using the sebcons class to store your data, then point to the rest of the list. Honestly, it would make more sense still to have Nodes only point to a single other Node (or two Nodes if you point to Next and Previous Nodes). This way, you can iterate from Node to Node until you find the place to insert, create a new Node with the elem, and simply jocky some pointers. I talk more about Linked List design in my Linked List Tutorial, if you want to check it out.

Also, in addition to the structure of your program, you need to work on your indentation and spacing conventions as well because it is difficult for us to read your code, and therefore help you debug it. Thanks for helping us help you! :)
Was This Post Helpful? 0
  • +
  • -

#3 Guest_Roger*


Reputation:

Re: List Functions - problems with recursion

Posted 02 April 2010 - 06:24 PM

My apologies regarding the indentation and spacing of the codes, i will make sure i will check it before posting in the future.

My professor whats me to implement this method

static seblist <String> insert (String x, seblist <String> m)

Sorry, if i have repeated myself.

as the coursework set is Defining your own recursive data structures(Lists).

The recursion bit is where things get tricky as i know how to insert into a list but i wouldnt know how to insert into a sorted list which it will have to implement. Checking the head ..getting the index 0 position of the string is easy, therefore allowing me to insert the string after the head if for example head is "good" and word entered is "super" therefore the list would contain [good,super,tennis,zack], but when it gets to the tail which can be as long as it can..is where things get tricky as i think i would need to recursively check the tail.

I hope ive made things bit clearer.
Was This Post Helpful? 0

#4 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10695
  • View blog
  • Posts: 39,790
  • Joined: 27-December 08

Re: List Functions - problems with recursion

Posted 02 April 2010 - 07:10 PM

Same concept as a Linked List, just use recursion to iterate if that is the requirement. When you find the insertion point, create a new Node with the element. That Node should also point to the Node right of the insertion point, and have the left Node point to it.

Also, something I noticed above in your OP. You should use the compareTo() method to compare Strings (invoke it from the String object), as it returns -1, 0, or 1 based on whether or not the invoking String is <, ==, > than param String object. So there is no need to check each character one at a time in the Strings.
Was This Post Helpful? 0
  • +
  • -

#5 Guest_Roger*


Reputation:

Re: List Functions - problems with recursion

Posted 03 April 2010 - 01:25 PM

Hi, i've managed to get it nearly working, been working on it for the past hour or so..but 1 problem i am getting is due to the last node

Thanks for the advice macosxnerd101 about using the compareTo method!

For example i have these words in my list.

[apple,bear,plate]

when i insert for example "mobile" it works and inserts it in order

[apple,bear,mobile,plate]

its just on the last node that an exception occurs if i enter a word such as window. It causes this exception..

Exception in thread "main" java.lang.IllegalArgumentException: Can't do head of empty list
at sebnil.head(sebnil.java:18)

I am so close to getting this work, just need some advice regarding this issue.

class week8_easy
{
	static seblist <String> insert (String x, seblist <String> m) {

		if(x.equals("")){
			//if empty..return an empty list
			return new sebnil();

		}
		
		else if(x.compareTo(m.head())<0){

			String h=m.head();
			String t=m.tail().toString();
			return new sebcons(x,new sebcons(h,new sebcons(t.substring(1, t.length()-1),new sebnil())));
		}

		else{
			return new sebcons(m.head(),insert(x,m.tail()));
		}
	}

	public static void main (String []args)
	{

		seblist <String> m= new sebcons("apple",new sebcons("bear",new sebcons("plate",new sebnil())));	
		System.out.println("reverse of " +m+" is");
		System.out.println(m.reverse());
		System.out.println(m.length());
		System.out.println(insert("window",m));

	}

}


Was This Post Helpful? 0

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10695
  • View blog
  • Posts: 39,790
  • Joined: 27-December 08

Re: List Functions - problems with recursion

Posted 03 April 2010 - 02:54 PM

Look at your sebnil class. Your head(), tail(), and elementAt() methods all throw IllegalArgumentsExceptions. Why do you need the sebnil class at all? If you don't have an element to insert (String trim().length() == 0), just return the seblist that was passed to the method.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1