読者です 読者をやめる 読者になる 読者になる

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

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を使ったループの方がすっきり書ける場合が多いみたいなので、「再帰でもループが書ける」くらいに思っておいた方がいいのかもしれない。