Обсуждение:Хвостовая рекурсия

Примеры

Необходимо добавить примеры нехвостовой рекурсии. Еще лучше преобразование нехвостовая рекурсия -> хвостовая рекурсия. 80.254.112.221 22:02, 9 января 2009 (UTC) Андрей.

Язык

А слабо было показать на примере более распространенного языка? C, C# или Java? Abatishchev 12:07, 30 июля 2010 (UTC)

В Java не поддерживается. В C:

vi@vi-notebook:~/code/prejvm$ cat tailrec.c 
int factorial_accum(long long int n, long long int accum) {
    if(n==0) {
	return accum;
    } else {
	return factorial_accum(n-1, accum*n);
    }
}

int factorial(int n) { return factorial_accum(n, 1); }

int main(int argc, char* argv[]) {
    printf("%d\n", factorial(atoi(argv[1]))); 
    return 0;
}
vi@vi-notebook:~/code/prejvm$ gcc tailrec.c -o tailrec   # No optimisation
vi@vi-notebook:~/code/prejvm$ ./tailrec 10
3628800
vi@vi-notebook:~/code/prejvm$ ./tailrec 100000
0
vi@vi-notebook:~/code/prejvm$ ./tailrec 1000000000
Segmentation fault
vi@vi-notebook:~/code/prejvm$ gcc tailrec.c -O2 -o tailrec   # Optimise tail calls
vi@vi-notebook:~/code/prejvm$ ./tailrec 1000000000
0

_Vi 12:06, 15 сентября 2010 (UTC)

Не согласен с формулировкой "не поддерживается". Код компилируется, работает, хотя бы для малых n. Переполнение стека при больших n говорит о том, что компилятор не заменил хвостую рекурсию итерацией, то есть о неэффективной поддержке хвостовой рекурсии. Стандарты C/C++ и Java и не требует от компиляторов оптимизировать хвостовую рекурсию. В отличие от, скажем, Scheme, где это строго предписывается стандартом. -- X7q 12:20, 15 сентября 2010 (UTC)

Спасибо! Abatishchev 16:14, 15 сентября 2010 (UTC)

Привел пример на C. -- X7q 01:42, 16 сентября 2010 (UTC)