为什么我的正常递归和尾递归示例之间存在舍入差异？

Question

在使用尾递归示例进行操作时,我注意到正常递归调用和尾递归调用的结果之间存在小的差异:

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在循环的每次迭代中都会分配参数,并且小的舍入错误会在那里滑动.

Answer 1

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

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

尝试重写其中一个版本,以便它以另一种方式迭代,理论上你应该得到相同的答案.

Answer 2

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

在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*...更准确(更接近用实数得到的结果),但没关系:这两个数字非常接近并且非常接近实际结果.

Answer 3

区别在于Scala将尾递归转换为循环的事实.没有优化,结果将是相同的.对于舍入错误而言,递归对循环的作用也不同.

差异是数字乘以的顺序.在开始乘以数字之前,您的第一个解决方案一直向下递归到1.所以它最终会计算出来n * ( (n - 1) * (... * (2 * 1))).尾递归版本立即开始相乘,因此它最终会计算出来n * (n-1) * ... * 2 * 1.

当然,通常我们会说这两个是相同的,因为乘法是关联的,但对浮点运算来说则不然.使用浮点(x * y) * z可能不同,x * (y * z)因为舍入错误的传播方式不同.这样就解释了你的行为.

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