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

 
 
Morris Dovey
Guest
Posts: n/a
 
      02-10-2008
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
 
Reply With Quote
 
 
 
 
Gene
Guest
Posts: n/a
 
      02-10-2008
On Feb 10, 9:36*am, Morris Dovey <(E-Mail Removed)> 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.

 
Reply With Quote
 
 
 
 
Gene
Guest
Posts: n/a
 
      02-10-2008
On Feb 10, 7:09*am, Morris Dovey <(E-Mail Removed)> 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.
 
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