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(no de *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_re cursion_back.c: 69: error: initializer element is not
constant
reverse_list_re cursion_back.c: 76: error: invalid type argument of '->'


Any and every help is appreciated.

[Ian Collins]

Re: Reverse a linked list using Recursion

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(no de *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.

[Morris Dovey]

Re: Reverse a linked list using Recursion

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

[Gene]

Re: Reverse a linked list using Recursion

On Feb 9, 9:09 pm, Morris Dovey <mrdo...@iedu.c omwrote:

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

[Morris Dovey]

Re: Reverse a linked list using Recursion

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

[Willem]

Re: Reverse a linked list using Recursion

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]

Re: Reverse a linked list using Recursion

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

[Gene]

Re: Reverse a linked list using Recursion

On Feb 10, 9:36 am, Morris Dovey <mrdo...@iedu.c omwrote:

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

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]

Re: Reverse a linked list using Recursion

On Feb 10, 7:09 am, Morris Dovey <mrdo...@iedu.c omwrote:

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 USAhttp://www.iedu.com/DeSoto

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.

[Morris Dovey]

Re: Reverse a linked list using Recursion

Gene wrote:

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!

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA

http://www.iedu.com/DeSoto