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

Question

Мне кажется, что должно быть возможно напечатать круговой связанный список назад в постоянном пространстве и линейном времени с помощью рекурсии и оптимизации хвоста. Тем не менее, у меня возникают трудности из-за попытки распечатать текущий элемент после выполнения рекурсивного вызова. Проверяя разборку, я вижу, что функция вызывается и не подпрыгивает. Если я изменил его для печати вперед, а не назад, вызов функции будет правильно удален.

Я видел this Связанный вопрос, однако меня особенно интересует его решение с использованием рекурсии и 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); 
    } 
} 

Answer 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. Список проходит через два прохода: сначала отменить его на месте, а затем распечатать элементы и снова отменить его. И, насколько я могу судить, gcc -O3 делает оптимизацию хвостового вызова, поэтому алгоритм работает в постоянном пространстве.

Для вызова этой функции используйте:

bar(&e1, NULL, 0); 

Answer 2

Update: этот ответ вводит в заблуждение (пожалуйста, снимите его!), это правда, только если вы не можете модифицировать y структура данных.

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

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

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

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