1

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

我已经看到了这个相关的问题，但是我对使用递归和 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);
    }
}
4

2 回答 2

4

更新：这个答案具有误导性（请否决它！），只有当您无法修改数据结构时，它才是正确的。

不可能。递归和常数空间是这项任务的矛盾要求。

我知道您想使用 TCO，但您不能，因为在递归调用之后您还有额外的工作要做。

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

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

于 2013-09-04T15:15:44.770 回答
2

要从尾调用优化中受益，您必须重新组织代码。这是一种方法：

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

此函数假定列表的结尾由 表示NULL。该列表分两次遍历：第一次是原地反转，第二次是打印元素并再次反转它。而且，据我所知，gcc -O3进行了尾调用优化，因此算法在恒定空间中运行。

要调用此函数，请使用：

bar(&e1, NULL, 0);
于 2013-09-04T18:00:46.070 回答