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

更新:循環リストのわずかな変更を加えたジョニの回答を使用して解決しました

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

末尾呼び出しの最適化の恩恵を受けるには、コードを再編成する必要があります。これを行う1つの方法は次のとおりです。

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ます。リストは 2 つのパスでトラバースされます。1 つ目はその場で反転し、2 つ目は要素を出力して再び反転します。そして、私が知る限りgcc -O3、テールコールの最適化を行うため、アルゴリズムは一定のスペースで実行されます。

この関数を呼び出すには:

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