Tail call optimization of Fibonacci function in Java

I'm studying tail call recursion and found some of the documents mentioned Sun Java does not perform tail call optimization

public class Fibonacci {
    public static void main(String[] args) throws InterruptedException {
        int n = Integer.parseInt(args[0]);
        System.out.println("\n Value of n : " + n);
        System.out.println("\n Using Iteration : ");
        long l1 = System.nanoTime();
        fibonacciIterative(n);
        long l2 = System.nanoTime();
        System.out.println("iterative time = " + (l2 - l1));
        System.out.println(fibonacciIterative(n));

        System.out.println("\n Using Tail recursion : ");
        long l3 = System.nanoTime();
        fibonacciTail(n);
        long l4 = System.nanoTime();
        System.out.println("Tail recursive time = " + (l4 - l3));
        System.out.println(fibonacciTail(n));

        System.out.println("\n Using Recursion : ");
        long l5 = System.nanoTime();
        fibonacciRecursive(n);
        long l6 = System.nanoTime();
        System.out.println("Head recursive time = " + (l6 - l5));
    }

    private static long fibonacciRecursive(int num) {
        if (num == 0) {
            return 0L;
        }
        if (num == 1) {
            return 1L;
        }
        return fibonacciRecursive(num - 1) + fibonacciRecursive(num - 2);
    }

    private static long fibonacciIterative(int n) throws InterruptedException {
        long[] arr = new long[n + 1];
        arr[0] = 0;
        arr[1] = 1;
        for (int i = 2; i <= n; i++) {
            // Thread.sleep(1);
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[n];
    }

    private static long fibonacciTail(int n) {
        if (n == 0)
            return 0;
        return fibHelper(n,1,1);
    }

    private static long fibHelper(int n,int m,long fibM_minus_one,long fibM) {
        if (n == m)
            return fibM;
        return fibHelper(n,m + 1,fibM,fibM_minus_one + fibM);
    }
}

When running this program, I put forward some results:

>The head recursion method cannot be completed when n > 50 The program seems to hang up Any idea, why does this happen? Compared with head recursion, tail recursion takes much less time Sometimes it takes less time than iterative methods Does this mean that Java performs some tail call optimization internally? If so, why do I give stackoverflowerror 5000 under N >?

System specification:

Intel Core 5 processor,

Windows XP,

32-bit Java 1.6

The default stack size of the JVM

Solution

No, No The hotspot JIT compiler does not implement tail call optimization

The result you are observing is a typical value of an exception that you see in a Java benchmark that does not consider JVM warm - up For example, the "first few" times of a method call will be executed by the interpreter Then the JIT compiler will compile the method... It will get faster

To get meaningful results, run the cycle around the whole cycle until the time is stable The results of earlier iterations are then discarded

This just proves that no tail optimization occurs