x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 242

Developing a pure recursive algorithm to return the reverse of a singly linked list ..

Can anyone help me develop this algorithm?
We are not allowed to use ANY assignment statements ..
The methods that we have at our disposal are:

first(list): returns the data value of the first element in 'list'

rest(list): returns a pointer to the second element in 'list'

isMember(object, list): determines if object is in the list .. returns true or false ..

deleteFirst(object,list): returns the same list but with the first instance of 'object' in the list omitted ..
deleteAll(object,list): returns the same list but with all instances of 'object' in the list omitted ..
0
eskimon
• 19
• 9
• 6
• +1
1 Solution

Commented:
We don't do people's homework here, sorry. Or is this an olympiad question?
0

Author Commented:
Sorry I was told that you guys could (in theory) help with snibbits of homework code ..
My apologies ..
0

Commented:
hard one .. hmmm ...
0

Commented:
We would help if you tried to solve your problem/assignment and came across some specific question/problem/bug. The question you posted sounds like the whole assignment, or at least an integral part of it.
0

Commented:
we can help you. but we won't write it for yourself (at least - not me and Sasha_Mapa)
0

Author Commented:
If this were the only part of the assignment I wouldn't be here .. This is the 10th out out of 15 recursive methods we have to develop, and unfortunately methods 11-15 need to be able to use this reverse() method in order to work ..
0

Author Commented:
Sorry I should have posted the other methods:

isNull(list): determines if list is null .. returns true for null and false for non-null ..

append(list1, list2): returns the list formed by adding list2 to the end of list1 ..

add(object, list): adds 'object' at the beginning of 'list', and then returns the new list ..

equal(object1,object2): determines if 2 objects are equal .. returns true for equal and false for not equal ..
0

Author Commented:
Sorry I should have posted the other methods:

isNull(list): determines if list is null .. returns true for null and false for non-null ..

append(list1, list2): returns the list formed by adding list2 to the end of list1 ..

add(object, list): adds 'object' at the beginning of 'list', and then returns the new list ..

equal(object1,object2): determines if 2 objects are equal .. returns true for equal and false for not equal ..
0

Commented:
As I said, if you have some specific question/problem/bug, ask about it...
0

Commented:
I didn't read the whole question (in fact it's not a good idea to put the Question as a Title)

it seems to me that you need just an idea - so here is mine

rev (List original, List reverse)
{
if (isNull(original))
return reverse;
else
}

use it as

List reverse = rev(original, new List()); // or whatever you use to create ampty List

btw. is this a java question ?
0

Author Commented:
Basically the approach I am trying to take is this:

reverse(list){
take the last element of the list and place it at the beginning of a new list, and then append the new list to the old list, but without the last element
call reverse() on the new list
}

But I am having trouble translating this into code
0

Commented:
what a discussion :)

so - what about my code (btw. what's your language - isNull(list) is not good Java design :)
0

Author Commented:
yeah this is a java question .. and unfortunately the reverse() method is only allowed one parameter ..

the method is not inherently difficult .. it's the restrictions that they place on us that make it difficult ..

0

Author Commented:
isNull(list) is actually one of the methods we are instructed to use .. I agree it's goofy to use it ..
0

Author Commented:
isNull(list) is actually one of the methods we are instructed to use .. I agree it's goofy to use it ..
0

Commented:
1. what is 'pure recursive' definition
2. if you are allowed to create 2 methods - your problem is solved

List reverse (List original)
{
return rev(original, new List());
}

// standard Prolog technique :)
0

Author Commented:
What I mean by "pure recursion" is that we are not allowed to use any assignment statements .. ie, all problems have to be solved using recursion and recursion alone .. no 'helper variables' like counters or anything of that sort are allowed ..

Also we are not allowed to use the 'new' operator anywhere in the code except in the add() method .. :(
0

Commented:
well - this code is ugly (don't like the append & add stuff) - but it seems to be working

I think that I can clear it ...

reverse(List list)
{
if (isNull(list))
return new List()
else
{
}
}
0

Author Commented:
hey hey, i think we have a heyhey winner .. :)

It's not pretty by any means, but functional:

public static List reverse(List list){
if (isNull(list))
else{
}
}

I hope this formats properly when I post it .. :)
0

Author Commented:
/me sets mode +genius heyhey
0

Commented:
List Rev(List l)
{
return Rec( Rest(l), First(l) );
}

List Rec( List l, Element e )
{
if ( IsNull(l) )
{
return new List(e);
}
else
{
List L = Rec(Rest(l), First(l));
return Append(L,e)
}
}

That's the solution
Ovidiu Craciun
0

Commented:
> /me sets mode +genius heyhey

thanks

btw. I still don't like the append/add stuff
0

Author Commented:
:)
0

Commented:
LOL! Some people have the nerve to post an answer after seeing such a thread?? I'm shocked and surprised!
0

Author Commented:
heyhey, I don't care for the append/add stuff either .. but I think the purpose of the assignment is to get us in the mode of recursion, even when it makes the problem harder and messier to solve ..

0

Author Commented:
>LOL! Some people have the nerve to post an answer after seeing such a thread?? I'm shocked and surprised!

Sasha, perhaps heyhey remembers what it's like being in university in the week before finals ..
0

Commented:
I was talking about ovidiucraciun. Also, I can't remember that - I'm just finishing highschool :-)
0

Author Commented:
Oh, ok .. :)
0

Author Commented:
Not to overstay my welcome here, but can someone tell me what the heck I am doing wrong in this method:

public static List dupeRemove(List l){
if(!isMember(first(l),rest(l))){
}
else{
return dupeRemove(rest(l));
}
}

The method is not one of the methods assigned in the project, but it would make my life a lot easier if I could get it to work .. All it is supposed to do is return a list with all duplicate entries of the passed list removed ..

so:
dupeRemove({1,2,2,3,3,4,4,5}) = {1,2,3,4,5}

0

Commented:
Umm, no stopping condition? like if isEmpty(l) return new List()
0

Author Commented:
Ok here's the new code:

public static List dupeRemove(List l){
if(isNull(l)){
}
else if(!isMember(first(l),rest (l))) {
}
else{
return dupeRemove(rest(l));
}
}

When I pass the set {1,2,2,2,5} to the method, I get this:

at List.first(List.java)
at List.isMember(List.java)
at List.dupeRemove(List.java)
at List.dupeRemove(List.java)
at List.dupeRemove(List.java)
at List.dupeRemove(List.java)
at List.dupeRemove(List.java)
at List.main(List.java)

I have about 45 minutes to get this method working .. If I can get it to work, I can easily get 3 of the assigned methods to work .. If not, I am screwed .. ;/
0

Commented:
I don't like that

0

Author Commented:
I don't either, but seeing as that we are now allowed to use 'new', it is the only way I can get my hands on a clean list ..
Do you have a suggestion?
0

Commented:
can you post the whole List.java ?

the Exception is thrown somewhere inside the 'first' method (called from isMember)
0

Author Commented:
sorry I had to turn it in at 10am EST ..
it's a lost cause now ..
tnx anyhow
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.