JVMは最後の再帰を最適化しているかどうか

1841 ワード

JVMは、最後の再帰を最適化していますか?
いくつかのブログを見て、ないと言って、JDK 8の下でテストをしました.
package fibonicc;

public class Test {
    //1 1 2 3 5 8
    private static int fibonicc(int n) {
        if(n<=1) {
            return 1;
        }
        return fibonicc(n-1)+fibonicc(n-2);
    }
    
    //n   n=1 
    private static int fibonicc2(int n,int last,int total) {
        if(n==1) {
            return total;
        }
        return fibonicc2(n-1,total,last+total);
    }
    //     
    private static int fibonicc3(int n) {
        if(n<=1) {
            return 1;
        }
        int last = 1;
        int current = 1;
        int i=2;
        int tmp = current;
        while(i++<=n) {
            tmp = current;
            current = last+current;
            last = tmp;
        }
        return current;
    }
    
    private static int fibonicc4(int n,int last,int total) {
        if(n==1) {
            return total;
        }
        int result = fibonicc4(n-1,total,last+total);
        return result;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
//      System.out.println(fibonicc(50));
        long start = (System.nanoTime());
        System.out.println(fibonicc2(5000,1,1));
        System.out.println(System.nanoTime()-start);
        start = (System.nanoTime());
        System.out.println(fibonicc3(5000));
        System.out.println(System.nanoTime()-start);
        start = (System.nanoTime());
        System.out.println(fibonicc4(5000,1,1));
        System.out.println(System.nanoTime()-start);
    }

}


fiboniccは普通の再帰で、遅いです.
fibonicc 2はテール再帰実装であり、fibonicc 2(5000,1,1)は通常の再帰よりも1092785ナノ秒かかります.
fibonicc 3はサイクル実装であり、fibonicc 3(5000)は419347ナノ秒かかり、テール再帰よりも速い.
fibonicc 4はfobonicc 2の時間複雑度と一致する非テール調であり,1132819時間かかり,テール再帰との時間差は多くないようである.