对于n > 2
,您的getSum(n)
递归调用会两次调用自身。这些调用中的每一个都可以进一步递归。方法调用的总数缩放为2^n
,并且2^50
是一个非常大的数字。这种糟糕的缩放比例反映了以下事实:简单的递归方法最终会不必要地多次重新计算相同的结果(例如fib(4)),这就是为什么您的程序随着速度的增加而如此之快地减速n
。
在某一点之后获得的负返回值是由于超出数据类型的限制引起的int
。您可能会使用更大的数据类型获得更大的限制long
。如果这还不够,那么您将需要执行像这样的操作BigInteger
,而这会大大降低性能。