递归求斐波那契数之和

Question

我有点被困在这里了。我知道可以递归地找到特定的斐波那契数：

int fib (int n)
{
    if (n <= 1)
        return n;

    else 
        return fib(n-1) + fib(n-2);
}

我知道我可以迭代地调用该函数 n 次来找到斐波那契数的总和

int sum = 0;
for (int i = 0; i < n; i++)
{
    sum += fib(i);
}

但是我很难想出一个递归函数来求和。我认为它与原始的斐波那契函数没有太大不同。 （这是一项旨在提高我编写 ocaml 语法的能力的作业，而不是编写递归函数）

Answer 1

既然没有人愿意回答你的问题，那就开始吧：

int fib_sum(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    return fib_sum(n-1) + fib_sum(n-2) + 1;
}

Answer 2

如果您想要一个仅涉及 fib_sum() 的递归解决方案，这里是一个：

int fib_sum (int n)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return 2;
    return fib_sum(n-1) + fib_sum(n - 2) + 1;
}

Answer 3

观察 fib_sum(n) == fib(n+2) - 1 你可以使用或多或少相同的函数。

Answer 4

我想这会很好用

int fib_sum (int n){
  if(n<=1) {
    return n;
  }
  else {
    return fib_Sum(n-1) + fib_Sum(n-2) + 1;
  }
}

Answer 5

记住元素的计数是从0开始的 所以元素 0 1 1 2 3 5 8 13 然后位置 0 1 2 3 4 5 6 7 因此，如果 n = 5，则总和 = (0+1+1+2+3+5)=12

递归函数将是：

 int fib_sum (int n){ if(n<=1) { return n; } else { return fib_Sum(n-1) + fib_Sum(n-2) + 1; } }

Answer 6

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)