2

如果我运行以下代码：

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 递归版本耗时 5803 毫秒。1134903170 迭代版本耗时 0 毫秒。

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

注意我使用的是 Oracle JDK 1.7

4

4 回答 4

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

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

您可以查看此页面，了解如何使用尾调用优化编写递归斐波那契求解器。

于 2013-01-12T15:11:13.160 回答
5

正如其他答案所述，您的函数不是尾递归的，这是斐波那契的尾递归版本：

long fibonacci(int n) {
    if (n == 0)
        return 0;
    else
        return fibonacciTail(n, 1, 0, 1);
}

long fibonacciTail(int n, int m, long fibPrev, long fibCurrent) {
    if (n == m)
        return fibCurrent;
    else
        return fibonacciTail(n, m + 1, fibCurrent, fibPrev + fibCurrent);
}

此外，JVM 不进行尾调用优化，因此将为每个递归调用分配一个堆栈帧，这使得这是一个相当昂贵的操作。然而，重要的是要注意这在技术上是依赖于实现的，有关执行 TCO 的 IBM SDK 链接的评论，请参阅此SO 问题以获取更多信息。

一个优化的版本是手动进行尾调用优化，将上面的代码转换为带有变量重新分配的 while 循环：

long fibonacciIter(int n) {
    int m = 1;
    long fibPrev = 0;
    long fibCurrent = 1;
    while (n != m) {
        m = m + 1;
        int current = fibCurrent;
        fibCurrent = fibPrev + fibCurrent;
        fibPrev = current;
    }
    return fibCurrent;
}
于 2013-01-12T15:17:46.000 回答
1

在递归版本中，您正在递归地创建函数，这很昂贵，因为函数调用涉及将变量推入堆栈、堆栈管理等，而迭代在同一个堆栈上运行。

于 2013-01-12T15:11:42.053 回答
1

在递归代码中，调用次数与答案成正比，即 O(exp(n))

在迭代方法中，运行时间与它循环的次数成正比。在）

更糟糕的是，循环是比递归调用快得多的操作，因此即使相同迭代的订单仍然会快得多。

您可以像这样编写迭代 fib。

public static long iterativeFib(int n) { // no chance of taking a long
    long a = 0, b = 1;    
    while(n-- > 0) {
        long c = a + b;
        a = b;
        b = c;
    }
    return c;
}

有谁知道为什么运行如此缓慢？它只是一个写得不好的函数吗？

Java 不是一种函数式语言，它不进行尾调用优化。这意味着迭代通常比 Java 中的递归快得多。（有例外）

于 2013-01-12T16:08:38.063 回答