Я написал простую функцию Фибоначчи как упражнение на С++ (используя Visual Studio), чтобы проверить Tail Recursion и посмотреть, как это работает.
это код:
int fib_tail(int n, int res, int next) {
if (n == 0) {
return res;
}
return fib_tail(n - 1, next, res + next);
}
int main()
{
fib_tail(10,0,1); //Tail Recursion works
}
когда я скомпилировался в режиме Release, я видел оптимизированную сборку, используя инструкцию JMP, несмотря на вызов. Итак, мой вывод: работа хвоста рекурсии. См. Изображение ниже:
Я хотел бы выполнить некоторые тесты производительности, увеличив входную переменную n в моей функции Fibonacci. Затем я решил изменить тип переменной, используемый в функции, от int до unsigned long long. Затем я прошел большое число, например: 10e + 08
Теперь это новая функция:
typedef unsigned long long ULONG64;
ULONG64 fib_tail(ULONG64 n, ULONG64 res, ULONG64 next) {
if (n == 0) {
return res;
}
return fib_tail(n - 1, next, res + next);
}
int main()
{
fib_tail(10e+9,0,1); //Tail recursion does not work
}
Когда я запускал код выше, я получил исключение, что заставило меня думать, что хвостовая рекурсия не работает. Я посмотрел на сборку, и на самом деле я нашел это:
Как вы видите сейчас, есть инструкция вызова, тогда как я ожидал только простой JMP. Я не понимаю, почему использование переменной 8 байтов отключает рекурсию хвоста. Почему компилятор не выполняет оптимизацию в этом случае?
