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

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
}