使用递归实现斐波那契数列

Question

使用递归实现斐波那契数列

3

这是我解决“用最少的处理能力求解斐波那契数列第n项”的想法 -

int fibo(int n, int a, int b){
    return (n>0) ? fibo(n-1, b, a+b) : a;
}

main(){
    printf("5th term of fibo is %d", fibo(5 - 1, 0, 1));
}

要打印出所有项，直到第n项为止：

int fibo(int n, int a, int b){
    printf("%d ", a);
    return (n>0)? fibo(n-1, b, a+b): a;
}

我把这段代码展示给了我的大学教授，根据她的意见，这种解决斐波那契问题的方式是错误的，因为它没有抽象出方法。我应该使用被称为fibo(n)的函数来调用，而不是fibo(n, 0, 1)。对我来说，这并不是一个令人满意的答案，所以我想向SOF上的专家询问。

它相对于传统的斐波那契问题解决方法有其优势。我们采用两个并行递归来得到斐波那契数列的第n项（fibo(n-1) + fibo(n-2)），这种技术在给出100项时可能会很慢，而即使在最坏情况下，我的技术也会更快。

为了抽象它，我可以使用默认参数，但C语言不支持这样做。虽然我可以使用类似于-

int fibo(int n){return fiboN(n - 1, 0, 1);}
int fiboN(int n, int a, int b){return (n>0)? fiboN(n-1, b, a+b) : a;}

但是仅仅抽象整个想法就足够了吗？我该如何说服别人这种方法并不是错误的（虽然有点模糊）？

（我知道，这不是我应该在SOF上问的问题，但我只是想从这里的专家那里获得建议。）

- killerthawne

6

我感到困惑。既然你没有对a和b进行任何操作，它们为什么还要出现？而且这个函数不管什么情况下都会返回零吗？ - Sami Kuhmonen

1

正如@SamiKuhmonen所说，这段代码将始终返回0。也许您的教授希望您解决这个问题而不是“抽象”问题？在我看来，“抽象”问题实际上并不是问题，而是一种功能，因为您可以为斐波那契计算器指定起始值。 - Alerra

1

你测试过你的想法吗？它有效吗？我不认为第5个斐波那契数是零，但也许我错过了什么？ - n. m.

第五个斐波那契数是第四个加上第三个。所以尝试计算第四个数字。那就是第三个加上第二个。所以计算第三个……它是第二个加上第一个。我认为你走在正确的轨道上，保留多个数字，但是当你调用fibo(5,0,1)时传递的额外数字是第一和第二个，而这些在计算第五个数时没有用处。 - Tim Randall

哦，我的错。我的代码中有一个打字错误。它应该返回a而不是0。差不多可以了，请重新检查代码。 - killerthawne

7个回答

2

根据你的方法，结果将是0。你一直递归，直到 n=0，然后返回0。但你还需要检查当n==1时，应该返回1；此外，你有a和b的值，但对它们什么都没有做。

我建议您查看以下递归函数，也许它可以帮助您修复：

int fibo(int n){
    if(n < 2){
        return n;
    }
    else 
    {
       return (fibo(n-1) + fibo(n-2));    
    }
}

这是研究递归时经典的问题。

编辑1：根据@Ely的建议，下面是一种优化的递归方式，采用记忆化技术。当计算列表中的一个值时，它不会像第一个例子那样重新计算，而是会存储在数组中，并在需要时从该数组中获取：

const int MAX_FIB_NUMBER = 10;

int storeCalculatedValues[MAX_FIB_NUMBER] = {0};

int fibo(int n){

    if(storeCalculatedValues[n] > 0)
    {
        return storeCalculatedValues[n];
    }

    if(n < 2){
        storeCalculatedValues[n] = n;
    }
    else 
    {
       storeCalculatedValues[n] = (fibo(n-1) + fibo(n-2));
    }
    return storeCalculatedValues[n];
}

- Simion

那非常低效。 - Keith Thompson

我同意，但这是递归。 - Simion

我知道这种方法，我的教授教过我们用这种方法来解决问题。请看修改后的代码，有一个笔误。 - killerthawne

上述方法的问题在于，它会为解决数列的每个新项在内存中建立两个并行堆栈。这种方式计算第1000个项需要花费数分钟（可能更快）来得出答案。但是在我的建议方法中，它记住斐波那契数列的最后两个项，并且不需要每次都从头开始，就可以给出第n项的值，与传统方法相比更加高效。 - killerthawne

@Simion 这里有一种不需要递归就能解决的方法... https://dev59.com/F63la4cB1Zd3GeqPQKYm#51885162 - Eugene

显示剩余2条评论

1

使用递归，并以“最少的处理能力”为目标，解决fibonacci()的方法是使每个调用返回2个值。也许一个通过返回值，另一个通过int *参数。

通常，递归的想法是让顶级函数执行一次准备和参数检查，然后是以简洁方式编写的本地辅助函数。

以下内容遵循OP的想法，包括一个int fibo(int n)和一个辅助函数int fiboN(int n, additional parameters)。

递归深度为O(n)，内存使用也为O(n)。

static int fib1h(int n, int *previous) {
  if (n < 2) {
    *previous = n-1;
    return n;
  }
  int t;
  int sum = fib1h(n-1, &t);
  *previous = sum;
  return sum + t;
}

int fibo1(int n) {
  assert(n >= 0); // Handle negatives in some fashion
  int t;
  return fib1h(n, &t);
}

- chux - Reinstate Monica

1

#include <stdio.h>
int fibo(int n);//declaring the function.

int main()
{
    int m;
    printf("Enter the number of terms you wanna:\n");
    scanf("%i", &m);
    fibo(m);
    for(int i=0;i<m;i++){
        printf("%i,",fibo(i)); /*calling the function with the help of loop to get all terms */
    }
    return 0;
}

