c++ - Print a linked list backwards in constant space and linear time using recursion -

it seems me should possible print circular linked list backwards in constant space , linear time using recursion , tail-call-optimization. however, having difficulty due trying print current element after making recursive call. inspecting disassembly, see function being called , not jumped to. if change print forwards instead of backwards, function call eliminated.

i have seen this related question, interested in solving using recursion , tco.

the code using:

#include <stdio.h>  struct node {     int data;     struct node *next; };   void bar(struct node *elem, struct node *sentinel) {     if (elem->next == sentinel) {         printf("%d\n", elem->data);         return;     }     bar(elem->next, sentinel), printf("%d\n", elem->data); }  int main(void) {     struct node e1, e2;     e1.data = 1;     e2.data = 2;     e1.next = &e2;     e2.next = &e1;     bar(&e1, &e1);     return 0; } 

and compiling with

    $ g++ -g -o3 -wa,-alh test.cpp -o test.o 

update: solved using joni's answer slight modifications circular list

void bar(struct node *curr, struct node *prev, struct node *sentinel,     int pass) {     if (pass == 1) printf("%d\n", curr->data);     if (pass > 1) return;     if ((pass == 1) && (curr == sentinel))         return;      /* reverse current node */     struct node *next = curr->next;     curr->next = prev;      if (next != sentinel) {         /* tail call current pass */         bar(next, curr, sentinel, pass);     } else if ((pass == 1) && (next == sentinel)) {         /* make sure print last element */         bar(next, curr, sentinel, pass);     } else {         /* end of list reached, go on list in reverse */         bar(curr, prev, sentinel, pass+1);     } } 

to benefit tail-call optimization have reorganize code. here's 1 way it:

void bar(struct node *curr, struct node *prev, int pass) {     if (pass == 1) printf("%d\n", curr->data);     if (pass > 1) return;      /* reverse current node */     struct node *next = curr->next;     curr->next = prev;      if (next) {         /* tail call current pass */         bar(next, curr, pass);     } else {         /* end of list reached, go on list in reverse */         bar(curr, null, pass+1);     } } 

this function assumes end of list signaled null. list traversed in 2 passes: first reverse in-place, second print elements , reverse again. and, far can tell, gcc -o3 tail-call optimization algorithm runs in constant space.

to call function use:

bar(&e1, null, 0);