Напечатайте связанный список назад в постоянном пространстве и линейном времени, используя рекурсию

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

обновление: решено с использованием ответа Джони с небольшими изменениями для кругового списка

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

1

c++recursion tail-call-optimization

Решение

Другие решения

Обновление: этот ответ вводит в заблуждение (пожалуйста, уменьшите его!), Это верно только в том случае, если вы не можете изменить структуру данных.

Это невозможно. Рекурсия и постоянное пространство являются противоречивыми требованиями в этой задаче.

Я понимаю, что вы хотели бы использовать TCO, но вы не можете, так как у вас есть дополнительная работа, чтобы сделать после рекурсивный вызов.

Из википедии http://en.wikipedia.org/wiki/Tail_call:

В информатике хвостовой вызов — это вызов подпрограммы, который происходит
внутри другой процедуры, как его окончательное действие.

5

Источник

Accepted Answer

Чтобы извлечь выгоду из оптимизации хвостового вызова, вы должны реорганизовать код. Вот один из способов сделать это:

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

2