無視されやすいクラスメンバーメソッドの末尾再帰最適化制限

テール再帰とは,メソッドの再帰呼び出しがメソッド体の最後にある.scalaコンパイラは、最後に再帰するバイトコードをループ実行の形式に最適化するが、無視される可能性がある.まず例を見てみましょう.

class Approx {
  def isGoodEnough(guess: Double): Boolean =
    if (guess < 1) true
    else false

  def improve(guess: Double): Double = guess - 1

  @tailrec
  final def approximate(guess: Double): Double =
    if (isGoodEnough(guess)) guess
    else approximate(improve(guess))

  def approximateLoop(initialGuess: Double): Double = {
    var guess = initialGuess
    while (!isGoodEnough(guess))
      guess = improve(guess)
    guess
  }
}

object TailRecDemo {
  val app = new Approx()

  def main(args: Array[String]) = {
    println(System.getProperty("java.class.path"))
    recursive(1)
    iterate(1)
    recursive(10)
    iterate(10)
    recursive(100)
    iterate(100)
  }

  def recursive(n: Int) = {
    val start = java.lang.System.currentTimeMillis()
    for (i <- 0 to 10000000) {
      app.approximate(n)
    }
    println(java.lang.System.currentTimeMillis() - start)
  }

  def iterate(n: Int) = {
    val start = java.lang.System.currentTimeMillis()
    for (i <- 0 to 10000000) {
      app.approximateLoop(n)
    }
    println(java.lang.System.currentTimeMillis() - start)
  }

}

以下に実行結果を示すと,再帰呼び出しの方式はループ方式よりもかなり遅く,回数が多ければ多いほど遅い幅が大きくなる傾向が見られる. 

922
969
2406
2032
13578
8047

approximateに@tailrecコメントを付けて再コンパイルします.コンパイラにエラーが発生しました.
  
error: could not optimize @tailrec annotated method approximate: it is neither private nor final so can be overridden def approximate(guess: Double): Double =
元はclassで定義された関数についてfinalまたはprivateとして宣言されていない場合、コンパイラはテール再帰を最適化しません.
Scalaはテール再帰の最適化に多くの制限があり、例えば再帰は直接再帰で間接的ではなく、関数オブジェクト呼び出しによる再帰ではなく、scalaがこれらの制限を突破できれば、それは非常に心を奮い立たせることである.