用于大数字的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是黄金比例。然而，斐波那契数字的问题与使用方法无关，但与数字的位数无关。他们将很难写入大量。