Scala,尾递归与非尾递归递归,为什么尾递归较慢？

发布时间：2020-12-16 19:00:52 所属栏目：安全来源：网络整理

导读：我正在解释一个朋友,我预计 Scala中的非尾递归函数比尾递归慢,所以我决定验证它. 我写了一个很好的旧阶乘函数,并尝试比较结果.以下是代码： def main(args: Array[String]): Unit = { val N = 2000 // not too much or else stackoverflows var spent1: Long

我正在解释一个朋友,我预计 Scala中的非尾递归函数比尾递归慢,所以我决定验证它.
我写了一个很好的旧阶乘函数,并尝试比较结果.以下是代码：

def main(args: Array[String]): Unit = {
  val N = 2000 // not too much or else stackoverflows
  var spent1: Long = 0
  var spent2: Long = 0
  for ( i <- 1 to 100 ) { // repeat to average the results
    val t0 = System.nanoTime
    factorial(N)
    val t1 = System.nanoTime
    tailRecFact(N)
    val t2 = System.nanoTime
    spent1 += t1 - t0
    spent2 += t2 - t1
  }
  println(spent1/1000000f) // get milliseconds
  println(spent2/1000000f)
}

@tailrec
def tailRecFact(n: BigInt,s: BigInt = 1): BigInt = if (n == 1) s else tailRecFact(n - 1,s * n)

def factorial(n: BigInt): BigInt = if (n == 1) 1 else n * factorial(n - 1)

结果令我困惑,我得到这样的输出：

578.2985

870.22125

意义非尾递归函数比尾递归函数快30％,操作次数相同！

什么会解释这些结果？

解决方法

除了@monkjack显示的问题(即,乘小*大比大*小,这确实占了更大的差异),您的算法在每种情况下是不同的,所以它们并不是真正的可比性.

在尾递归版本中,您将会从大到小的方式：

n * n-1 * n-2 * ... * 2 * 1

在非尾递归版本中,您将从小到大的倍数：

n * (n-1 * (n-2 * (... * (2 * 1))))

如果您改变了尾递归版本,使其从小到大增加：

def tailRecFact2(n: BigInt) = {
  def loop(x: BigInt,out: BigInt): BigInt =
    if (x > n) out else loop(x + 1,x * out)
  loop(1,1)
}

那么尾递归比正常递归快约20％,而不是10％,因为如果你只是做出monkjack的修正.这是因为将BigInts加在一起比乘以大的BigInts快.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!