获取由斐波那契数组成的总和的代码

Question

我正在尝试编写一个简单的递归代码来计算斐波那契级数的总和，但我不知道如何使计数器正常工作，这是我的代码：

public static long fibonacciRecursiveHits(int n,long sum) 
{
    if (n>1)
    {
        sum++;
        sum =  fibonacciRecursiveHits(n-1,sum) + fibonacciRecursiveHits(n-2,sum);
    }
    return sum;
}

示例：

Input: 4
Correct Output: 4 //The number of sums
My Output: 12

Answer 1

您的问题是您正在计算 n 的总和数，并且将其添加到 n+1 和 n+2 的总和中，这使您不止一次计算它们。

简单的解决方案：return总和数

只需计算 n 的总和数，而不向下传递。例如试试这个：

public static long fibonacciRecursiveHits(int n)
{
    if (n>1)
    {
        return  fibonacciRecursiveHits(n-1) + fibonacciRecursiveHits(n-2) + 1;
    } else {
        return 0;
    }
}

我们在这里做什么：如果 n > 1，我们计算 n-1 的所有总和加上 n-2 的总和加上这个总和（1 个总和）。

备选方案：传递参数

如果你想将总和作为参数向下传递并递归更新它，你可以，但并非没有技巧，因为 Java 是按值传递，这意味着如果您在函数中修改 sum，它不会为调用者修改。有几种方法可以解决此问题。

创建一个包含 int sum 的对象并向下传递该对象
创建一个静态变量 sum，以便您可以在 class
创建一个包含一个元素的数组并将其传递下去
this answer中描述的其他方式

这是一个关于如何使用选项 3 的示例：

public static void fibonacciRecursiveHits(int n, long[] sum)
{
    if (n>1)
    {
        sum[0]++;
        fibonacciRecursiveHits(n-1, sum);
        fibonacciRecursiveHits(n-2, sum);
    }
}

发生的情况是，每次进行求和的调用都会增加求和。

现在你这样称呼它：

    long[] sum = {0};
    fibonacciRecursiveHits(4, sum);
    System.out.println(sum[0]); //sum[0] contains your result

迭代求解

上述递归解决方案的问题在于它们具有指数运行时间 O(2^n)，这意味着在中型到大型输入上会非常慢。另一种方法是迭代构建结果并将它们保存在数组中（动态规划）。这将运行时间减少到 O(n)。

public static long fibonacciRecursiveHits(int n)
{
    long[] sums = new long[n+1];
    // sums[0] and sums[1] are both initialized to 0
    for(int i = 2; i <= n; i++){
        sums[i] = sums[i-2] + sums[i-1] + 1;
    }
    return sums[n];
}

获取由斐波那契数组成的总和的代码

Code to get sums made of a fibonacci number

java

recursion

math

fibonacci

简单的解决方案：return总和数

备选方案：传递参数

迭代求解