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]

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.

[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!

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto

[Gene]

On Feb 9, 9:09*pm, Morris Dovey <[e-mail]:

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]

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]

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]

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]

On Feb 10, 9:36*am, Morris Dovey <[e-mail]:

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]

On Feb 10, 7:09*am, Morris Dovey <[e-mail]:

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]

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