S-JIS[2011-02-24] 変更履歴
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ループでコーディングすればいいじゃん、と思わなくもないのだが(苦笑)