java 斐波那契数列 - 递归求和
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15394972/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
fibonacci series - recursive summation
提问by Learner
Ok, I initially wrote a simple code to return the Fibonacci number from the series based on the user input..
好的，我最初编写了一个简单的代码来根据用户输入从系列中返回斐波那契数。
n=5 will produce 3..
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));
}
I was thinking of modifying the code to return the sum of the series rather than just returning the value from the series and while trying to do the sum I accidentally added 1 to the return statement and to my surprise, it returned the sum correctly.
我正在考虑修改代码以返回系列的总和，而不仅仅是从系列中返回值，在尝试计算总和时，我不小心在 return 语句中添加了 1，令我惊讶的是，它正确地返回了总和。
The below code will return 7 for n=5.
下面的代码将在 n=5 时返回 7。
I am not sure if this is a right way to calculate the sum...
我不确定这是否是计算总和的正确方法......
I still couldn't figure out how the summation of the series works if I add 1. Can someone please explain??
如果我加 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));
}
EDIT:
编辑：
For Fibonacci series..0,1,1,2,3,5,8,13,21,34,55,89,144....
对于斐波那契数列..0,1,1,2,3,5,8,13,21,34,55,89,144....
I tried for some random n
我尝试了一些随机 n
n=13
n=13
The function returns 376
函数返回 376
0+1+1+2+3+5+8+13+21+34+55+89+144 = 376
0+1+1+2+3+5+8+13+21+34+55+89+144 = 376
n=10
n=10
The function returns 88
函数返回 88
0+1+1+2+3+5+8+13+21+34= 88
0+1+1+2+3+5+8+13+21+34= 88
回答by jxh
Your modification to your fibonacciprogram does indeed work to calculate sums. However, the way you have used recursion is inefficient. One way to deal with this is with a "dynamic programming" approach, where calculated values are cached so that they can be re-used by the second recursive call. However, the n-th Fibonacci number can be forward calculated from the base. A recursive implementation of this would be:
您对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);
}
The corresponding code for the sum would be:
总和的相应代码是：
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 recursion will often be changed by the compiler/interpreter into a simple loop as part of tail callremoval.
作为尾调用删除的一部分，尾递归通常会被编译器/解释器更改为一个简单的循环。
You asked:
你问：
I still couldn't figure out how the summation of the series works if I add 1. Can someone please explain??
如果我加 1，我仍然无法弄清楚该系列的总和是如何工作的。有人可以解释一下吗？？
This question is really about understanding the algorithm, which I would suppose is topical on SO. But, math is required to describe why the algorithm works. So, this is really a math question. There is a well known theorem regarding the sum of Fibonacci numbers. If F[i]is the i-th Fibonacci number, and S[n]is the sum of the first nFibonacci numbers, then the theorem above states:
这个问题实际上是关于理解算法，我认为这是关于 SO 的主题。但是，需要数学来描述算法的工作原理。所以，这真的是一道数学题。关于斐波那契数的和，有一个众所周知的定理。如果F[i]是第 i 个斐波那契数，并且S[n]是第一个n斐波那契数之和，则上述定理指出：
S[n] = F[n+2] - 1
So, if we consider that by definition of S[n+2],
所以，如果我们根据 的定义考虑S[n+2]，
S[n+2] = S[n+1] + F[n+2]
Then, substituting S[n] + 1for F[n+2]:
然后，取代S[n] + 1了F[n+2]：
S[n+2] = S[n+1] + S[n] + 1
Which you should recognize is your "add 1 modified" fibonaccifunction.
您应该认识到的是您的“添加 1 个修改”fibonacci功能。
Below is a proof by induction that your program computes the sum that I provided in my original answer. Let Frepresent your fibonaccifunction, and let Srepresent your "add 1 modified" fibonaccifunction.
以下是归纳证明，您的程序计算了我在原始答案中提供的总和。让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
Then, you want a proof that for k > 0:
然后，您需要一个证明k > 0：
k
.---
S[k] = > F[i]
`---
i = 1
Note that the above summation is true if and only if:
请注意，当且仅当：
S[1] = F[1]
S[k] = F[k] + S[k-1] for k > 1
The proof is fairly straight forward. The base cases are trivially true.
证明是相当直接的。基本情况是微不足道的。
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
The induction step is: Given that for some k > 2, S[j+1] = F[j+1] + S[j]for 0 < j < k+1, prove that the equality holds true if j = k+1, that is: S[k+2] = F[k+2] + S[k+1].
归纳步骤是： 鉴于对于某些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]
This completes the proof.
至此，证明完毕。
回答by óscar López
No it won't. The second version of the code does notcompute the sum of all the values of the fibonacci function up to the given value. And the base cases are wrong, too!
不，不会。代码的第二个版本不计算斐波那契函数的所有值的总和，直到给定的值。基本情况也是错误的！
If you want to calculate the sum recursively, split the problem in two parts, like this:
如果要递归计算总和，请将问题分为两部分，如下所示：
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);
}
The first function calculates fibonacci, the second takes care of adding the values up to a given number.
第一个函数计算斐波那契，第二个函数负责将值相加到给定的数字。
回答by Moshe Shamy
The right way to do it is use accumlator.
正确的做法是使用累加器。
the code should look something like this (i didn't check it, it's only the idea)
代码应该看起来像这样（我没有检查它，这只是想法）
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;
}
回答by Andrei Cernei
Recursively is a very inefficient way to calculate the Fibonacci number.After the number 43 it will take more then 30 sec till you'll have the answer. I tried to find out how much time will take to calculate the number 52 and it took about 47 minutes. So the time grows very fast.
递归是计算斐波那契数的一种非常低效的方法。在数字 43 之后，您将需要 30 秒以上的时间才能得到答案。我试图找出计算数字 52 需要多少时间，大约需要 47 分钟。所以时间增长得非常快。
The recursive code:
递归代码：
private int calculateRecursivelyInt(int fnum)
{
if (fnum == 0)
return 0;
if (fnum == 1)
return 1;
return calculateRecursivelyInt(fnum - 1) + calculateRecursivelyInt(fnum - 2);
}
Loops are much more efficient
循环效率更高
//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;
}
回答by thanga
another approach to print Fibonacci series using recursive function.
另一种使用递归函数打印斐波那契数列的方法。
#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);
}
回答by Floris
Your code needs to test for n<1- if you pass an argument of 0 or less, it will go on forever...
您的代码需要测试n<1- 如果您传递 0 或更少的参数，它将永远持续下去......
Other than that - if you call fib(5), here is what happens:
除此之外 - 如果你打电话给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
Your original method is good, but it depends on how you consider the "order" of a Fibonacci number (what do you want the first number to be).
您的原始方法很好，但这取决于您如何考虑斐波那契数的“顺序”（您希望第一个数字是什么）。
