java - 斐波那契数列 - 递归求和

Question

好的，我最初写了一个简单的代码来根据用户输入从系列中返回斐波那契数..

n=5 会产生 3..

static int fibonacci(int n) {
        if (n == 1)
            return 0;
        else if (n == 2)
            return 1;
        else
            return (fibonacci(n - 1) + fibonacci(n - 2));
    }

我正在考虑修改代码以返回系列的总和，而不是仅仅返回系列的值，并且在尝试求和时我不小心将 1 添加到 return 语句，令我惊讶的是，它返回了总和正确。

下面的代码将在 n=5 时返回 7。

我不确定这是否是计算总和的正确方法...

如果我加 1，我仍然无法弄清楚级数的总和是如何工作的。有人可以解释一下吗？？

static int fibonacci(int n) {
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return (fibonacci(n - 1) + fibonacci(n - 2)+(1));
}

编辑:

对于斐波那契数列..0,1,1,2,3,5,8,13,21,34,55,89,144....

我尝试了一些随机的 n

n=13

函数返回376

0+1+1+2+3+5+8+13+21+34+55+89+144 = 376

n=10

函数返回88

0+1+1+2+3+5+8+13+21+34=88

Answer 1

您对 fibonacci 的修改程序确实可以计算总和。但是，您使用递归的方式效率低下。处理此问题的一种方法是使用“动态编程”方法，其中缓存计算值，以便第二次递归调用可以重新使用它们。但是，可以从基数向前计算第 n 个斐波那契数。这个的递归实现是:

public static int fib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return fib_r(b, a+b, n-1);
}

public static int fib (int n) {
    return fib_r(0, 1, (n > 0) ? n : 1);
}

求和的相应代码是:

public static int sumfib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return sumfib_r(b, a+b+1, n-1);
}

public static int sumfib (int n) {
    return sumfib_r(0, 1, (n > 0) ? n : 1);
}

作为 tail call 的一部分，尾递归通常会被编译器/解释器更改为一个简单的循环。删除。

你问:

I still couldn't figure out how the summation of the series works if I add 1. Can someone please explain??

这个问题实际上是关于理解算法，我认为这是关于 SO 的主题。但是，需要数学来描述算法为何有效。所以，这真的是一道数学题。有一个 well known theorem regarding the sum of Fibonacci numbers .如果F[i]是第 i 个斐波那契数，S[n]是第一个n的总和斐波那契数列，则上面的定理指出:

    S[n] = F[n+2] - 1

因此，如果我们根据 S[n+2] 的定义来考虑,

S[n+2] = S[n+1] + F[n+2]

然后，代入 S[n] + 1对于 F[n+2] :

S[n+2] = S[n+1] + S[n] + 1

您应该认识到的是您的“添加 1 个修改”fibonacci功能。

---

下面是一个归纳证明，证明您的程序计算了我在原始答案中提供的总和。让F代表你的fibonacci功能，让S代表你的“加1修改”fibonacci功能。

F[1] = 0
F[2] = 1
F[i] = F[i-1] + F[i-2] for i > 1

S[1] = 0
S[2] = 1
S[i] = S[i-1] + S[i-2] + 1 for i > 1

然后，您需要一个关于 k > 0 的证明:

         k
       .---  
S[k] =  >   F[i]
       `---
       i = 1

请注意，当且仅当:

S[1] = F[1]
S[k] = F[k] + S[k-1] for k > 1

证明相当简单。基本情况是微不足道的。

S[1] = F[1] = 0
S[2] = F[2] + F[1] = 1
S[3] = S[2] + S[1] + 1 = F[3] + F[2] + F[1] = 2

归纳步骤是:假设对于某些 k > 2 , S[j+1] = F[j+1] + S[j]对于 0 < j < k+1 , 如果 j = k+1 证明等式成立，即:S[k+2] = F[k+2] + S[k+1] .

    S[k+2] = S[k+1] + S[k] + 1
=>  S[k+2] = (F[k+1] + S[k]) + (F[k] + S[k-1]) + 1
=>  S[k+2] = (F[k+1] + F[k]) + (S[k] + S[k-1] + 1)
=>  S[k+2] = F[k+2] + S[k+1]

这样就完成了证明。