java - 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 是一个非常大的数字。这种糟糕的缩放反射(reflect)了这样一个事实，即头脑简单的递归方法最终不必要地多次重新计算相同的结果(例如 fib(4))，这就是为什么你的程序随着你增加 n.

您在某个点后得到的负返回值是由于超出了数据类型int 的限制。您可以使用更广泛的数据类型获得更大的限制，大概是 long。如果这还不够，那么您将需要使用 BigInteger 之类的东西，这会导致性能大幅下降。