再帰と末尾呼び出しの最適化を使用して、一定の空間と線形時間で循環リンクリストを逆方向に出力できるように思えます。ただし、再帰呼び出しを行った後に現在の要素を印刷しようとすると、問題が発生します。逆アセンブリを調べると、関数が呼び出され、ジャンプされていないことがわかります。逆方向ではなく順方向に出力するように変更すると、関数呼び出しが適切に削除されます。
この関連する質問を見たことがありますが、再帰と 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);
}
}