用於大數字的Java遞歸斐波納契實現

Question

我一直在玩一些代碼今晚，我編碼了一個非常簡單的算法，我認爲這是斐波那契遞歸和大數字的一個非常好的解決方案。我想知道你們想想看，如果你有與我們做的更好，共享任何貢獻......看看代碼波紋管

public class RecursiveFibonacci { 

    public void calculateFib(long first, long next, long counter, int n) { 
     if(counter == n) { 
      return; 
     } 
     counter++; 
     if(first == 0 && next == 0) { 
      System.out.println("0"); 
      calculateFib(0, 1, counter, n); 
      return; 
     } 

     if(first == 0 && next == 1) { 
      System.out.println("1"); 
      calculateFib(1, 0, counter, n); 
      return; 
     } 

     if(first == 1 && next == 0) { 
      System.out.println("1"); 
      calculateFib(1, 1, counter, n); 
      return; 
     } 

     long result = first + next; 
     if(result > 1) { 
      System.out.println(result); 
       calculateFib(next, result, counter, n); 
     } 
    } 

    public RecursiveFibonacci() { 
     calculateFib(0, 0, 0, 9999999); 
    } 

    public static void main(String[] args) { 
     new RecursiveFibonacci(); 
    } 

} 

Answer 1

斐波那契序列只取決於前兩個值，您的基本案例是F(0) = 1和F(1) = 1，以及一般F(n) = F(n - 1) + F(n - 2)。你所需要做的就是記住這些。遞歸是解決斐波納契數字的一種不好的方法，因爲數值越高，你不必要地做出的呼叫就越多。你很快就會用完堆棧空間。

Answer 2

一個問題是，calculateFib()不返回任何計算結果。它只打印結果。因此，更改代碼以便返回結果。

一旦工作，請嘗試非遞歸變體，這在實踐中更適合。

Answer 3

由於F 有〜2089876個數字，所以您需要使用approximation。另請考慮memoization。

Answer 4

我覺得遞歸斐波那契數具有非常高的計算複雜度也可能爲O（n！），而迭代就是O（n）的:)

Answer 5

計算第i個斐波那契的最好方法是而不是遞歸。您可以使用這些公式：

Phi是黃金比例。然而，斐波那契數字的問題與使用方法無關，但與數字的位數無關。他們將很難寫入大量。