Это квалифицируется как хвостовая рекурсия?

Question

Это квалифицируется как хвостовая рекурсия?

Возможный дубликат:
Хвостовая рекурсия в C ++

Я новичок в хвосте рекурсии в C ++. Мой проект требует, чтобы все мои функции были рекурсивными. Я проверил следующий код, и он работает правильно. Однако я не уверен, что то, как я это сделал, квалифицируется как хвостовая рекурсия.

static int sum_helper(list_t hList, int accumulator){
if (list_isEmpty(hList))
return accumulator;
else {
accumulator += list_first(hList);
hList = list_rest(hList);
return sum_helper(hList, accumulator);
}
}

int sum(list_t list){
/*
// EFFECTS: returns the sum of each element in list
//          zero if the list is empty.
*/
if (list_isEmpty(list))
return 0;
return sum_helper(list, 0);
}

Спасибо!

2

c++tail-recursion

Решение

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

Это хвостовая рекурсия, при условии, что list_t не имеет нетривиального деструктора. Если у него есть нетривиальный деструктор, деструктор должен запускаться после возврата рекурсивного вызова и до того, как сама функция вернется.

Бонус:

int sum(list_t hList, int accumulator = 0) {
return list_isEmpty(hList)
? 0
: sum(list_rest(hList), accumulator + list_first(hList));
}

Но вкусы меняются; некоторым людям может понравиться ваш.

2

С теоретической точки зрения да, это хвостовая рекурсия (при условии, что hList не имеет нетривиального деструктора). Но с практической точки зрения это зависит от вашего компилятора и его настроек. Давайте посмотрим на сборку, сгенерированную для этого простого кода:

#include <cstdlib>

struct list{
int head;
list * tail;
};int sum_helper(list * l, int accumulator){
if (l == NULL)
return accumulator;
else {
accumulator += l->head;
return sum_helper(l->tail, accumulator);
}
}

Оптимизация включена: (g ++ -O2 …, скучная часть опущена):

    testq   %rdi, %rdi
movl    %esi, %eax
je  .L2
...
.L6:
...
jne .L6                  <-- loop
.L2:
rep
ret

Это явно петля. Но когда вы отключаете оптимизацию, вы получаете:

_Z10sum_helperP4listi:
.LFB6:
...
jne .L2
movl    -12(%rbp), %eax
jmp .L3
.L2:
...
call    _Z10sum_helperP4listi     <-- recursion
.L3:
leave
.cfi_def_cfa 7, 8
ret

Что рекурсивно.

1

Источник

Accepted Answer

Короче ничего не делаешь после рекурсивного вызова (sum_helper). Это означает, что вам никогда не нужно возвращаться к вызывающей стороне, и, таким образом, вы можете выбросить кадр стека вызывающей стороны.

Возьмите пример нормальной факторной функции

int fact(int x)
{
if(x == 0)
return 1;
else
return x * fact(x-1);
}

Это не хвостовая рекурсия, так как значение fact(x-1) нужно вернуть, затем умножить на шесть. Вместо этого мы можем немного обмануть и передать аккумулятор. Видеть это:

int fact(int x, int acc)
{
if(x == 0)
return acc;      // Technically, acc * 1, but that's the identity anyway.
else
return fact(x-1, acc*x);
}

Здесь последний вызов функции в потоке управления fact(x-1, acc*x), После этого нам не нужно использовать возвращаемое значение для чего-либо из вызываемой функции для чего-либо еще, поэтому мы не делаем необходимость вернуться к текущему кадру. По этой причине мы можем выбросить кадр стека и применить другие оптимизации.

Отказ от ответственности: я, вероятно, применил алгоритм факториала неправильно, но вы получите суть. С надеждой.

2