== Fibonacci数列在所有递推关系中，最为人们熟知，在较为复杂的Basic，Pascal，C语言中，Fibonacci数列这类的问题因为解法相对简单，也就逐渐退出了竞赛的舞台。但这并不代表Fibonacci数列没有任何研究价值，反之，它能带给我们一些不一样的启发。
Fibonacci数列的代表问题便是由意大利著名数学家Fibonacci于1202年提出的兔子繁殖问题，（又被称为“Fibonacci问题“）
兔子繁殖问题：
有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子，问过n个月共有多少对兔子?
还是先找找规律。
第一个月：一对新兔子r1（用小写字母表示新兔子）。
第二个月：还是一对新兔子，不过已经长大，具备生育能力了，用大写字母R1表示。
第三个月：R1生了一对新兔子r2，总共三对。
第四个月：R1又生了一对新兔子r3，一共三对。另外，r2长大了，变成R2.
第五个月：R1和R2各生一对，记为r4和r5，共五对，此外，r3变成R3.
第六个月：R1，R2，R3各生一对，记为r6，r7，r8。此外，r4和r5长大了。
.............................
我们可以根据这个画一个表格：
通过观察这份表格，我们不难发现：
若设满x个月共有兔子对，其中当月出生的兔子数目为
对。第x-1个月留下的兔子数目设为
对。则：
=
+
=
（即第x-2个月的所有兔子到第x月都有繁殖能力了）
=
+
边界条件：=0，
=1
由上面的递推关系式可依次得到：
=
+
=1,
=
+
=2.............
可能上面的表格不大直观，附上另一种表格：
不管是大兔子还是小兔子，纵使前几个值是不一样的，但是到后面也开始遵循1，1，2，3，5，8............
再观察这个顺序我们不难发现，前两项相加等于第三项，即=
+
。
那么兔子繁殖这个代码就不难敲出：
#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
int i,a[100],n;
cin>>n;
a[1]=1;
a[2]=1;
for (i=3; i<=n; i++)
a[i]=a[i-1]+a[i-2];
cout<<a[n];
}
因此我们也可以通过这个规律来完成递归的代码：
计算第n个斐波那契数：
#include<bits/stdc++.h>
using namespace std;
int fb(int n){
if(n==1)return 1;
if(n==2)return 1;
else return fb(n-1)+fb(n-2);
}
int main(){
int n;
cin>>n;
cout<<fb(n);
return 0;
}
附上非递归代码：
#include<bits/stdc++.h>
using namespace std;
int f(int n){
int a,a1=1,a2=1;
for(int i=3;i<=n;i++)
{
a=a1+a2;a1=a2;a2=a;
}
if(n==1||n==2)return 1;
else return a;
}
int main(){
int n;
cin>>n;
cout<<f(n);
return 0;
}
