S-JIS[2011-02-24] 変更履歴

Scala tailrecアノテーション

Scalaのtailrecアノテーションのメモ。

概要

scala.annotation.tailrecアノテーションは、末尾再帰でないメソッドの場合にコンパイルエラーにするアノテーション。

再帰するメソッド（自分自身を呼び出すメソッド）は、呼び出す回数が多くなるとその分スタックフレームを消費してしまう（最悪はOutOfMemoryErrorが発生する）が、
末尾再帰だと効率の良いループに変換してくれる。

tailrecアノテーションを付けておくと、誤って末尾再帰になっていない時にコンパイルエラーになってくれる。

例

@tailrecの使用例。

import scala.annotation.tailrec

メソッドが末尾再帰でないとコンパイルエラーになる。
（再帰呼び出し部分が呼び出した結果との演算になっていると、末尾再帰に出来ない）

scala> @tailrec
     | def f(n: Int): Int = {
     |   if (n <= 0) 0 else n + f(n-1)
     | }
<console>:11: error: could not optimize @tailrec annotated method: it contains a recursive call not in tail position
       def f(n: Int): Int = {
           ^

メソッドが末尾再帰なら何も起きない。

scala> @tailrec
     | def f(n: Int, s:Int = 0): Int = {
     |   if (n <= 0) s else f(n-1, s+n)
     | }
f: (n: Int,s: Int)Int

なお、通常のクラス内でメソッドを末尾再帰にしようとした場合、サブクラスでオーバーライドすると中身が変わってしまう可能性がある為、コンパイルエラーになる。
privateやfinalにすれば大丈夫らしい。

sample.scala:6: error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden
  def f(n: Int, s:Int = 0): Int = {
      ^

  @tailrec
  final def f(n: Int, s:Int = 0): Int = {
    if (n <= 0) s else f(n-1, s+n)
  }

あるいはメソッド内関数にしちゃうとか。（メソッド内の関数は、コンパイルすると通常のクラス内のprivate finalなメソッドとして定義される）

  def f(n: Int) = {

    @tailrec
    def tf(n: Int, s: Int): Int = {
      if (n <= 0) s else tf(n-1, s+n)
    }

    tf(n, 0)
  }

ちなみに、末尾再帰のメソッドは、コンパイルするとwhileループに置き換えられる。

  public final int f(int n, int s) {
    do {
      if (n <= 0) {
        return s;
      }
      s += n;
      n = n - 1;
    } while(true);
  }

だったら最初から（末尾再帰なメソッドを書くんじゃなくて）whileループでコーディングすればいいじゃん、と思わなくもないのだが(苦笑)