Впервые постер здесь, я надеюсь, что этот вопрос приемлем.
В качестве небольшого теста я написал приложение, которое вычисляет факториал числа, используя итерацию и рекурсию. Казалось, это работает нормально, за исключением случаев, когда вы пытаетесь вычислить факториал для чисел больше 24.
Например, при расчете факториала 24 оба метода дают правильный ответ 62044840173323941.
Однако при расчете факториала 25 ответы различаются. Рекурсивный метод дает ответ как 1.5511210043330986e + 025, в то время как итерационный метод дает ответ как 1.5511210043330984e + 025.
Согласно Вольфраму Альфе, правильный ответ должен быть таким же, как итерационный метод, так почему же расхождение между функциями? Я спросил своих коллег, и они также не могут объяснить поведение.
#define TEST_CASE 25
double GetFactorialRecursive(double i)
{
if (i == 1)
return i;
else
return i * GetFactorialRecursive(i - 1);
}
double GetFactorialIterative(double i)
{
double result = 1.0;
for (; i > 0; --i)
result *= i;
return result;
}
int main ()
{
double recres = 0, itrres = 0;
recres = GetFactorialRecursive(TEST_CASE);
itrres = GetFactorialIterative(TEST_CASE);
if (recres != itrres)
std::cout << "Error" << "\n";
std::cout << std::setprecision(25) << "Recursion: " << recres << ", Iteration: " << itrres << "\n";
return 0;
}
Спасибо за ваше внимание.
Рекурсивная версия рассчитывает 5 * (4 * (3 * (2 * 1)))
Итерационная версия рассчитывает 1 * (2 * (3 * (4 * 5)))
Разница в порядке операций меняет порядок округления арифметики с плавающей запятой, что приводит к другому результату.
Тип double
является не точный тип. Это обещает быть приближенным к правильному значению.
Таким образом, обе реализации не гарантируются быть точными.
Что касается ваших реализаций, то есть два факторы, которые мог вызвать разные ответы.
Порядок умножений различен, что дает разные результаты из-за округления с плавающей точкой.
Если вы измените for
цикл, чтобы идти от 1
в i
(а не из i
в 1
), вы должны получить тот же результат, что и в рекурсивной версии.