Разве это не хвост рекурсивный? (ошибка переполнения стека)
Это небольшая функция, которую я написал, чтобы проверить, является ли целое число простым или нет:
int prime(int x, int y = 2)
{
if(y <= x/2)
{
if((x % y) == 0)
return 0;
}
else
return 1;
return prime(x, ++y);
}
Теперь я компилирую его с Visual Studio 2012, и если я даю ему большое значение, такое как 105943, возникает ошибка переполнения стека, и код ломается. Теперь эта функция не является хвостовой рекурсивной? Если это так, то для рекурсивных вызовов не должен поддерживаться стек, и переполнение не должно происходить?
Что я не получаю здесь точно?
Решение
Это хвостовая рекурсивная функция, но никакой компилятор не требует оптимизации хвостовой рекурсии в цикле. Скорее всего, если у вас достаточно высокие уровни оптимизации, это будет сделано. Но это все.
LISP (и производные языки) — единственные, которые я знаю, где хвостовая рекурсия на самом деле является требованием реализации.
Другие решения
Других решений пока нет …