C++ 递归斐波那契
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1518726/
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
Recursive Fibonacci
提问by Ian Burris
I'm having a hard time understanding why
我很难理解为什么
#include <iostream>
using namespace std;
int fib(int x) {
if (x == 1) {
return 1;
} else {
return fib(x-1)+fib(x-2);
}
}
int main() {
cout << fib(5) << endl;
}
results in a segmentation fault. Once x gets down to 1 shouldn't it eventually return?
导致分段错误。一旦 x 下降到 1 它不应该最终返回吗？
回答by Georg Fritzsche
When x==2you call fib(1)and fib(0):
当x==2您调用fib(1)和 时fib(0)：
return fib(2-1)+fib(2-2);
Consider what will happen when fib(0)is evaluated...
考虑fib(0)评估时会发生什么......
回答by LiraNuna
The reason is because Fibonacci sequence starts with twoknown entities, 0 and 1. Your code only checks for one of them (being one).
原因是因为斐波那契数列以两个已知实体 0 和 1开始。您的代码仅检查其中之一（为一个）。
Change your code to
将您的代码更改为
int fib(int x) {
if (x == 0)
return 0;
if (x == 1)
return 1;
return fib(x-1)+fib(x-2);
}
To include both 0 and 1.
包括 0 和 1。
回答by Dzmitry Huba
Why not use iterative algorithm?
为什么不使用迭代算法？
int fib(int n)
{
int a = 1, b = 1;
for (int i = 3; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
回答by Vanji
By definition, the first two numbers in the Fibonacci sequence are 1 and 1, or 0 and 1. Therefore, you should handle it.
根据定义，斐波那契数列中的前两个数字是 1 和 1，或 0 和 1。因此，您应该处理它。
#include <iostream>
using namespace std;
int Fibonacci(int);
int main(void) {
int number;
cout << "Please enter a positive integer: ";
cin >> number;
if (number < 0)
cout << "That is not a positive integer.\n";
else
cout << number << " Fibonacci is: " << Fibonacci(number) << endl;
}
int Fibonacci(int x)
{
if (x < 2){
return x;
}
return (Fibonacci (x - 1) + Fibonacci (x - 2));
}
回答by Pedro Eugénio
This is my solution to fibonacci problem with recursion.
这是我用递归解决斐波那契问题的方法。
#include <iostream>
using namespace std;
int fibonacci(int n){
if(n<=0)
return 0;
else if(n==1 || n==2)
return 1;
else
return (fibonacci(n-1)+fibonacci(n-2));
}
int main() {
cout << fibonacci(8);
return 0;
}
回答by hqt
I think this solution is short and seem looks nice:
我认为这个解决方案很短而且看起来不错：
long long fib(int n){
return n<=2?1:fib(n-1)+fib(n-2);
}
Edit : as jweyrich mentioned, true recursive function should be:
编辑：正如 jweyrich 提到的，真正的递归函数应该是：
long long fib(int n){
return n<2?n:fib(n-1)+fib(n-2);
}
(because fib(0) = 0. but base on above recursive formula, fib(0) will be 1)
（因为 fib(0) = 0。但基于上述递归公式，fib(0) 将为 1）
To understand recursion algorithm, you should draw to your paper, and the most important thing is : "Think normal as often".
要理解递归算法，你应该画你的论文，最重要的是：“经常思考正常”。
回答by noelyahan
int fib(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}
in fibonacci sequence first 2 numbers always sequels to 1 then every time the value became 1 or 2 it must return 1
在斐波那契数列中，前 2 个数字总是后继为 1，然后每次该值变为 1 或 2 时，它必须返回 1
回答by user2331083
int fib(int x)
{
if (x == 0)
return 0;
else if (x == 1 || x == 2)
return 1;
else
return (fib(x - 1) + fib(x - 2));
}
回答by zod
int fib(int x)
{
if (x < 2)
return x;
else
return (fib(x - 1) + fib(x - 2));
}
回答by Jokerius
if(n==1 || n==0){
return n;
}else{
return fib(n-1) + fib(n-2);
}
However, using recursion to get fibonacci number is bad practice, because function is called about 8.5 times than received number. E.g. to get fibonacci number of 30 (1346269) - function is called 7049122 times!
然而，使用递归来获得斐波那契数是不好的做法，因为函数被调用的次数是接收数的 8.5 倍。例如，要获得 30 (1346269) 的斐波那契数 - 函数被调用 7049122 次！
