Scalaって末尾再帰の最適化してるの?
Scalaの勉強中。
Scalaはオブジェクト指向でありながら、関数的にもプログラムを書けるという特徴を持っているとのことで、「だったら末尾再帰は最適化されるよね?」ってことでバイトコードがどうなってるのか調べてみた。
結論からいえば、d:id:mzp:20081112:factでも言われてるとおり、末尾最適化はされるらしい。
たとえば、
object TailCallTest { def fact(n: Int, a: Int): Int = { if (n == 0) a else fact(n - 1, a * n) } def main(args: Array[String]) { val n = args(0).toInt println("fact(" + n + ") = " + fact(n, 1)) } }
というコードを書く。factは末尾再帰になっていることに注意。
これをコンパイルする。
fsc TailCallTest.scala
.classファイルが2つできるのだけど、そのうち$がついてるほうを
javap -c TailCallTest$
で確認してみると、factに該当する部分は
public int fact(int, int); Code: 0: iload_1 1: iconst_0 2: if_icmpne 7 5: iload_2 6: ireturn 7: iload_1 8: iconst_1 9: isub 10: iload_2 11: iload_1 12: imul 13: istore_2 14: istore_1 15: goto 0
と、たしかにループになっている。素晴らしい。
ただし、すべての末尾呼び出しが最適化されるわけではないらしい。まぁ、普通のメソッド呼び出しはinvokevirtualにコンパイルされるようだし、当たり前といえば当たり前か。そんなわけで、相互再帰とかを書いてしまうと最適化してくれない。
と、ここまで書いてきたけど、ここのコメント欄でも言われてるように、Scalaならforを使ったループの方がすっきり書ける場合が多いみたいなので、「再帰でもループが書ける」くらいに思っておいた方がいいのかもしれない。