我试图在Java中找到Fibonacci序列的总和，但运行时间过长（或者假设为？）。每当我使用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);
}
对于n > 2，你的getSum(n)的调用递归地调用自己两次。每个调用都可以进一步递归。方法调用的总数称为2^n，而2^50是一个非常大的数字。这种不良的缩放反映了这样一个事实：简单的递归方法最终会不必要地重新计算相同的结果（例如fib（4））很多次，这就是为什么你的程序在增加n时会如此迅速地减速。
在某个点之后得到的负返回值来自超出数据类型int的限制。你可以用更广泛的数据类型获得更大的限制，大概是long。如果这还不够，那么你需要去像BigInteger这样的东西，这会带来很大的性能损失。
如果要计算第50个Fibonacci数，则需要使用long而不是int。第50个斐波纳契数是12586269025并超过int的最大值（见http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html）。
非递归算法可能会更快，请参阅http://planet.jboss.org/post/fibonacci_sequence_with_and_without_recursion了解不同的实现。
正如其他人已经说过的那样，你应该使用long来计算斐波纳契值，因为这个数字会非常快。
如果您的表格优先级是性能，您可以使用以下公式：
http://mathurl.com/kcjrbja.png 同
http://mathurl.com/q4r3qyv.png
（想法取自线性代数讲座，实际公式取自Wikipedia。） 这样，您将获得恒定时间内的第n个斐波那契数（取决于公式中第n个幂的计算）。
以下代码计算前93个数字的斐波纳契序列，没有等待时间（在我的机器上）：
private static final double SQRT_FIVE = Math.sqrt(5);
private static final double GOLDEN_RATIO = (1 + SQRT_FIVE) / 2;
public static void main(String[] args) {
for(int i = 0; i <= 92; i++) {
System.out.println("fib(" + i + ") = " + calculateFibonacci(i));
}
}
public static long calculateFibonacci(int n) {
double numerator = Math.pow(GOLDEN_RATIO, n) - Math.pow(1-GOLDEN_RATIO, n);
double denominator = SQRT_FIVE;
// This cast should in general work, as the result is always an integer.
// Floating point errors may occur!
return (long)(numerator/denominator);
}
从长度上的第94个数字不再足够，你需要使用BigInteger和拟合数学运算，因为double计算可能会产生如此大的数字的计算错误。
首先，使用long而不是int，以避免溢出。
其次，使用非递归算法，因为我认为在指数时间内存在递归算法。一个设计良好的非递归的将在线性时间内解决（我认为）。
示例非递归
static long getSum(int n){
long[] fibonacci = new long[n];
fibonacci[0] = 1;
fibonacci[1] = 1;
if (n==0) return 0;
if (n==1 || n==2) return 1;
for(int i = 2; i < n;i++){
fibonacci[i] = fibonacci[i-1]+ finonacci[i-2];
}
return fibonacci[n-1];
}
我没有测试过这个，但它应该可以工作。
如果您打算经常调用此方法，那么将数组存储在方法之外可能是谨慎的，因此在执行此操作时这是一个简单的查找。这将为已经计算过至少一次的数字提供恒定的时间解决方案。以下是一个例子。
static long[] fibonacci= {1,1};
static long getSum(int n){
if (n==0) return 0;
if (n==1 || n==2) return 1;
int old_length = fibonacci.length;
if(fibonacci.length < (n-1)){
fibonacci = Arrays.copyOf(fibonacci,n);
}else{
return fibonacci[n-1];
}
for(int i = old_length; i < n;i++){
fibonacci[i] = fibonacci[i-1]+ finonacci[i-2];
}
return fibonacci[n-1];
}
同样，该示例未经测试，因此可能需要进行一些调试。
这是算法的线性时间实现，它使用恒定开销而不是线性开销。
static long getSum(int n){
long currentNum = 0;
long previousNum = 1;
long previousNum2 = 1;
if (n==0) return 0;
if (n==1 || n==2) return 1;
for(int i = 2; i < n;i++){
currentNum = previousNum+ previousNum2;
previousNum2 = previousNum;
previousNum = currentNum;
}
return currentNum;
}
如果要保持递归方法不变，请在数组或映射中缓存计算结果。为n计算一个Fibonacci时，保存该结果。然后，在您的方法中，首先看看您是否有结果并返回，如果您这样做。否则，进行递归调用。这是一个例子：仍然使用递归并且它非常快：
public static Map<Long,Long> cache = null;
public static void main(String[] args) {
cache = new HashMap<Long,Long>();
cache.put(0L,0L);
cache.put(1L,1L);
cache.put(2L,1L);
Long sum=getSum(50L);
System.out.println("Sum of Fibonacci Numbers is " + sum);
}
static Long getSum(Long n){
if (cache.containsKey(n)) { return cache.get(n); }
else {
Long fib = getSum(n-1) + getSum(n-2);
cache.put(n, fib);
return fib;
}
}
递归解决方案不一定非常慢。如果您使用这种尾递归解决方案，您将节省大量内存并仍然可以实现极快的速度（例如，在我的机器上以1.1秒运行Fib（10000））。
这里n是你计算Fibonacci数的序列号，而f0和f1是两个累加器，分别用于前一个和当前的Fibonacci数。
public class FibonacciRec {
public static int fib(int n, int f0, int f1) {
if (n == 0) {
return f0;
} else if (n == 1){
return f1;
} else {
return fib(n-1, f1, f0+f1);
}
}
public static void main(String[] args) {
System.out.println(fib(10, 0, 1));
}
}