Improve company productivity with a Business Account.Sign Up

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

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
Asked:
eskimon
  • 19
  • 9
  • 6
  • +1
1 Solution
 
Sasha_MapaCommented:
We don't do people's homework here, sorry. Or is this an olympiad question?
0
 
eskimonAuthor Commented:
Sorry I was told that you guys could (in theory) help with snibbits of homework code ..
My apologies ..
0
 
heyhey_Commented:
hard one .. hmmm ...
0
Upgrade your Question Security!

Your question, your audience. Choose who sees your identity—and your question—with question security.

 
Sasha_MapaCommented:
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
 
heyhey_Commented:
we can help you. but we won't write it for yourself (at least - not me and Sasha_Mapa)
0
 
eskimonAuthor 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
 
eskimonAuthor 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
 
eskimonAuthor 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
 
Sasha_MapaCommented:
As I said, if you have some specific question/problem/bug, ask about it...
0
 
heyhey_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
    return append(rest(original), add(first(original), reverse);
}


use it as

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

btw. is this a java question ?
0
 
eskimonAuthor 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
 
heyhey_Commented:
what a discussion :)

so - what about my code (btw. what's your language - isNull(list) is not good Java design :)
0
 
eskimonAuthor 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
 
eskimonAuthor Commented:
isNull(list) is actually one of the methods we are instructed to use .. I agree it's goofy to use it ..
0
 
eskimonAuthor Commented:
isNull(list) is actually one of the methods we are instructed to use .. I agree it's goofy to use it ..
0
 
heyhey_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
 
eskimonAuthor 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
 
heyhey_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
  {
    return append(reverse(rest(list)), add(first(list), new List()));
  }
}
0
 
eskimonAuthor 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))
          return (add(null,null));
    else{
    return deleteAll(null,append   (reverse(rest(list)), add(first(list), add(null,null))));
    }
}


I hope this formats properly when I post it .. :)
0
 
eskimonAuthor Commented:
/me sets mode +genius heyhey
0
 
ovidiucraciunCommented:
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
 
heyhey_Commented:
> /me sets mode +genius heyhey

thanks
what about rejecting answer, increasing the points :) and accepting my comment as answer ? :)

btw. I still don't like the append/add stuff
0
 
eskimonAuthor Commented:
:)
0
 
Sasha_MapaCommented:
LOL! Some people have the nerve to post an answer after seeing such a thread?? I'm shocked and surprised!
0
 
eskimonAuthor 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 ..

tnx for your help
0
 
eskimonAuthor 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
 
Sasha_MapaCommented:
I was talking about ovidiucraciun. Also, I can't remember that - I'm just finishing highschool :-)
0
 
eskimonAuthor Commented:
Oh, ok .. :)
0
 
eskimonAuthor 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))){
          return add(first(l),dupeRemove(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
 
Sasha_MapaCommented:
Umm, no stopping condition? like if isEmpty(l) return new List()
0
 
eskimonAuthor Commented:
Ok here's the new code:

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



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

Exception in thread "main" java.lang.NullPointerException:
        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
 
heyhey_Commented:
I don't like that

> return add(null,null);

0
 
eskimonAuthor 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
 
heyhey_Commented:
can you post the whole List.java ?

the Exception is thrown somewhere inside the 'first' method (called from isMember)
0
 
eskimonAuthor 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.

Join & Write a Comment

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

  • 19
  • 9
  • 6
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now