时间戳

首页 > 解决方案 > 尾递归和按名称/值调用

scala - 尾递归和按名称/值调用

问题描述

学习 Scala 和函数式编程。在以下尾递归阶乘实现中：

def factorialTailRec(n: Int) : Int = {

    @tailrec
    def factorialRec(n: Int, f: => Int): Int = {
      if (n == 0) f else factorialRec(n - 1, n * f)
    }

    factorialRec(n, 1)
}

我想知道让第二个参数按值调用与按名称调用（正如我所做的那样）是否有任何好处。在第一种情况下，每个堆栈帧都承载着一个产品。在第二种情况下，如果我的理解是正确的，整个产品链将被转移到第 th 堆栈帧的情况下if ( n== 0)，n所以我们仍然必须执行相同数量的乘法运算。不幸的是，这不是 a^n 形式的乘积，可以通过重复平方以 log_2n 步计算，而是每次相差 1 的项的乘积。所以我看不到任何优化最终产品的可能方法：它仍然需要 O(n) 项的乘法。

这个对吗？就复杂性而言，按值调用是否等同于按名称调用？

标签： scalatail-recursioncallbynamecall-by-value

解决方案

让我稍微扩展一下您在评论中已经被告知的内容。这就是编译器对按名称参数进行去糖的方式：

@tailrec
def factorialTailRec(n: Int, f: => Int): Int = {
  if (n == 0) {
    val fEvaluated = f
    fEvaluated
  } else {
    val fEvaluated = f // <-- here we are going deeper into stack. 
    factorialTailRec(n - 1, n * fEvaluated)
  }
}

推荐阅读