-1

今晚我一直在玩一些代码，我编写了一个非常简单的算法，我认为它对于斐波那契递归和大数字来说是一个非常好的解决方案。我想知道你们对此有何看法，如果您对改进它有任何贡献，请与我们分享……看看下面的代码

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(); 
    }

}
4

5 回答 5

1

斐波那契数列仅取决于前两个值，您的基本情况是F(0) = 1and F(1) = 1，并且对于一般情况F(n) = F(n - 1) + F(n - 2)。您需要做的就是在计算时记住这些。递归是解决斐波那契数的一种糟糕方法，因为值越高，不必要的调用就越多。你很快就会用完堆栈空间。

于 2013-02-12T01:24:12.133 回答
1

我认为递归斐波那契也具有非常高的计算复杂度，可能是 O(n!)，而迭代只是 O(n) :)

于 2013-02-12T01:44:26.983 回答
1

计算第 i 个斐波那契的最佳方法不是递归。您可以使用以下公式：

在此处输入图像描述

在此处输入图像描述

在此处输入图像描述

phi是黄金比例。然而，斐波那契数的问题与使用方法无关，而与数字的位数有关。它们将变得难以为大数编写。

于 2013-02-12T02:25:04.867 回答
0

一个问题是，它calculateFib()不返回任何计算结果。它只打印结果。因此，更改代码以使其返回结果。

一旦可行，也可以尝试非递归变体，这在实践中更适合。

于 2013-02-12T01:30:15.770 回答
0

因为 F 9999999有 ~2089876 位，所以您需要使用近似值。还要考虑memoization。

于 2013-02-12T01:32:23.447 回答