Эта функция действительно рекурсивна?

Question

Эта функция действительно рекурсивна?

Я читал о рекурсии в Программируемые интервью (3-е изд.), Где они представляют следующую рекурсивную factorial функция:

int factorial(int n){
if (n > 1) { /* Recursive case */
return factorial(n-1) * n;
} else {     /* Base case */
return 1;
}
}

В нижней части той же страницы (стр. 108) они говорят о хвостовых рекурсивных функциях:

Обратите внимание, что когда значение, возвращаемое рекурсивным вызовом, само сразу возвращается, как в предыдущем определении для factorialфункция хвостовая рекурсия.

Но так ли это на самом деле? Последний вызов в функции * вызовите, не будет ли сохранен этот кадр стека (если мы не примем во внимание оптимизацию компилятора)? Это действительно хвост рекурсивный?

1

c++tail-recursion

Решение

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

Вы можете переписать его как хвостовой рекурсивный:

int factorial(int n){
return factorial2(n, 1);
}
int factorial2(int n, int accum) {
if (n < 1) {
return accum;
} else {
return factorial2(n - 1, accum * n);
}
}

5

Цитирование по этой ссылке: хвостовая рекурсия на примере факториала

 factorial(n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}//equivalent to your code

This definition is NOT tail-recursive since the recursive call to
factorial is not the last thing in the function
(its result has to be multiplied by n)

1

Tail Recursive это особый случай рекурсии, в котором последняя операция функции является рекурсивным вызовом. В хвостовой рекурсивной функции нет ожидающих операций, которые должны быть выполнены при возврате из рекурсивного вызова.
Упомянутая вами функция не является хвостовой рекурсией, потому что есть ожидающая операция, т.е. умножение, которое должно быть выполнено по возвращению из рекурсивного вызова.
Если вы сделали это:

    int factorial(int n,int result)
{
if (n > 1)
{ /* Recursive case */
return factorial(n-1,n*result);
}
else
{     /* Base case */
return result;
}
}

будет хвостовой рекурсивной функцией. так как он не имеет ожидающей операции по возвращению из рекурсивного вызова.

0

Источник

Accepted Answer

Нет, это не хвостовая рекурсия. Результат возвращается factorial(n-1) все еще должен быть умножен на n, что требует, чтобы factorial(n) восстановить контроль (таким образом, обязав, чтобы призыв к factorial(n-1) быть вызовом, а не прыжком).

С учетом сказанного, даже если бы он был хвост-рекурсивным, компилятор все равно мог бы не использовать TCO для него. Зависит от компилятора и оптимизаций, которые вы просите сделать.

4