logo标签列表

斐波那契数列 - 递归求和

javamathrecursionfibonacci
6

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

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加了进去，结果惊奇地发现这样可以正确地返回序列的和。
以下代码在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

如果n = 5，你的结果应该是11，而不是7。（1 + 2 + 3 + 5 = 11）。你想要计算什么？ - niculare
我从0开始而不是1...所以0+1+1+2+3... - Learner
它对于系列中的下一个数字有效吗？如果不是，则该算法是错误的。 - Sotirios Delimanolis
这不是 int fib(int n){ return n <= 1 ? n : fib(--n) + fib(--n);} 吗？ - user1181445
6个回答
10
你对 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);
}

尾递归往往会被编译器/解释器作为尾调用移除的一部分而转换成简单的循环。

您问道：

如果我加1，我仍然无法弄清楚这个级数的求和如何工作。请有人解释一下吗？

这个问题实际上是关于理解算法的，我想它也与SO的主题有关。但是，需要数学来描述算法为什么有效。因此，这实际上是一个数学问题。有一个关于斐波那契数列和的著名定理。如果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修改版”斐波那契函数。
以下是归纳证明，证明您的程序计算了我在原始答案中提供的总和。让F代表您的斐波那契数列函数，让S代表您的“加1修改版”斐波那契数列函数。
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]

这证明完成了。

3
不，它不会。代码的第二个版本并没有计算出给定值之前所有斐波那契函数值的总和。而且基本情况也是错误的！
如果您想递归地计算总和，请将问题分成两部分，像这样：
public static int fib(int n) {
    return n < 2 ? n : fib(n-1) + fib(n-2);
}

public static int sumfib(int n) {
    return n < 0 ? 0 : fib(n) + sumfib(n-1);
}

第一个函数计算斐波那契数列，第二个函数则负责将给定数字之前的值相加。
1
正确的方法是使用累加器。
代码应该类似于这样（我没有检查它，只是个想法）。
static int fibonacci(int n, int accumlator) {
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        accumlator = (fibonacci(n - 1, accumlator) + fibonacci(n - 2, accumlator));
        return accumlator;
}
0

使用递归函数打印斐波那契数列的另一种方法。

#include <iostream>

// 0 1 1 2 3 5 8 13...
//

void fibb (int idx, int curr = 0, int next = 0)
{
        std::cout << curr << ", ";
        if(!idx) return;
        if(curr == 0) {
                curr = 1;
                fibb(--idx, curr, next);
                return;
        }
        next += curr;
        fibb(--idx, next, curr);
}


int main()
{
        fibb(10);
}
0

使用递归计算斐波那契数列是一种非常低效的方法。在计算第43个数字后，需要超过30秒才能得到答案。我尝试计算第52个数字所需的时间，结果大约需要47分钟。因此，计算时间增长非常快。

递归代码：

private int calculateRecursivelyInt(int fnum)
    {
        if (fnum == 0)
            return 0;
        if (fnum == 1)
            return 1;

        return calculateRecursivelyInt(fnum - 1) + calculateRecursivelyInt(fnum - 2);
    }

循环结构更高效

    //This method will be able to calculate till the F46 because int can't hold a 
    // bigger number. You can calculate till 92 with a type long and till 93 with
    // unsigned long in C#.

    private int calculateLoopInt(int num)
    {
        int fnum = 0;
        int val1 = 0;
        int val2 = 1;

        for (int i = 0; i < num; i++)
        {
            if (num == 1)
                fnum = 1;
            else if (i > 0)
            {
                fnum = val1 + val2;
                val1 = val2;
                val2 = fnum;
            }
        }
        return fnum;
    }
0

你的代码需要测试 n<1 - 如果传入一个小于等于0的参数，它会无限执行...

除此之外 - 如果调用 fib(5)，以下是发生的事情：

...
return(fib(4) + fib(3))

fib(4):
return(fib(3) + fib(2))

fib(3):
return(fib(2) + fib(1))

now fib(2) == 1 by your definition, and fib(1) == 0

so fib(3) == 1

then fib(4) == 1 + 1 = 2

and fib(5) = fib(4) + fib(3) = 2 + 1 = 3

Now if you add the '+1', the following happens:

fib(1) and fib(2) are unchanged
fib(3) = 1 + 0 + 1 = 2
fib(4) = fib(3) + fib(2) + 1 = 4
fib(5) = fib(4) + fib(3) + 1 = 4 + 2 + 1 = 7

你的原始方法不错，但它取决于你如何考虑斐波那契数列的“顺序”（你想让第一个数字是什么）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接