使用递归的斐波那契

Question

这是我的解决思路'nth term of fibonacci series with least processing power'-

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 上提出的问题，但我只是想在这里获得专家的建议。）

Answer 1

采用您的方法，您的结果将是 0。你只是递归，直到 n=0 并且在那一点 return 0 。但是你还必须检查 n==1 并且你应该 return 1 ；你也有值 a 和 b 你做与他们无关。

我建议看看下面的递归函数，也许它会帮助你修复：

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

递归研究中的经典问题。

EDIT1：根据@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];
}

Answer 2

solving 'nth term of fibonacci series with least processing power'

斐波那契数列的递归关系，我可能不需要给你解释了。虽然你的教授给了你一个很好的提示。

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

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

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

顺便说一句，在教学上没有帮助，但很有趣：还有一个 closed form expression 表示第 n 个斐波那契数。

This wasn't a satisfactory answer to me, so I thought of asking experts on SOF.

"Uh, you do not consider your professor an expert?" 是我的第一个想法。

Answer 3

使用递归并以 最小处理能力 为目标，解决 fibonacci() 的方法是让每个调用 return 2 个值。也许一个通过 return 值，另一个通过 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);
}

Answer 4

理解递归中的基本情况应该是 a 而不是 0，这在我看来是一个极好的（尽管不是最佳的）解决方案。该函数中的递归是尾递归，因此一个好的编译器将能够避免堆栈增长使函数 O(1) soace 和 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 + 1 替换 b 得到：

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) 步中执行计算，每一步产生两个连续的值。

Answer 5

附带说明一下，您几乎可以在不递归的情况下执行 fibonacci problem，这是我所知道的最快的方法。虽然代码在 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;
}

Answer 6

虽然@rici 的回答基本令人满意，但我只是想分享我解决这个问题的经验。所以这是我对使用递归查找斐波那契的理解-

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

所以我的结论是，如果我做了适当的研究，时间复杂度和 space 要求都不能使用递归计算同时减少。要实现这两个目标，备选方案可以使用迭代 Matrix exponentiation or fast doubling。

使用递归的斐波那契

Fibonacci using Recursion

c

recursion

fibonacci