java中的fibonacci函数的尾调用优化

Question

我正在研究Tail调用递归,并且遇到了一些提到的文档.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 Recursive方法无法完成.程序看起来像被绞死了.任何想法,为什么会发生这种情况？
2. 与Head递归相比,Tail递归方法花费的时间要少得多.有时甚至比迭代方法花费的时间更少.这是否意味着java在内部进行了一些Tail调用优化？如果确实如此,为什么我这样做会给n> 5000的StackOverflowError？

系统规格:

英特尔酷睿5处理器

Windows XP,

32位Java 1.6

JVM的默认堆栈大小.

Answer 1

这是否意味着java在内部进行了一些Tail调用优化？

不,不是的.HotSpot JIT编译器不实现尾调用优化.

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

为了获得有意义的结果,在整个批次周围放置一个循环并运行它多次,直到时间稳定.然后丢弃早期迭代的结果.

...为什么我这样做会给n> 5000的StackOverflowError？

这只是证据表明没有任何尾调用优化发生.

Answer 2

对于第一个问题，2^50（或接近的值）是多少？递归 Fib 函数中的每个数字 N 都会调用它两次（之前的 2 次）。其中每一个都调用 2 个先前的迭代，等等......因此它会增长到 2^(Nk) 的递归（k 可能是 2 或 3）。

第二个问题是因为第二个问题是直N递归。它不是双头的(N-1),(N-2)，而是简单地从 M=1、M=2...M=N 开始构建。每一步都会保留 N-1 值用于相加。由于它是 O(N) 操作，因此它与迭代方法相当，唯一的区别在于 JIT 编译器如何优化它。不过，递归的问题在于，堆栈到帧上的每个级别都需要巨大的内存占用 - 在某些限制下，您会耗尽内存或堆栈空间。 它通常仍然比迭代方法慢。