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

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

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

hard one .. hmmm ...

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.

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

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 ..

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 ..

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 ..

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

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 ?

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

what a discussion :)

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

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 ..
 

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

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

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 :)

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 .. :(

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 .. :)

/me sets mode +genius heyhey

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

> /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

:)

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

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

>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 ..

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

Oh, ok .. :)

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}

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

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 .. ;/

I don't like that

> return add(null,null);

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?

can you post the whole List.java ?

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

sorry I had to turn it in at 10am EST ..
it's a lost cause now ..
tnx anyhow