再帰関数には @tailrec アノテーションを

Scala

　Scala東北のMLに流れてきた記事です。後で読み返し易いようにここにもメモしておきます。

　非関数型言語に慣れ親しんだ身としては、「while使わないで再帰関数使えよ」という関数型言語のスタンスを見ると真っ先に思いつくのが「言いたいことはわかるが、でかいループ回したらスタックオーバーフローするべ」ということです。

　しかし、Scalaをはじめとする関数型言語ではコンパイル時に再帰関数を最適化してスタックを使わないループ等にしてくれるそうでこの心配はないとのこと。ただし、これには条件があってScalaの場合

  • 自分自身を呼ぶ末尾再帰関数であること
  • 再帰関数が、オーバーライドされる可能性のないメソッドであること。つまりメソッドを定義するクラスが final であるかメソッド自体が final、あるいは private であること

末尾再帰関数というのは関数の最後の処理が再帰呼び出しになっているような関数のことです。

たとえば、1からnまでの数をすべて足した数を求める関数は以下のように定義できますが、これは末尾再帰関数ではありません。なぜなら、再帰呼び出しとしてsumを呼んだあとに、その結果とnを加算しているからです。

def sum(n: Int): Int = {
  if (n == 0)
    0
  else
    n + sum(n - 1)
}

println(sum(10))    // 55 と表示

以下のようにすると末尾再帰関数になります。

def sum(n: Int, total: Int): Int = {
  if (n == 0)
    total
  else
    sum(n - 1, n + total)
}

println(sum(10, 0))    // 55 と表示

　ということで、末尾再帰最適化を期待してるんだけど、何かとしくじって最適化されなくなっちゃった場合、でかいループをさせてスタックオーバーフローを起こすなどしない限りそれはなかなか見つけられないですよね。特にデータ数の少ないテスト環境では動いちゃって、本番で稼働させたらいきなり死んだ！なんてなったらかっこ悪すぎます。

　そこで、Scala 2.8では、@scala.annotaiton.tailrecアノテーションが追加されたそうです。これを末尾再帰最適化を期待するメソッドにつけとくと、最適化されないパターンだったときにコンパイラがエラーを吐いてくれるそうです。これは便利！ Scala 2.8 は今月中に正式リリースされるなんて噂を聞きますが、2.8に移行したら必ず使用したいですね！