Если вы хотите избежать переполнения стека с помощью бесконечной рекурсии, вам, к сожалению, придется углубиться в какую-то сборку, чтобы изменить стек так, чтобы новая запись активации не постоянно помещалась в стек, что после какая-то точка вызовет переполнение. Поскольку вы делаете рекурсивный вызов в конце функции, он вызывается в других языках, где рекурсия популярна (т. Е. В Lisp, Scheme, Haskell и т. Д.), Для оптимизации с помощью trail-call. Это предотвращает переполнение стека, в основном превращая хвостовой вызов в цикл. Это будет примерно так в C (примечание: я использую встроенную сборку с gcc на x86, и я изменил ваши аргументы на int
с double
, чтобы упростить сборку. Также я изменил на C с C ++, чтобы избежать искажения имен имен функций. Наконец, "\ n \ t" в конце каждого оператора не является фактической командой сборки, но требуется для встроенной сборки в gcc):
#include <stdio.h>
void rek(int x)
{
printf("Value for x: %d\n", x);
//we now duplicate the equvalent of `rek(x+1);` with tail-call optimization
__asm("movl 8(%ebp), %eax\n\t" //get the value of x off the stack
"incl %eax\n\t" //add 1 to the value of x
"movl 4(%ebp), %ecx\n\t" //save the return address on the stack
"movl (%ebp), %edx\n\t" //save the caller's activation record base pointer
"addl $12, %ebp\n\t" //erase the activation record
"movl %ebp, %esp\n\t" //reset the stack pointer
"pushl %eax\n\t" //push the new value of x on the stack for function call
"pushl %ecx\n\t" //push the return value back to the caller (i.e., main()) on the stack
"movl %edx, %ebp\n\t" //restore the old value of the caller's stack base pointer
"jmp rek\n\t"); //jump to the start of rek()
}
int main()
{
rek(1);
printf("Finished call\n"); //<== we never get here
return 0;
}
Скомпилированный с gcc 4.4.3 в Ubuntu 10.04, он работал «бесконечно» в бесконечном цикле без переполнения стека, где, как и без оптимизации хвостового вызова, он довольно быстро падал с ошибкой сегментации. Из комментариев в разделе __asm
видно, как пространство записи активации стека «перерабатывается», чтобы каждый новый вызов не занимал пространство в стеке. Это включает в себя сохранение значений ключей в старой записи активации (базовый указатель записи активации предыдущего абонента и адрес возврата) и их восстановление, но с изменением аргументов для следующего рекурсивного вызова функции.
И снова, другие языки, в основном функциональные языки, выполняют оптимизацию хвостового вызова в качестве базовой функции языка. Так что рекурсивная функция хвостового вызова в Scheme / Lisp / etc. не будет переполнять стек, поскольку этот тип манипуляции со стеком выполняется для вас скрытно, когда новый вызов функции выполняется как последний оператор существующей функции.