递归求斐波那契数之和

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