对于带递归的斐波那契数列，这是更好的方法吗？

Question

我在哪里看到递归斐波那契数列，每个人都说

a[i] = fib(i - 1) + fib( i - 2)

不过也可以用

解决

a[i] = fib(i - 1) + a[i-2] // If array 'a' is a global variable.

如果数组'a'是全局变量，那么在计算a[i-2]的时候会计算a[i-2];

在java..

中可以用下面的程序解决

public class Fibonacci {

    public static int maxNumbers = 10;
    public static double[] arr = new double[maxNumbers];

    public static void main(String args[])
    {
        arr[0] = 0;
        arr[1] = 1;

        recur(maxNumbers - 1);
    }

    public static double recur(int i)
    {
        if( i > 1)
        {
            arr[i] = recur(i - 1) + arr[i - 2];
        }

        return arr[i];
    }
}

此外，与原始程序相比，复杂性也更低。这样做有什么缺点吗？

Answer 1

你已经完成了斐波那契计算的第一步Dynamic Programming，DP的思想是避免冗余计算，你的算法达到了目的。

A "classic" 自下而上的 DP 斐波那契实现从低到高填充元素：

arr[0] = 0
arr[1] = 1
for (int i = 2; i <= n; i++)
    arr[i] = arr[i-1] + arr[i-2]

（优化可以单独存储 curr,last，并在每次迭代时修改它们。

你的做法在原理上基本相同

附带说明一下，计算斐波那契的 DP 方法需要 O(n) 时间，其中有更有效的矩阵指数解决方案：

1 1 
1 0

以上内容成立是因为您使用了

1     1               F_{n+1}                1*F{n+1} + 1*F{n}           F_{n+2}
               *                       =                          =                         
1     0               F_{n}                  1*F{n+1} + 0*F{n}           F_{n+1}

在上面的矩阵上使用exponent by squaring，这可以在O(logn)中解决。

Answer 2

这只是非递归版本的一步： https://gist.github.com/vividvilla/4641152

总的来说，这种部分递归的方法看起来非常混乱

Answer 3

如果你只想要第 n 个斐波那契数，你可以这样做：

static double fib(double prev, double curr, int n) {

    if(n == 0)
        return curr;

    return fib(curr, prev+curr, n-1);

}

初始条件为 prev = 0、curr = 1、n = maxNumbers。此函数是尾递归的，因为您不需要存储递归调用的 return 值以进行任何其他计算。初始堆栈帧被重用（这节省了内存），一旦你达到你的基本情况，returned 的值与每个其他递归调用的 returned 的值相同。

Answer 4

您也可以使用两个递归函数进行编码，但由于同一个值会一遍又一遍地计算，所以您可以采用动态编程方法，您可以将值存储在 return 中 [=13] =] C++ 中的这个

#include <bits/stdc++.h>

using namespace std;

int dp[100];

int fib(int n){

   if(n <= 1)
     return n;

   if(dp[n]!= -1)
     return dp[n];

   dp[n] = fib(n-1) + fib(n-2);

   return dp[n];

}

int main(){

   memset(dp,-1,sizeof(dp));

   for(int i=1 ;i<10 ;i++)
    cout<<fib(i)<<endl;

}

Answer 5

通过像您一样使用数组，您只需重新计算两个分支之一（每次迭代中最长的一个），最终复杂度为 O(n)。

如果您要跟踪之前计算出的斐波那契数有多大，您可以使用它并生成 O(max(n-prevn, 1))。如果需要，这是从底部到 i 填充数组的代码的更改版本：

public class Fibonacci {
    public static final int maxNumbers = 93; // fib(93) > Long.MAX_VALUE 
    public static long[] arr = new long[maxNumbers];
    public static int calculatedN = 0;

    public static long fib(int i) throws Exception
    {
        if( i >= maxNumbers )
            throw new Exception("value out of bounds"); 

        if( calculatedN == 0 ) {
            arr[0] = 0L;
            arr[1] = 1L;
            calculatedN = 1;
        }

        if( i > calculatedN ) {
           for( int x=calculatedN+1; x<=i; x++ ){
             arr[x] = arr[x-2] + arr[x-1];
           }
           calculatedN = i;
        }

        return arr[i];
    }

    public static void main (String args[]) {
       try {
        System.out.println(fib(50)); // O(50-2)
        System.out.println(fib(30)); // O(1)        
        System.out.println(fib(92)); // O(92-50)
        System.out.println(fib(92)); // O(1)        
       } catch ( Exception e ) { e.printStackTrace(); }
    }
}

我把double改成了long。如果您需要比 fib(92) 更大的斐波那契数，我会将 long 更改为 Biginteger。

对于带递归的斐波那契数列，这是更好的方法吗？

Is this a better way for Fibonacci Series with Recursion?

java

algorithm

recursion