Reverse a linked list using Recursion

Discussion in 'C Programming' started by DanielJohnson, Feb 9, 2008.

  1. 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.
    DanielJohnson, Feb 9, 2008
    #1
    1. Advertising

  2. DanielJohnson

    Ian Collins Guest

    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.
    Ian Collins, Feb 9, 2008
    #2
    1. Advertising

  3. DanielJohnson

    Morris Dovey Guest

    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
    Morris Dovey, Feb 10, 2008
    #3
  4. DanielJohnson

    Gene Guest

    On Feb 9, 9:09 pm, Morris Dovey <> wrote:
    > 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);
    Gene, Feb 10, 2008
    #4
  5. DanielJohnson

    Kaz Kylheku Guest

    On Feb 9, 10:48 am, 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


    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.
    Kaz Kylheku, Feb 10, 2008
    #5
  6. DanielJohnson

    Morris Dovey Guest

    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
    Morris Dovey, Feb 10, 2008
    #6
  7. DanielJohnson

    Willem Guest

    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
    Willem, Feb 10, 2008
    #7
  8. DanielJohnson

    Morris Dovey Guest

    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
    Morris Dovey, Feb 10, 2008
    #8
  9. DanielJohnson

    Morris Dovey Guest

    Re: Reverse a linked list using Recursion [rambling]

    DanielJohnson wrote:

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

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto
    Morris Dovey, Feb 10, 2008
    #9
  10. > 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.
    DanielJohnson, Feb 10, 2008
    #10
  11. DanielJohnson

    Morris Dovey Guest

    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
    Morris Dovey, Feb 10, 2008
    #11
  12. DanielJohnson

    Gene Guest

    On Feb 10, 9:36 am, Morris Dovey <> 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.
    Gene, Feb 10, 2008
    #12
  13. DanielJohnson

    Gene Guest

    On Feb 10, 7:09 am, Morris Dovey <> 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.
    Gene, Feb 10, 2008
    #13
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Perpetual Snow

    Reverse a linked list

    Perpetual Snow, Nov 26, 2003, in forum: C Programming
    Replies:
    9
    Views:
    3,317
    Derk Gwen
    Nov 27, 2003
  2. RAJASEKHAR KONDABALA

    Reverse search in a singly-linked list

    RAJASEKHAR KONDABALA, Dec 24, 2003, in forum: C Programming
    Replies:
    20
    Views:
    5,798
    saadbinsaulat
    Feb 27, 2011
  3. fool
    Replies:
    14
    Views:
    496
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    659
    John Carson
    Oct 2, 2006
  5. Replies:
    8
    Views:
    723
    John Reye
    Apr 26, 2012
Loading...

Share This Page