Scala の末尾再帰の最適化を確認する

Scala の末尾再帰の最適化を確認してみた。
まず、実験につかったソースコード (java と scala) を示し、それぞれを走らせた結果をします。

$ cat SumJava.java
// See http://d.hatena.ne.jp/unageanu/20080504/1209870210

class SumJava {

    // 1から引数までの総和を計算する関数
    // 末尾再帰でない版
    static long sum( long i ) {   
    return (i == 0) ? i : i + sum(i - 1);
    }

    // 1から引数までの総和を計算する関数
    // 末尾再帰版
    static long sumTailCalls( long i ) {
    return _sumTailCalls( i, 0 );
    }
    static long _sumTailCalls( long i, long total ) {
    return i == 0 ? total  : _sumTailCalls( i - 1, total + i );
    }

    // メイン
    public static void main( String[] args ) {
    long[] params = { 4, 100, 1000, 10000, 100000, 1000000 };

    for(long i : params) {
        try {
        System.out.println( "Sum( " + i + " ) = " + sumTailCalls(i) );
        System.out.println( "Sum( " + i + " ) = " + sum(i) );
        } catch (Throwable th) {
        System.out.println(th.getClass().getName());
        }
    }   
    }
}

$ cat SumScala.scala
// See http://d.hatena.ne.jp/unageanu/20080504/1209870210

object SumScala {
  // 1から引数までの総和を計算する関数
  // 末尾再帰でない版
  def sum( i :Long ) :Long = {
    if ( i == 0 ) i else i + sum(i - 1)
  }

  // 末尾再帰版
  def sumTailCalls( i :Long ) :Long = {
    def _sum( j :Long, total :Long ) :Long = {
      if ( j == 0 ) total else _sum( j - 1, total + j )
    }
    _sum( i, 0 )
  }

  def main(args :Array[String]) {
    val params = List(4, 100, 1000, 10000, 100000, 1000000)
    params.foreach { i =>
      try {
    Console.println( "Sum( " + i + " ) = " + sumTailCalls(i))
    Console.println( "Sum( " + i + " ) = " + sum(i) )
      } catch {
    case th: Throwable => Console.println( th )
      }
    }
  }
}

コンパイルして走らせよう。

$javac SumJava.java
$ java -cp . SumJava
Sum( 4 ) = 10
Sum( 4 ) = 10
Sum( 100 ) = 5050
Sum( 100 ) = 5050
Sum( 1000 ) = 500500
Sum( 1000 ) = 500500
java.lang.StackOverflowError
java.lang.StackOverflowError
java.lang.StackOverflowError

java では 1...10000 以上は再帰呼び出しが深くなりすぎて スタックオーバーフローとなってしまう。
(末尾再帰かどうかには関係なく)

$ scalac SumScala.scala
$ scala SumScala
Sum( 4 ) = 10
Sum( 4 ) = 10
Sum( 100 ) = 5050
Sum( 100 ) = 5050
Sum( 1000 ) = 500500
Sum( 1000 ) = 500500
Sum( 10000 ) = 50005000
java.lang.StackOverflowError
Sum( 100000 ) = 5000050000
java.lang.StackOverflowError
Sum( 1000000 ) = 500000500000
java.lang.StackOverflowError

Scala では、末尾再帰の方法ではスタックオーバーフローが発生せずに 合計計算ができている。