Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Reverse a linked list using Recursion

Reply
Thread Tools

Reverse a linked list using Recursion

 
 
DanielJohnson
Guest
Posts: n/a
 
      02-09-2008
Hi,

I am not seeking a solution nor am I asking a homework problem. I have
my solution but it doesn't run correctly as expected because of some
error and I am trying to understand this error. Here is my code

node* Reverse_List(node *p)
{
/*Is there any problem with this statement */
static node *head = p;
static node *revHead = NULL;
if (p == NULL)
return NULL;
if (p->next == NULL)
revHead = p;
else
/* ***** Is this allowed in C99 specs***** */
reverse(p->next)->next = p;
if (p == head) {
p->next = NULL;
return revHead;
}
else
return p;
}


I get the following error. I am using gcc compiler

In function 'Reverse_List':
reverse_list_recursion_back.c:69: error: initializer element is not
constant
reverse_list_recursion_back.c:76: error: invalid type argument of '->'


Any and every help is appreciated.
 
Reply With Quote
 
 
 
 
Ian Collins
Guest
Posts: n/a
 
      02-09-2008
DanielJohnson wrote:
> Hi,
>
> I am not seeking a solution nor am I asking a homework problem. I have
> my solution but it doesn't run correctly as expected because of some
> error and I am trying to understand this error. Here is my code
>
> node* Reverse_List(node *p)
> {
> /*Is there any problem with this statement */
> static node *head = p;


Static variables are initialised before the program runs, so the
initialiser must be a compile time constant.

> static node *revHead = NULL;
> if (p == NULL)
> return NULL;
> if (p->next == NULL)
> revHead = p;
> else
> /* ***** Is this allowed in C99 specs***** */
> reverse(p->next)->next = p;


reverse is not declared.

--
Ian Collins.
 
Reply With Quote
 
 
 
 
Morris Dovey
Guest
Posts: n/a
 
      02-10-2008
The answer to your question is that you _can_ use a pointer value
returned from a function as a pointer to an object of appropriate
type. <g>

I couldn't resist playing along. I took a slightly different
approach by keeping an internal pointer ('tail') to the last node
in the list.

typedef struct node_d
{ struct node_d *next;
int data;
} node;

node *rev(node *p)
{ static node *head, *tail;
if (p)
{ rev(p->next);
p->next = NULL;
if (head) tail->next = p;
else head = p;
tail = p;
}
else head = NULL;
return head;
}

An interesting exercise. Thanks!

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto
 
Reply With Quote
 
Gene
Guest
Posts: n/a
 
      02-10-2008
On Feb 9, 9:09*pm, Morris Dovey <(E-Mail Removed)> wrote:
> The answer to your question is that you _can_ use a pointer value
> returned from a function as a pointer to an object of appropriate
> type. <g>
>
> I couldn't resist playing along. I took a slightly different
> approach by keeping an internal pointer ('tail') to the last node
> in the list.
>
> * *typedef struct node_d
> * *{ *struct node_d *next;
> * * * int data;
> * *} *node;
>
> * *node *rev(node *p)
> * *{ *static node *head, *tail;
> * * * if (p)
> * * * { *rev(p->next);
> * * * * *p->next = NULL;
> * * * * *if (head) tail->next = p;
> * * * * *else head = p;
> * * * * *tail = p;
> * * * }
> * * * else head = NULL;
> * * * return head;
> * *}
>


Well, since the cat is out of the bag, IMO it's more intuitive to
build the reversed list with a second parameter...

node *rev(node *head, *reversed_tail)
{
if (head) {
node *next = head->next;
head->next = reversed_tail;
return rev(next, head);
}
return reversed_tail;
}

Since this is tail-recursive, if you compile it with e.g. gcc -O2, it
will be transformed into a loop.

Initiate with

node *reversed_list = rev(list, NULL);

 
Reply With Quote
 
Kaz Kylheku
Guest
Posts: n/a
 
      02-10-2008
On Feb 9, 10:48*am, DanielJohnson <(E-Mail Removed)> wrote:
> Hi,
>
> I am not seeking a solution nor am I asking a homework problem. I have
> my solution but it doesn't run correctly as expected because of some
> error and I am trying to understand this error. Here is my code


Using (non-tail) recursion to reverse lists is retarded. It requires
automatic storage in proportion to the length of the list.

> node* Reverse_List(node *p)
> {
> * /*Is there any problem with this statement */
> * static node *head = p;
> * static node *revHead = NULL;


Static variables render your code nonreentrant. There is almost no
excuse for introducing reentrancy issues into a simple list reversal.

C doesn't have this feature of one-time initialization of static
variables with the values of run-time expressions.

C++ has the feature. That feature is typically implemented using
hidden flags, analogous to this:

{
static node *head;
static node *revHead;
static int __entered_before;

if (!__entered_before) {
__entered_before = true;
head = p;
}

If you can't avoid writing recursion that has some kind of pervasive
context that must be accessible during an entire session, consider
breaking the function into two: an interface part and a recurser:

static node *Reverse_Private(node *, context *ctx)
{
/* context has members ctx->head and ctx->revHead */

/* ... rest of function ... */
}

node *Reverse_List(node *list)
{
/* context is automatically allocated, not statically, and
so reverse is reentrant */
context ctx = { 0, 0 };
return Reverse_Private(list, &ctx);
}

Reverse_Private recurses by calling itself, and passes down the ctx
pointer it was given; it doesn't call Reverse_List.
 
Reply With Quote
 
Morris Dovey
Guest
Posts: n/a
 
      02-10-2008
Gene wrote:

> Well, since the cat is out of the bag, IMO it's more intuitive to
> build the reversed list with a second parameter...
>
> node *rev(node *head, *reversed_tail)
> {
> if (head) {
> node *next = head->next;
> head->next = reversed_tail;
> return rev(next, head);
> }
> return reversed_tail;
> }


It's _less_ intuitive to me, and (probably) uses 50% more stack
space - but I like this a lot better than what I cobbled
together.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto
 
Reply With Quote
 
Willem
Guest
Posts: n/a
 
      02-10-2008
Morris wrote:
) Gene wrote:
)> Well, since the cat is out of the bag, IMO it's more intuitive to
)> build the reversed list with a second parameter...
)>
)> node *rev(node *head, *reversed_tail)
)> {
)> if (head) {
)> node *next = head->next;
)> head->next = reversed_tail;
)> return rev(next, head);
)> }
)> return reversed_tail;
)> }
)
) It's _less_ intuitive to me, and (probably) uses 50% more stack
) space - but I like this a lot better than what I cobbled
) together.