int fibo(int n)
{ 
    if(n==0){
        return 0;
    }
    if(n==1){
        return 1;
    }

    if (n > 1)
    {
        int nextTerm;
        nextTerm = fibo(n - 2) + fibo(n - 1); /*recursive case,function calling itself.*/
         return nextTerm;
    }
}

- SUMIT KUMAR

这是使用递归方法的斐波那契数列的基本解决方案。 - SUMIT KUMAR

0

顺便提一下，你可以在几乎不使用递归的情况下解决斐波那契问题，这使它成为我所知道的最快的方法。代码是用Java编写的：

public int fibFor() {
    int sum = 0;
    int left = 0;
    int right = 1;
    for (int i = 2; i <= n; i++) {
        sum = left + right;
        left = right;
        right = sum;
    }
    return sum;
}

- Eugene

是的，我非常清楚这种方法。由于我们所学的实际模块是递归，因此我们必须仅使用这个概念来实现所有内容。顺便说一下，谢谢你的建议。 - killerthawne

即使是阶乘这样的东西，通过简单的循环结构实现也非常快速，消耗较少/几乎没有堆栈内存，并且易于理解，但是大学还是要求我们使用那些繁琐的递归方法来实现所有这些东西，即使它们的效率低了一百倍。 - killerthawne

0

解决“使用最少的处理能力求解斐波那契数列的第n项问题”

我可能不需要向您解释斐波那契数的递归关系。尽管您的教授给了您一个很好的提示。

抽象出细节。她是对的。如果您想要第n个斐波那契数，只需告诉程序：Fibonacci(n)。

由于您的目标是“使用最少的处理能力”，因此您教授的提示也适用于一种称为memoization的技术，它基本上意味着“如果您已经计算过第n个斐波那契数，只需重复使用结果；无需重新计算”。在文章中，您可以找到阶乘数的示例。

为此，您可能需要考虑一种数据结构，其中存储第n个斐波那契数；如果该内存已经有一个斐波那契数，只需检索它，否则将计算出的斐波那契数存储在其中。

顺便说一句，这并不有助于教学，但很有趣：第n个斐波那契数还存在闭合形式表达式。

这对我来说并不是一个令人满意的答案，所以我想向SOF上的专家请教。"嗯，你不认为你的教授是专家吗？"这是我的第一反应。

- Ely

是的，她的回答对我来说不够令人满意。抽象的东西是我在发布问题时添加的，她根本没有提到它。请再次检查原始代码，我已经更正了拼写错误。 - killerthawne

如果您已经计算过第n个斐波那契数，只需重复使用结果即可，无需重新计算。这正是我对其他解决方案的担忧。如果我想打印出100个斐波那契数列，就需要调用fibo() 100次+内部调用它所做的任何调用，如“return fibo(n-1) + fibo(n-2)”。对于记忆化问题，如果我遵循@simion答案中提到的技术之一，您认为创建一个全局数组是一个好主意吗？ - killerthawne

0

虽然@rici的回答大多数情况下是令人满意的，但我只是想分享一下我解决这个问题时学到的东西。以下是我对使用递归查找斐波那契数列的理解：

传统的实现fibo(n) { return (n < 2) n : fibo(n-1) + fibo(n-2);}在时间和空间需求方面都非常低效。这会不必要地构建堆栈。它需要O(n)的堆栈空间和O(rⁿ)的时间，其中r = (√5 + 1)/2。
使用@Simion的建议中提出的记忆化技术，我们只需创建一个永久堆栈，而不是编译器在运行时创建的动态堆栈。因此，内存需求保持不变，但时间复杂度以分摊的方式降低。但如果我们只需要使用它一次，则没有帮助。
我在我的问题中提出的方法需要O(1)的空间和O(n)的时间。使用相同的记忆化技术，时间需求也可以以分摊的方式降低。
从@rici的帖子中，fib(2n) = fib(n)² + 2fib(n)fib(n - 1)，正如他建议的那样，时间复杂度降低到O(log n)，我想，堆栈增长仍然是O(n)。

所以我的结论是，如果我进行了适当的研究，使用递归计算无法同时减少时间复杂度和空间需求。要实现这两个目标，可以采用迭代、矩阵乘法或快速倍增等替代方法。

- killerthawne

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- rici · Accepted Answer

在理解递归中的基础情况应该以 a 为基础，而不是 0 的前提下，这对我来说似乎是一个很好（尽管不是最佳）的解决方案。该函数中的递归是尾递归，因此一个好的编译器将能够避免堆栈增长，使函数的空间复杂度为 O(1)，时间复杂度为 O(n)（忽略数字大小的迅速增长）。

您的教授正确地指出了调用者不应该必须处理正确的初始化。因此，您应该提供一个外部包装器，避免需要填写值的需要。

int fibo(int n, int a, int b) {
    return n > 0 ? fibo(b, a + b) : a;
}
int fib(int n) { return fibo(n, 0, 1); }

然而，如果调用者想要改变初始值，提供和记录更通用的接口也可能很有用。

顺便说一下，还有一种基于递归的更快的计算技术。

fib(a + b - 1) = f(a)f(b) + f(a - 1)f(b - 1)

将b替换为b + 1得到：

fib(a + b) = f(a)f(b + 1) + f(a - 1)f(b)

通过这些公式，我们可以计算：

fib(2n - 1) = fib(n + n - 1)
            = fib(n)² + fib(n - 1)²

fib(2n)     = fib(n + n)
            = fib(n)fib(n + 1) + fib(n - 1)fib(n)
            = fib(n)² + 2fib(n)fib(n - 1)

这可以使计算在O(log n)步内完成，每一步产生两个连续的值。