scala - 为什么这个函数不是尾递归的？

Question

我为帕斯卡三角形编写了以下函数。为什么打电话

pascal_cont(a-1, b-1, (x:Int) => pascal_cont(a, b-1, (y:Int) => cont(x + y)))

不是尾递归吗？

def pascal(c: Int, r: Int): Int = {
  def pascal_cont(a:Int, b:Int, cont: (Int) => Int): Int = {
    if (a==0 || a==b) cont(1)
    else pascal_cont(a-1, b-1, (x:Int) => pascal_cont(a, b-1, (y:Int) => cont(x + y)))        
  }

  pascal_cont(c,r,n => n)  
}

Answer 1

如果@tailrec在函数上添加注释，pascal_cont您将收到以下错误：

[error] ....scala:18: could not optimize @tailrec annotated method pascal_cont: it contains a recursive call not in tail position
[error]         pascal_cont(a-1, b-1, (x:Int) => pascal_cont(a, b-1, (y:Int)=> cont (x + y)))
[error]                                                     ^
[error] one error found

所以 lambda 表达式内部的调用不在尾部位置，这就是它不是尾部递归的原因

Answer 2

Scala 编译器无法优化任何（理论上）尾递归函数，因为它将它们转换为 while 循环。例如，它也无法优化相互尾递归函数。您可以使用蹦床模式来缓解这种情况。

在 Scala 中，scala.util.control.TailCalls包含必要的实用程序。这将变成：

def pascal(c: Int, r: Int): Int = {
  import scala.util.control.TailCalls._

  def pascal_cont(a:Int, b:Int, cont: (Int) => TailRec[Int]): TailRec[Int] = {
    if (a==0 || a==b) cont(1)
    else tailcall {
      pascal_cont(a-1, b-1, (x:Int) =>
        pascal_cont(a, b-1, (y:Int) => cont(x + y)))
    }
  }

  pascal_cont(c,r,n => done(n)).result
}