プログラミング雑記

プログラミングの雑記です。

末端再帰

  • 末端再帰に持ち込めれば、「whileループによる実装と同じパフォーマンスまで最適化」を受けることができる。
  • 末端再帰の最適化をオフにするコンパイラオプションは、 -g:notailcalls
  • ただし、Scalaの現状の最適化は、「同じメソッドに対して関数オブジェクト等を利用しないで末端再帰した場合のみ」行われる
object Main extends App {

  // count == 1
  try {
    tailRecursive()
  } catch {
    case ex: Exception =>
      val count = ex.getStackTrace
        .map {
          _.getMethodName
        }.count(_.contains("tailRecursive"))
      println(count)
  }

  // count == 11
  try {
    tailRecursiveNo()
  } catch {
    case ex: Exception =>
      val count = ex.getStackTrace
        .map {
          _.getMethodName
        }.count(_.contains("tailRecursive"))
      println(count)
  }

  class Marker(count_ : Int) {
    val count: Int = count_
  }
  def tailRecursive(marker: Marker = new Marker(0)): Marker = {
    if (marker.count >= 10) { throw new Exception() }
    else { tailRecursive(new Marker(marker.count + 1)) }
  }
  def tailRecursiveNo(marker: Marker = new Marker(0)): Marker = {
    if (marker.count >= 10) { throw new Exception() }
    else {
      val result = tailRecursiveNo(new Marker(marker.count + 1))
      result
    }
  }
}