5

第一次在这里发帖，我希望这个问题是可以接受的。

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

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

然而，在计算 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;
}

谢谢您的考虑。

4

3 回答 3

9

递归版本计算 5 * (4 * (3 * (2 * 1)))

迭代版本计算 1 * (2 * (3 * (4 * 5)))

运算顺序的不同会改变浮点算术的四舍五入方式，从而产生不同的结果。

于 2013-04-08T07:15:23.517 回答
5

该类型double不是精确类型。它有望成为正确值的近似值。

因此，不能保证这两种实现都是准确的。

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

  1. 您正在以不同的方式订购乘法。
  2. 您的迭代版本在同一个变量中执行所有数学运算。与 Intel 兼容的架构（x86 和 x86-64）在其浮点寄存器中使用80 位精度，并且该精度一直保持到寄存器存储到内存中为止。
于 2013-04-08T07:20:32.900 回答
2

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

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

于 2013-04-08T07:15:59.760 回答