斐波那契数列 - 递归求和 [英] fibonacci series - recursive summation

问题描述

好吧，我最初写了一个简单的代码，根据用户输入从系列中返回Fibonacci数字。

Ok, I initially wrote a simple code to return the Fibonacci number from the series based on the user input..

n = 5将产生3 ..

n=5 will produce 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语句中，令我惊讶的是，它正确地返回了总和。

I was thinking of modifying the code to return the sum of the series rather than just returning the value from the series and while trying to do the sum I accidentally added 1 to the return statement and to my surprise, it returned the sum correctly.

以下代码将返回7代表n = 5.

The below code will return 7 for n=5.

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

I am not sure if this is a right way to calculate the sum...

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

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

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

编辑：

对于Fibonacci系列.. 0,1,1,2,3,5,8,13,21,34,55,89,144 ....

For Fibonacci series..0,1,1,2,3,5,8,13,21,34,55,89,144....

我试过对于某些随机n

I tried for some random n

n = 13

该函数返回376

0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 + 21 + 34 + 55 + 89 + 144 = 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

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

推荐答案

您对斐波那契计划的修改确实可以计算总和。但是，使用递归的方式效率很低。处理此问题的一种方法是使用动态编程方法，其中计算值被缓存，以便第二次递归调用可以重用它们。但是，第n个斐波纳契数可以从基数计算出来。递归实现的方法是：

Your modification to your fibonacci program does indeed work to calculate sums. However, the way you have used recursion is inefficient. One way to deal with this is with a "dynamic programming" approach, where calculated values are cached so that they can be re-used by the second recursive call. However, the n-th Fibonacci number can be forward calculated from the base. A recursive implementation of this would be:

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 recursion will often be changed by the compiler/interpreter into a simple loop as part of tail call removal.

你问：

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

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

这个问题实际上是关于理解算法的，我认为这是SO的主题。但是，需要数学来描述算法的工作原理。所以，这真的是一个数学问题。有一个关于斐波那契数字总和的众所周知的定理。如果 F [i] 是第i个斐波纳契数，而 S [n] 是第一个的总和 n Fibonacci数，然后上面的定理说明：

This question is really about understanding the algorithm, which I would suppose is topical on SO. But, math is required to describe why the algorithm works. So, this is really a math question. There is a well known theorem regarding the sum of Fibonacci numbers. If F[i] is the i-th Fibonacci number, and S[n] is the sum of the first n Fibonacci numbers, then the theorem above states:

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

因此，如果我们根据<$的定义考虑c $ c> 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修改斐波那契功能。

Which you should recognize is your "add 1 modified" fibonacci function.

以下是感应证明您的程序计算我在原始答案中提供的总和。设 F 表示您的斐波那契函数，并让 S 代表你的添加1修改斐波那契函数。

Below is a proof by induction that your program computes the sum that I provided in my original answer. Let F represent your fibonacci function, and let S represent your "add 1 modified" fibonacci function.

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

注意如果且仅在以下情况下，总和为真：

Note that the above summation is true if and only if:

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

证明非常简单。基本情况很简单。

The proof is fairly straight forward. The base cases are trivially true.

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] 。

The induction step is: Given that for some k > 2, S[j+1] = F[j+1] + S[j] for 0 < j < k+1, prove that the equality holds true if j = k+1, that is: 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]

这完成证明。

这篇关于斐波那契数列 - 递归求和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！