获取斐波那契数列总和的代码

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 的总和中，这使你对它们进行多次计数。

简单的解决方案：返回总和的数量

只需计算 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是按值传递，这意味着如果你在函数中修改总和，它不会为调用者进行修改。 有多种方法可以解决这个问题。

1. 创建一个包含

   int sum

   的对象并将该对象向下传递
2. 创建一个静态变量 sum，这样你就可以在类中的任何地方修改它
3. 创建一个包含一个元素的数组并将其向下传递
4. 这个答案
中描述的其他方式

以下是如何使用选项 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];
}

Answer 2

def fibo(n):
if n == 1 or n == 0:
    global prev
    prev = 1
    return 1
sum = fibo(n-1) + prev
prev = sum - prev
return sum   

n = int(input('Enter number: '))
print(fibo(n-1))

T(n) = T(n-1) + O(1) = O(n)