java - java中斐波那契函数的尾调用优化

Question

我正在研究尾调用递归并发现了一些提到的文档。 Sun Java 没有实现尾调用优化。 我编写了以下代码以 3 种不同的方式计算斐波那契数: 1.迭代 2.头部递归 3.尾递归

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, 0, 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);
    }
}

在运行这个程序时我得出了一些结果:

1. 当 n>50 时，Head 递归方法没有完成。程序看起来像挂了。知道为什么会发生这种情况吗？
2. 与头递归相比，尾递归方法花费的时间要少得多。 有时比迭代方法花费的时间更少。是不是说java内部做了一些尾调用优化？ 如果是，为什么我在 n > 5000 时给出 StackOverflowError？

系统规范:

英特尔酷睿 5 处理器，

Windows XP,

32 位 Java 1.6

JVM 的默认堆栈大小。

Answer 1

Does it mean that java does some Tail call optimization internally?

不，它没有。 HotSpot JIT 编译器不实现尾调用优化。

您观察到的结果是您在未考虑 JVM 预热的 Java 基准测试中看到的典型异常。例如，调用方法的“前几次”，它将由解释器执行。然后 JIT 编译器将编译该方法……它会变得更快。

要获得有意义的结果，请围绕整个批处理进行循环并运行多次，直到时序稳定。然后丢弃早期迭代的结果。

... why I did it give StackOverflowError at n > 5000?

这只是没有发生任何尾调用优化的证据。