You may notice that it uses tail recursion.
A good compiler would rewrite the above code to:

node *rev(node *head, *reversed_tail)
{
tail_recurse:
if (head) {
node *next = head->next;
head->next = reversed_tail;
/* return rev(next, head); */
reversed_tail = head; head = next; goto tail_recurse;
}
return reversed_tail;
}


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
Reply With Quote
 
Morris Dovey
Guest
Posts: n/a
 
      02-10-2008
Willem wrote:

> You may notice that it uses tail recursion.
> A good compiler would rewrite the above code to:
>
> node *rev(node *head, *reversed_tail)
> {
> tail_recurse:
> if (head) {
> node *next = head->next;
> head->next = reversed_tail;
> /* return rev(next, head); */
> reversed_tail = head; head = next; goto tail_recurse;
> }
> return reversed_tail;
> }


Which (with cut-n-paste + minor tweak) "cleans up" to

node *rev(node *head, *reversed_tail)
{ while (head)
{ node *next = head->next;
head->next = reversed_tail;
reversed_tail = head;
head = next;
}
return reversed_tail;
}

Which eliminates the goto, the call/stack overhead, Kaz's
re-entrancy issue - but doesn't address the Dan's interest in a
recursive function.

No matter - /I/ like it.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto
 
Reply With Quote
 
