Reverse a linked list using Recursion

[DanielJohnson]

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.

 

[Ian Collins]

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.

 

[Morris Dovey]

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!

 

[Gene]

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

 

[Kaz Kylheku]

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.

 

[Morris Dovey]

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.

 

[Willem]

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

 

[Morris Dovey]

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]

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.

 

[DanielJohnson]

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.

 

[Morris Dovey]

You really aren't done tweaking yet. You can make reversed_tail a
local variable initialized to NULL, since that's all the caller does
with it.

Of course! I should have been paying more attention (besides, now
I can sneak away from not having typed reversed_tail <g>)

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

...which is the traditional iterative list reverser you will find in
some textbooks.

I /do/ like this better. I don't think we're doing much for Dan,
but I'm having fun!

I've missed a lot in never having taken any CS courses, and I'll
probably always be stuck in "catch-up" mode.

This is one of many cases where starting with a "recursive" functional
definition and transforming it with algebraic operations that preserve
behavior yields an efficient C code.

Looks like the proof is in the pudding. Thanks!

 

[Gene]

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.

You really aren't done tweaking yet. You can make reversed_tail a
local variable initialized to NULL, since that's all the caller does
with it.

Now you should _really_ like the fact that what this code does is, as
pseudocode,

set Y empty
while (list X is not empty)
push(pop(X), Y)
return Y

...which is the traditional iterative list reverser you will find in
some textbooks.

This is one of many cases where starting with a "recursive" functional
definition and transforming it with algebraic operations that preserve
behavior yields an efficient C code.

 

[Gene]

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.

It ought to use a small _constant_ stack space with a reasonable
compiler because the tail call becomes a loop. I know gcc -O2 will do
this. So will MS VC 2005 Express.

If the compiler is lame enought to miss the tail recursion, then it
will probably use 33% more stack than your code on most 32-bit
machines: 4 words rather than 3--frame pointer + return address + 2
vice 1 pointers per self-call.