recursion斐波那契

我很难理解为什么

#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不应该最终返回？

Answer 1

当x==2你可以调用fib(1)和fib(0) ：

 return fib(2-1)+fib(2-2); 

考虑当评估fib(0)时会发生什么…

Answer 2

原因是因为斐波那契数列从两个已知的实体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。

Answer 3

为什么不使用迭代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; } 

Answer 4

根据定义，Fibonacci序列中的前两个数字是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)); } 

Answer 5

我认为这个解决scheme很短，看起来很好看：

 long long fib(int n){ return n<=2?1:fib(n-1)+fib(n-2); } 

编辑：正如jweyrich提到的，真正的recursion函数应该是：

 long long fib(int n){ return n<2?n:fib(n-1)+fib(n-2); } 

（因为fib（0）= 0，但基于上面的recursion公式，fib（0）将是1）

要理解recursionalgorithm，你应该引用你的论文，最重要的是：“经常思考”。

Answer 6

 int fib(int n) { if (n == 1 || n == 2) { return 1; } else { return fib(n - 1) + fib(n - 2); } } 

在斐波那契数列中，前两个数字总是后缀为1，那么每次数值变成1或2时必须返回1

Answer 7

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

Answer 8

这是我解决斐波那契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; } 

Answer 9

 int fib(int x) { if (x < 2) return x; else return (fib(x - 1) + fib(x - 2)); } 

Answer 10

 if(n==1 || n==0){ return n; }else{ return fib(n-1) + fib(n-2); } 

然而，使用recursion来获得斐波那契数是不好的做法，因为函数被调用大约8.5倍的次数。 例如得到斐波那契数30（1346269） – 函数被称为7049122次！

Answer 11

我的解决scheme是：

 #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，如果是负的则返回错误

Answer 12

我认为这是使用recursion的斐波那契最好的解决scheme。

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