«

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

On Feb 10, 9:36*am, Morris Dovey <mrdo...@iedu.com> wrote:
> 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.

On Feb 10, 7:09*am, Morris Dovey <mrdo...@iedu.com> 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.
>
> --
> 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.