Scalaって末尾再帰の最適化してるの?

30分プログラム、その412。id:athosがScalaが末尾再帰の最適化してるか気にしてたのでコードを書いて確かめてみた。
ちなみに、id:athosはjavapで逆コンパイルしてみてgotoになっていることを確認したらしい。

使い方

// 末尾再帰じゃないやつはスタックオーバーフローする
scala> check(fact,10)
res21: Int = 1000000

// 末尾再帰版ならオーバーフローしない
// でもIntの範囲を越えるので0になる
scala> fact_iter(1000000)
res22: Int = 0

ソースコード

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

def fact_iter(n: Int) : Int = {
  def loop(m : Int,n : Int) : Int = {
    if(n == 0){
      m
    }else{
      loop(n*m,n-1)
    }
  }
  loop(1,n)
}

def check(f : Int => Int,n : Int) : Int ={
  val res : Option[Int] = try{
    f(n)
    None
  }catch{
    case e : java.lang.StackOverflowError =>
      Some(n)
  }
  res match {
    case None =>
      check(f,n*10)
    case Some(n) =>
      n
  }
}

参考

• 過去の30分プログラム