Solved

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

Posted on 2000-04-03
35
196 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
  • 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
 
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

For customizing the look of your lightweight component and making it look lucid like it was made of glass. Or: how to make your component more Apple-ish ;) This tip assumes your component to be of rectangular shape and completely opaque. (COD…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
This theoretical tutorial explains exceptions, reasons for exceptions, different categories of exception and exception hierarchy.

708 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

Need Help in Real-Time?

Connect with top rated Experts

14 Experts available now in Live!

Get 1:1 Help Now