いけむランド

はてダからやってきました

末尾再帰最適化

Scala で本当に末尾再帰がループに最適化されるかどうかを確認した。

% ls
Gcd.scala
% cat Gcd.scala
object Gcd {
  def gcd(a: Int, b: Int): Int = {
    if (b == 0)
      a
    else
      gcd(b, a % b)
  }
  def main(args: Array[String]) {
    Console.println("gcd(14, 21) = " + gcd(14, 21));
  }
}
% scalac -version
Scala compiler version 2.7.1.final -- Copyright 2002-2008, LAMP/EPFL
% scalac Gcd.scala
% ls
Gcd$.class  Gcd.class  Gcd.scala
% scala Gcd
gcd(14, 21) = 7
% javap -verbose Gcd\$
    :
    :
public int gcd(int, int);
  Code:
   Stack=3, Locals=4, Args_size=3
   0:   iload_2
   1:   iconst_0
   2:   if_icmpne       7
   5:   iload_1
   6:   ireturn
   7:   iload_2
   8:   iload_1
   9:   iload_2
   10:  irem
   11:  istore_2
   12:  istore_1
   13:  goto    0
  LineNumberTable: 
   line 3: 0
   line 4: 5
   line 2: 6
   line 6: 7

  LocalVariableTable: 
   Start  Length  Slot  Name   Signature
   0      16      0    this       LGcd$;
   0      16      1    a       I
   0      16      2    b       I
    :
    :


たしかにバイトコードでは再帰呼び出しではなく、先頭への goto になっている。