| | |
Recursion Problem
Thread Solved
![]() |
•
•
Join Date: Nov 2007
Posts: 6
Reputation:
Solved Threads: 1
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
•
•
Join Date: Nov 2007
Posts: 6
Reputation:
Solved Threads: 1
Basically I have objects in the SimpleList Routines. I need to manipulate them using recursion. Here is the code for SimpleList
What I have so far is:
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.
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 );
}
} 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 ()
} Last edited by VirusTalker; Dec 3rd, 2008 at 7:43 pm.
•
•
Join Date: Aug 2008
Posts: 77
Reputation:
Solved Threads: 16
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.
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.
![]() |
Similar Threads
- Recursion help....PLEASE!!! (C++)
- Recursion Problem (Java)
- help with recursion (C++)
- recursion problem... (Java)
- how do you reverse a linked list using recursion and return it as a string? (Java)
- recursion problem (C)
- help with recursion (C)
- C++ Beginner - #include recursion problem (C++)
- Need help with recursion and arrays (C++)
- Recursion (C)
Other Threads in the Java Forum
- Previous Thread: help with login applet.
- Next Thread: ReplaceAll Method
| Thread Tools | Search this Thread |
6 @param actuate affinetransform android api applet application arc array automation balls binary bluetooth bold business c++ class client code codesnippet collections color compare component coordinates count database defaultmethod detection doctype dragging ebook eclipse educational error file fractal froglogic game givemetehcodez graphics gui guitesting helpwithhomework html ide ideas image ingres intersect invokingapacheantprogrammatically j2me java java.xls javaexcel javaprojects jni jpanel jtextarea julia keytool keyword linux list map method methods mobile mysql netbeans nextline object parameter php pong problem producer program project projectideas recursive replaysolutions rim scanner sell server set size sms sql sun swing swt terminal threads tree web websites windows





