使用迭代和递归计算阶乘时的不同答案

Question

第一次在这里张贴海报，我希望这个问题是可以接受的。

作为一个小测试，我编写了一个使用迭代和递归计算数字阶乘的应用程序。这似乎工作正常，除非尝试计算大于24的数字的阶乘。

例如，当计算24的阶乘时，两种方法都给出了6204480173323941的正确答案。

然而，当计算25的阶乘时，答案不同。递归方法给出的答案为1.5511210043330986e 025，而迭代方法给出的答案为1.5511210043330984e 025。

根据Wolfram Alpha的说法，正确的答案应该与迭代方法相同，那么为什么函数之间存在差异呢？我问了我的同事，他们也无法解释这种行为。

#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;
}

谢谢您的考虑。

Answer 1

乘法的顺序不同，由于浮点舍入，给出不同的结果。

如果您将for循环更改为从1到i（而不是从i到1），您应该得到与递归版本相同的结果。

Answer 2

类型双不是精确类型。它promise是正确值的近似值。

因此，这两种实现都不能保证精确。

就您的实现而言，有两个因素可能会导致不同的答案。

1. 您对乘法的排序不同
2. 迭代版本在同一个变量中执行所有数学运算。与英特尔兼容的体系结构（x86和x86-64）在其浮点寄存器中使用80位精度，并且在寄存器存储到内存中之前一直保持该精度

Answer 3

递归版本计算5*（4*（3*（2*1）））

迭代版本计算1*（2*（3*（4*5）））

运算顺序的不同会改变浮点算术的循环方式，从而产生不同的结果。