8

在玩尾递归示例时，我注意到正常递归调用和尾递归调用的结果之间存在细微差异：

scala> def fact(n: Int): Double = if(n < 1) 1 else n * fact(n - 1)
fact: (n: Int)Double

scala> fact(30)
res31: Double = 2.6525285981219103E32

scala> @tailrec def fact(n: Int, acc: Double = 1): Double = if(n < 1) acc else fact(n - 1, n * acc)
fact: (n: Int, acc: Double)Double

scala> fact(30)
res32: Double = 2.652528598121911E32

只是出于好奇，有人可以向我解释为什么或在哪里进行舍入。我的猜测是，因为 Scala 编译器将尾递归版本转换为循环，所以acc在循环的每次迭代中都会分配参数，并且小的舍入误差会滑入其中。

4

3 回答 3

15

结果是不同的，因为两个版本以不同的顺序进行乘法运算，从而导致不同的舍入。

正常的递归调用会导致一个表达式n*([n-1]*([n-2]*(...)))，因为您首先计算 fact(n-1) 的值，然后将其与 n 相乘，而尾递归调用会导致((n*[n-1])*[n-2])*...您首先乘以 n，然后迭代到 n-1 .

尝试重写其中一个版本，使其以另一种方式迭代，从理论上讲，您应该得到相同的答案。

于 2012-08-06T13:52:09.880 回答
9

您的两个函数没有按相同的顺序执行操作。

在 C 中：

int main(int c, char **v)
{
  printf ("%.16e %.16e\n", 
      30.*29*28*27*26*25*24*23*22*21*20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2,
      2.*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29*30);
}

印刷：

2.6525285981219110e+32 2.6525285981219103e+32

（我使用了一个平台，C 中的浮点可以在其上工作）

您的函数的一个版本计算30.*29*...，另一个计算2.*3*...。这两个结果略有不同是正常的：浮点运算不是关联的。但请注意，结果没有什么深不可测的。您的一个函数精确计算IEEE 754 双精度表达式30.*29*...，另一个精确 2.*3*...计算. 它们都按设计工作。

如果我不得不猜测，我希望它2.*3*...更准确（更接近用实数获得的结果），但这并不重要：这两个数字非常接近并且非常接近真实结果。

于 2012-08-06T13:51:04.213 回答
6

不同之处不在于 Scala 将尾递归变成了循环。如果没有优化，结果将是相同的。此外，在舍入误差方面，递归的作用与循环的作用没有什么不同。

不同之处在于数字相乘的顺序。您的第一个解决方案在开始乘以数字之前一直递归到 1。所以它最终会计算n * ( (n - 1) * (... * (2 * 1)))。尾递归版本立即开始相乘，因此最终计算n * (n-1) * ... * 2 * 1.

当然，通常我们会说这两个是相同的，因为乘法是关联的，但对于浮点算术却不是这样。使用浮点数(x * y) * z可能会非常不同，x * (y * z)因为舍入误差的传播方式不同。所以这解释了你的行为。

请注意，当使用从 1 到 n 计数的 for 循环与从 n 到 1 计数的 for 循环来实现阶乘时，您会看到相同的差异。

于 2012-08-06T13:52:45.653 回答