java - 为什么这个递归斐波那契函数运行得如此糟糕？

Question

如果我运行以下代码:

public static void main(String[] argsv) {

    long whichFib = 45;
    long st;
    st = System.currentTimeMillis();
    System.out.println(recursiveFib(whichFib));
    System.out.println("Recursive version took " + (System.currentTimeMillis() - st) + " milliseconds.");

    st = System.currentTimeMillis();
    System.out.println(iterativeFib(whichFib));
    System.out.println("Iterative version took " + (System.currentTimeMillis() - st) + " milliseconds.");

}

public static long recursiveFib(long n) {

    if (n == 0)
        return 0;
    if (n == 1 || n == 2)
        return 1;

    return recFib(n - 1) + recFib(n - 2);
}

public static long iterativeFib(long n) {

    if (n == 0)
        return 0;
    else if (n == 1 || n == 2)
        return 1;

    long sum = 1;
    long p = 1;
    long u = 1;

    for (int i = 2; i < n; i++) {
        sum = p + u;
        p = u;
        u = sum;
    }

    return sum;
}

我得到以下输出:

1134903170 Recursive version took 5803 milliseconds. 1134903170 Iterative version took 0 milliseconds.

我觉得我在这里做错了什么。我认为编译器会优化尾部调用(递归斐波那契方法中的最后一行)，使其速度更接近迭代版本。有谁知道为什么运行这么慢？它只是一个写得不好的函数吗？

注意我正在使用 Oracle JDK 1.7

Answer 1

return recFib(n - 1) + recFib(n - 2);

由于您正在进行两次递归调用，而不是一次，因此编译器不太可能进行传统的尾调用优化。

你可以查看 this page有关如何使用尾调用优化编写递归 Fibonacci 求解器的想法。