Java中的斐波那契序列花费太长时间？

Question

我试图在Java中找到斐波那契数列的总和，但是运行时间太长了（或者应该吗？）。每当我使用40以上的整数时，这都会减慢速度。

注意：在50时，返回的负值使我感到困惑。

有什么建议吗？

public static void main(String[] args) {        
    //Find Fibonacci sequence
    int sum=getSum(50);
    System.out.println("Sum of Fibonacci Numbers is " + sum); 
}
static int getSum(int n){
    if (n==0) return 0;
    if (n==1 || n==2) return 1;
    else return getSum(n-1) + getSum(n-2);
}

Answer 1

对于n > 2，您的getSum(n)递归调用会两次调用自身。这些调用中的每一个都可以进一步递归。方法调用的总数缩放为2^n，并且2^50是一个非常大的数字。这种糟糕的缩放比例反映了以下事实：简单的递归方法最终会不必要地多次重新计算相同的结果（例如fib（4）），这就是为什么您的程序随着速度的增加而如此之快地减速n。

在某一点之后获得的负返回值是由于超出数据类型的限制引起的int。您可能会使用更大的数据类型获得更大的限制long。如果这还不够，那么您将需要执行像这样的操作BigInteger，而这会大大降低性能。