Solved

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

Posted on 2000-04-03
35
232 Views
Last Modified: 2012-08-13
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
Comment
Question by:eskimon
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 19
  • 9
  • 6
  • +1
35 Comments
 
LVL 7

Expert Comment

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

Author Comment

by:eskimon
ID: 2679461
Sorry I was told that you guys could (in theory) help with snibbits of homework code ..
My apologies ..
0
 
LVL 16

Expert Comment

by:heyhey_
ID: 2679472
hard one .. hmmm ...
0
PeopleSoft Has Never Been Easier

PeopleSoft Adoption Made Smooth & Simple!

On-The-Job Training Is made Intuitive & Easy With WalkMe's On-Screen Guidance Tool.  Claim Your Free WalkMe Account Now

 
LVL 7

Expert Comment

by:Sasha_Mapa
ID: 2679474
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
 
LVL 16

Expert Comment

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

Author Comment

by:eskimon
ID: 2679482
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 Comment

by:eskimon
ID: 2679489
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 Comment

by:eskimon
ID: 2679504
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
 
LVL 7

Expert Comment

by:Sasha_Mapa
ID: 2679505
As I said, if you have some specific question/problem/bug, ask about it...
0
 
LVL 16

Expert Comment

by:heyhey_
ID: 2679510
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
 

Author Comment

by:eskimon
ID: 2679512
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
 
LVL 16

Expert Comment

by:heyhey_
ID: 2679519
what a discussion :)

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

Author Comment

by:eskimon
ID: 2679521
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 Comment

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

Author Comment

by:eskimon
ID: 2679527
isNull(list) is actually one of the methods we are instructed to use .. I agree it's goofy to use it ..
0
 
LVL 16

Expert Comment

by:heyhey_
ID: 2679542
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 Comment

by:eskimon
ID: 2679553
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
 
LVL 16

Accepted Solution

by:
heyhey_ earned 50 total points
ID: 2679564
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
 

Author Comment

by:eskimon
ID: 2679595
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
 

Author Comment

by:eskimon
ID: 2679605
/me sets mode +genius heyhey
0
 
LVL 3

Expert Comment

by:ovidiucraciun
ID: 2679623
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
 
LVL 16

Expert Comment

by:heyhey_
ID: 2679632
> /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
 

Author Comment

by:eskimon
ID: 2679651
:)
0
 
LVL 7

Expert Comment

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

Author Comment

by:eskimon
ID: 2679655
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
 

Author Comment

by:eskimon
ID: 2679661
>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
 
LVL 7

Expert Comment

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

Author Comment

by:eskimon
ID: 2679679
Oh, ok .. :)
0
 

Author Comment

by:eskimon
ID: 2679832
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
 
LVL 7

Expert Comment

by:Sasha_Mapa
ID: 2679869
Umm, no stopping condition? like if isEmpty(l) return new List()
0
 

Author Comment

by:eskimon
ID: 2679896
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
 
LVL 16

Expert Comment

by:heyhey_
ID: 2680022
I don't like that

> return add(null,null);

0
 

Author Comment

by:eskimon
ID: 2680057
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
 
LVL 16

Expert Comment

by:heyhey_
ID: 2680240
can you post the whole List.java ?

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

Author Comment

by:eskimon
ID: 2680545
sorry I had to turn it in at 10am EST ..
it's a lost cause now ..
tnx anyhow
0

Featured Post

PeopleSoft Has Never Been Easier

PeopleSoft Adoption Made Smooth & Simple!

On-The-Job Training Is made Intuitive & Easy With WalkMe's On-Screen Guidance Tool.  Claim Your Free WalkMe Account Now

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

For beginner Java programmers or at least those new to the Eclipse IDE, the following tutorial will show some (four) ways in which you can import your Java projects to your Eclipse workbench. Introduction While learning Java can be done with…
Introduction This article is the last of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers our test design approach and then goes through a simple test case example, how …
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
Suggested Courses

752 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question