我很难理解为什么
#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;
}
导致分段错误。一旦 x 下降到 1，它最终不应该返回吗？
问问题
154308 次
13 回答
150
当x==2你打电话fib(1)时fib(0)：
return fib(2-1)+fib(2-2);
fib(0)考虑评估时会发生什么......
于 2009-10-05T07:52:49.447 回答
40
原因是斐波那契数列以两个已知实体 0 和 1 开始。您的代码只检查其中一个（是一个）。
将您的代码更改为
int fib(int x) {
if (x == 0)
return 0;
if (x == 1)
return 1;
return fib(x-1)+fib(x-2);
}
包括 0 和 1。
于 2009-10-05T07:56:34.467 回答
11
为什么不使用迭代算法？
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;
}
于 2009-10-05T08:14:08.113 回答
7
根据定义，斐波那契数列中的前两个数字是 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));
}
于 2014-08-12T18:03:40.683 回答
3
我认为这个解决方案很短，看起来不错：
long long fib(int n){
return n<=2?1:fib(n-1)+fib(n-2);
}
编辑：正如 jweyrich 提到的，真正的递归函数应该是：
long long fib(int n){
return n<2?n:fib(n-1)+fib(n-2);
}
（因为 fib(0) = 0。但基于上述递归公式，fib(0) 将为 1）
要理解递归算法，你应该在你的论文上画画，最重要的是：“Think normal as often”。
于 2012-07-07T04:54:24.463 回答
3
这是我用递归解决斐波那契问题的方法。
#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;
}
于 2016-03-15T13:13:24.390 回答
2
int fib(int n) {
if (n == 1 || n == 2) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}
在斐波那契数列中，前 2 个数字始终为 1，然后每次值变为 1 或 2 时，它必须返回 1
于 2013-03-03T15:00:34.157 回答
1
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));
}
于 2013-04-29T07:10:00.327 回答
1
int fib(int x)
{
if (x < 2)
return x;
else
return (fib(x - 1) + fib(x - 2));
}
于 2013-09-17T12:38:41.187 回答
1
if(n==1 || n==0){
return n;
}else{
return fib(n-1) + fib(n-2);
}
但是，使用递归来获取斐波那契数是不好的做法，因为调用函数的次数大约是接收到的数的 8.5 次。例如要获得 30 的斐波那契数 (1346269) - 函数被调用 7049122 次！
于 2013-12-10T09:19:24.233 回答
0
我的解决方案是：
#include <iostream>
int fib(int number);
void call_fib(void);
int main()
{
call_fib();
return 0;
}
void call_fib(void)
{
int input;
std::cout<<"enter a number\t";
std::cin>> input;
if (input <0)
{
input=0;
std::cout<<"that is not a valid input\n" ;
call_fib();
}
else
{
std::cout<<"the "<<input <<"th fibonacci number is "<<fib(input);
}
}
int fib(int x)
{
if (x==0){return 0;}
else if (x==2 || x==1)
{
return 1;
}
else if (x>0)
{
return fib(x-1)+fib(x-2);
}
else
return -1;
}
如果为负，则返回 fib(0)=0 和错误
于 2016-11-02T21:18:04.527 回答
0
我认为这是使用递归的斐波那契的最佳解决方案。
#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
ull FIBO[100005];
using namespace std;
ull fibo(ull n)
{
if(n==1||n==0)
return n;
if(FIBO[n]!=0)
return FIBO[n];
FIBO[n] = (fibo(n-1)+fibo(n-2));
return FIBO[n];
}
int main()
{
for(long long i =34;i<=60;i++)
cout<<fibo(i)<<" " ;
return 0;
}
于 2017-02-02T15:51:54.983 回答
0
我认为所有这些解决方案都是低效的。他们需要大量的递归调用才能得到结果。
unsigned fib(unsigned n) {
if(n == 0) return 0;
if(n == 1) return 1;
return fib(n-1) + fib(n-2);
}
此代码需要 14 次调用才能获得 fib(5) 的结果，fin(10) 需要 177 次调用，fib(30) 需要 2.7kk 次。
你最好使用这种方法，或者如果你想使用递归，试试这个：
unsigned fib(unsigned n, unsigned prev1 = 0, unsigned prev2 = 1, int depth = 2)
{
if(n == 0) return 0;
if(n == 1) return 1;
if(depth < n) return fib(n, prev2, prev1+prev2, depth+1);
return prev1+prev2;
}
此函数需要 n 次递归调用来计算 n 的斐波那契数。您仍然可以通过调用 fib(10) 来使用它，因为所有其他参数都有默认值。
于 2018-08-05T07:54:19.323 回答