斐波那契数列 – 递归求和
好吧，我最初编写了一个简单的代码，根据用户输入从系列中返回斐波纳契数。
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)); }
编辑：
对于斐波那契系列.. 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
您对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修改”的fibonacci函数。
以下是归纳certificate您的程序计算我在原始答案中提供的总和。 设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 ，对于0 < j < k+1 ， S[j+1] = F[j+1] + S[j] ，certificate如果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]
这样就完成了certificate。
不，不会。 代码的第二个版本不计算斐波那契函数的所有值的总和，直到给定值。 基本情况也是错误的！
如果要递归计算总和，请将问题分为两部分，如下所示：
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); }
第一个函数计算fibonacci，第二个函数负责将值添加到给定数字。
正确的方法是使用累加器。
代码应该看起来像这样（我没有检查它，它只是这个想法）
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; }
你的代码需要测试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
您的原始方法很好，但这取决于您如何考虑斐波那契数字的“顺序”（您希望第一个数字是什么）。
递归是计算斐波纳契数的一种非常低效的方法。在数字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; }
另一种使用递归函数打印Fibonacci系列的方法。
#include // 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); }