java - 两种不同的递归方式

我用两种不同的方法计算斐波纳契排。为什么fib1比fib2执行得长？

public class RecursionTest {

    @Test
    public void fib1() {
        long t = System.currentTimeMillis();

        long fib = fib1(47);

        System.out.println(fib + "  Completed fib1 in:" + (System.currentTimeMillis() - t));

        t = System.currentTimeMillis();

        fib = fib2(47);

        System.out.println(fib + "  Completed fib2 in:" + (System.currentTimeMillis() - t));

    }


    long fib1(int n) {
        if (n == 0 || n == 1) {
            return n;
        } else {
            return fib1(n - 1) + fib1(n - 2);
        }
    }


    long fib2(int n) {
        return n == 0 ? 0 : fib2x(n, 0, 1);
    }

    long fib2x(int n, long p0, long p1) {
        return n == 1 ? p1 : fib2x(n - 1, p1, p0 + p1);
    }
}

输出：

2971215073  Completed fib1 in:17414
2971215073  Completed fib2 in:0

最佳答案

因为两种算法的工作原理完全不同让我用fib（5）给你看这个。
如果您调用fib1（5），它在内部调用fib1（4）和fib1（3），让我们用树来可视化：
纤维板（5）
/ \
纤维（4）纤维（3）
现在，fib（4）内部称为fib（3）和fib（2）。
现在我们有了这个：
纤维板（5）
/\
纤维（4）纤维（3）
/\/\
腓（3）腓（2）腓（2）腓（1）
我想现在已经很明显了，剩下的你应该可以填了。
编辑：另一件你应该注意的事情是，它实际上必须多次执行相同的计算。在这张图中，fib（2）和fib（3）都被多次调用。如果起始数字越大，情况就越糟。/编辑
现在，让我们看看fib2（5）如果你用0来调用它，它返回0否则，它调用fib2x（n，0，1）
所以，我们要调用fib2x（5,0,1）。fib2x（n，0，1）现在内部调用fib2x（n-1，p1，p0+p1）等等。
所以，让我们看看：
fib2x（5，0，1）=>fib2x（4，1，1）=>fib2x（3，1，2）=>fib2x（2，2，3）=>fib2x（1，3，5）
到那时，它已经达到返回条件并返回5。
所以，你的算法完全不同第一个递归地从上到下工作。
第二个从1开始往上爬实际上，它比递归的迭代性更强（可能是递归编写的）。它保留已计算的值，而不是丢弃它们，因此需要调用的计算要少得多。

关于java - 两种不同的递归方式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10936405/