プログラムdeタマゴ

nodamushiの著作物は、文章、画像、プログラムにかかわらず全てUnlicenseです

Java 末尾再帰VS普通の再帰

ちょっと気になったんで、実験してみた。
Lispの方言の一つschemeを使い始めてからは、基本的に私は再帰呼び出しの書き方が末尾再帰で書く様になったんだけど、よくよく思い返してみればJavaでデバッグするときにスタック破棄されてない様な……。スタックが破棄されないんだったら末尾再帰する意味なんて無いんだど。
というわけで、実験してみた。(コード↓*1

public static void main(String[] args) {
    int i=0;
    long time = System.currentTimeMillis();
    while(i<100000){
        loop1(1000);
        i++;
    }
    long time = System.currentTimeMillis()-time;
    i=0;
    time2 = System.currentTimeMillis();
    while(i<100000){
        loop2(1000,0);
        i++;
    }
    time2 = System.currentTimeMillis()-time2;
    System.out.printf("%d %d \n",time,time2);
}

//普通の再起
public static int loop1(int k){
    if(k ==0)return 1;
    else return loop1(k-1)+1;
}

//末尾再起
public static int loop2(int k,int sum){
    if(k==0)return sum+1;
    else return loop2(k-1,sum+1);
}


で、結果は
172 203


この結果では、Javaは末尾再帰呼び出しをすると遅い。
引数の数の差が速度の差になったのだろうと思う。
ちなみに、loop2(100000,0)などと呼び出すとエラーが出る。やっぱりスタックは破棄されていない。

実際にはこんなものfor文なりを使えばいいから問題ないのだが、呼び出す関数は同じでもオブジェクトが違う場合は(これを再帰とは言わないのかも知れないが)末尾再帰の形にしない方がパフォーマンスは上がるのかも知れない。

ちなみに、こんな記事がありました。
Javaコードの診断: Javaコードのパフォーマンスを向上させる

記事の言っていることは分かるけど、実行時にスタックオーバーフロー起きないよう末尾再帰時のスタック管理ぐらいは最適化しても良いんじゃないかなぁ、とか思ったり。

*1:実際にはJavaが安定するまでの時間を考慮して、最初に処理を待つ処理がありますが、わかりやすさのため削りました。