斐波纳契系列 - 递归求和

Question

好的，我最初写了一个简单的代码来从基于用户输入的一系列返回Fibonacci数..

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

编辑：

对于斐波那契series..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部分去除。

你问：

我仍然无法找出级数求和是如何工作的，如果我加1，可有人请解释？

这个问题实际上是关于理解的算法，我会想是SO外用。但是，需要用数学来描述算法的工作原理。所以，这真是一个数学问题。有一个well known theorem regarding the sum of Fibonacci numbers。如果F[i]是第i个Fibonacci数，并且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] 

这样就完成了证明。

Answer 2

没有也不会。代码的第二个版本而不是计算斐波那契函数的所有值的总和直到给定值。基本情况也是错误的！

如果你想递归地计算总和，分成两个部分的问题，像这样的：

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

第一个函数计算斐波那契数，第二需要增加值达到一定数目的照顾。

Answer 3

你的代码需要测试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 

您的原始方法很好，但这取决于您如何考虑斐波纳契数的“顺序”（您希望第一个数字是什么）。

Answer 4

正确的做法是使用累加器。

代码应该是这个样子（我没有检查它，它的唯一的想法）

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

Answer 5

递归是计算斐波那契number.After数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; 
    } 

Answer 6

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

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