使用递归以恒定空间和线性时间向后打印链接列表

Question

在我看来,应该可以使用递归和尾调用优化在恒定空间和线性时间内向后打印循环链表.但是,由于在进行递归调用后尝试打印当前元素,我遇到了困难.通过检查反汇编,我看到函数被调用而不是跳转到.如果我将其更改为向前打印而不是向后打印,则可以正确消除函数调用.

我已经看到了这个相关的问题,但我特别感兴趣的是使用递归和TCO来解决它.

我正在使用的代码:

#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;
}

和编译

    $ g++ -g -O3 -Wa,-alh test.cpp -o test.o

更新:使用Joni的答案解决,略微修改循环列表

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);
    }
}

Answer 1

更新:这个答案有误导性(请注意它!),只有在你无法修改数据结构时才会这样.

不可能.递归和恒定空间是这项任务中相互矛盾的要求.

我知道你想使用TCO,但你不能在递归调用之后做额外的工作.

来自维基百科http://en.wikipedia.org/wiki/Tail_call:

在计算机科学中,尾调用是在另一个过程中作为其最终动作发生的子例程调用.