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

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

对于

n >2

，您的

getSum(n)

递归调用会两次调用自身。这些调用中的每一个都可以进一步递归。方法调用的总数缩放为

2^n

，并且

2^50

是一个非常大的数字。这种糟糕的缩放比例反映了以下事实：简单的递归方法最终会不必要地多次重新计算相同的结果（例如fib（4）），这就是为什么您的程序随着速度的增加而如此之快地减速

n

。

在某一点之后获得的负返回值是由于超出数据类型的限制引起的

int

。您可能会使用更大的数据类型获得更大的限制

long

。如果这还不够，那么您将需要执行像这样的 *** 作

BigInteger

，而这会大大降低性能。