0

学习 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) 项的乘法。

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

4

2 回答 2

2

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

@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)
  }
}
于 2019-06-04T10:04:30.833 回答
0

通过实验，我发现通过名称形式主义，该方法变成......非尾递归！我制作了这个示例代码来比较阶乘尾递归和阶乘非尾递归：

 package example

 import scala.annotation.tailrec

 object Factorial extends App {

  val ITERS = 100000

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

  for(i <-1 to ITERS) println("factorialTailRec(" + i + ") = " + factorialTailRec(i))


  def factorial(n:Int) : Int = {
    if(n == 0) 1 else n * factorial(n-1)
  }

  for(i <-1 to ITERS) println("factorial(" + i + ") = " + factorial(i))

}

观察内部tailRec函数按名称调用第二个参数。 注释仍然@tailRec不会引发编译时错误！

我一直在玩弄ITERS变量的不同值，对于 100,000 的值，我收到了... StackOverflowError！

尾递归方法中的堆栈溢出错误

（零的结果是因为溢出Int。）

所以我继续将 , 的签名更改factorialTailRec/2为：

def factorialTailRec(n: Int, f: Int): Int

即按值调用参数f。这一次，main运行的部分factorialTailRec完成得非常好，而当然，factorial/1以完全相同的整数崩溃。

非常非常有趣。似乎在这种情况下按名称调用会维护堆栈帧，因为需要计算产品本身一直到调用链。

于 2019-06-04T01:23:00.653 回答