为什么我的正常递归和尾递归示例之间存在舍入差异? [英] Why is there a rounding difference between my normal recursion and tail recursion example?

问题描述

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

While toying with a tail recursion example I noticed a small discrepancy between the results of a normal recursive call and a tail recursive call:

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

Just out of curiosity, can someone please explain to me why or where the rounding is happening. My guess is that because the Scala compiler translates the tail recursive version to a loop, the acc parameter is assigned at each iteration of the loop, and that the small rounding error slips in there.

推荐答案

结果不同，因为两个版本的乘法顺序不同，导致舍入不同.

The result is different because the two versions do the multiplications in different order, thus leading to different rounding.

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

The normal recursive call leads to an expression n*([n-1]*([n-2]*(...))), because you first compute the value of fact(n-1) and then multiply it with n, whereas the tail recursive one leads to ((n*[n-1])*[n-2])*... because you first multiply by n and then iterate on to n-1.

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

Try rewriting one of the versions so that it iterates the other way and you should, theoretically, get the same answer.

这篇关于为什么我的正常递归和尾递归示例之间存在舍入差异?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！