Morris Dovey
Guest
Posts: n/a
 
      02-10-2008
DanielJohnson wrote:

> I have programmed in C for sometime now but I am not a pro because I
> do not think in terms of call/stack overhead or type of recursive
> function etc. My main aim is to get the program up and running and see
> that big O is not too bad but I have never thought on the optimization
> at the compiler lever. Having said that, I now want to learn to
> analyze code. Can you suggest any good book or starting point where
> you can test your code in terms of calls or overheads and learn all
> these intricate things.
>
> I wrote the same program that is to reverse a linked list using
> iteration. I had a questions...when are recursive functions
> inefficient ? I have always seen people talking that use recursion
> only if it is must and iterative functions for all other cases. Can
> you Pros throw some insight into evaluating recursive/iterative
> functions and their overheads.


Dan...

In spite of the fact that I enjoy playing with recursive
algorithms, the only place where I've found it to offer any
advantage is when it allows postponement of some action or
decision until all of the determining factors are known - and
even then there is an element of risk introduced by the recursion
itself.

For example, I wrote a version of gets() that used getchar() to
recursively accept input and then (when the end of input was
recognized) allocated an exact-sized buffer, stored all of the
character data, and returned a pointer to the buffer. The danger
in that approach is that (on this machine, under this version of
Linux) the program would reliably blow up when an input line was
much longer than about 700K characters - because there was no was
to recognize that stack space was used up. This is the type of
failure that haunts recursive algorithms in general.

There are some fairly impressive code analysts right here on CLC
- Ben Pfaff, Kaz, Richard (more than one of 'em!), Chris
Torek,... too many to name. I'd look to them for book suggestions
- and if the answer you need is not in the book, I'd be inclined
to ask right here.

It's also informative to do what Willem just did - hand your code
to a real compiler and see what it does. After a while you begin
to have develop a feel for how various constructs translate into
machine operations (Lawrence Kirby has an amazing ability to do
this) and that can be both a help and a hinderance since this is
a very machine architecture specific technique. Still, knowing
how it plays on even one machine seems to provide a useful 'gut
feel' for other machines.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto
 
Reply With Quote
 
DanielJohnson
Guest
Posts: n/a
 
      02-10-2008
> Which (with cut-n-paste + minor tweak) "cleans up" to
>
> node *rev(node *head, *reversed_tail)
> { while (head)
> { node *next = head->next;
> head->next = reversed_tail;
> reversed_tail = head;
> head = next;
> }
> return reversed_tail;
> }
>
> Which eliminates the goto, the call/stack overhead, Kaz's
> re-entrancy issue - but doesn't address the Dan's interest in a
> recursive function.


I have programmed in C for sometime now but I am not a pro because I
do not think in terms of call/stack overhead or type of recursive
function etc. My main aim is to get the program up and running and see
that big O is not too bad but I have never thought on the optimization
at the compiler lever. Having said that, I now want to learn to
analyze code. Can you suggest any good book or starting point where
you can test your code in terms of calls or overheads and learn all
these intricate things.

I wrote the same program that is to reverse a linked list using
iteration. I had a questions...when are recursive functions
inefficient ? I have always seen people talking that use recursion
only if it is must and iterative functions for all other cases. Can
you Pros throw some insight into evaluating recursive/iterative
functions and their overheads.

Every help is greatly appreciated.


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
va_arg... recursion: changing arguments and the using recursion jononanon@googlemail.com C Programming 8 04-26-2012 08:37 PM
Reverse search in a singly-linked list RAJASEKHAR KONDABALA C Programming 20 02-27-2011 12:53 PM
Linked list within a linked list joshd C++ 12 10-02-2006 08:57 AM
Linked list, New try (was:Linked list, no out put,help) fool C Programming 14 07-03-2006 12:29 AM
Reverse a linked list Perpetual Snow C Programming 9 11-27-2003 01:58 AM



Advertisments