It seems to me like it should be possible to print a circular linked list backwards in constant space and linear time using recursion and tail-call-optimization. However, I am having difficulty due to trying to print the current element after making the recursive call. By inspecting the disassembly, I see that the function is being called and not jumped to. If I change it to print forwards instead of backwards, the function call is properly eliminated.
I have seen this related question, however I am specifically interested in solving it using recursion and TCO.
The code I am 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 with slight modifications for a 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 with current pass */
bar(next, curr, sentinel, pass);
} else if ((pass == 1) && (next == sentinel)) {
/* make sure to print the last element */
bar(next, curr, sentinel, pass);
} else {
/* end of list reached, go over list in reverse */
bar(curr, prev, sentinel, pass+1);
}
}
To benefit from tail-call optimization you have to reorganize the code. Here's one way to do 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 with current pass */
bar(next, curr, pass);
} else {
/* end of list reached, go over list in reverse */
bar(curr, NULL, pass+1);
}
}
This function assumes that the end of the list is signaled by NULL
. The list is traversed in two passes: first to reverse it in-place, second to print the elements and reverse it again. And, as far as I can tell, gcc -O3
does a tail-call optimization so the algorithm runs in constant space.
To call this function use:
bar(&e1, NULL, 0);