使用递归算法求Fibonacci数列的第n项，第一项是1，第二项是1，第n项是前两项之和

使用递归算法求Fibonacci数列的第n项，第一项是1，第二项是1，第n项是前两项之和

int F(int n)
{
if(n==0) //比较用==
return 1;
    else if(n==1) //比较用==
return 1;
else
return (F(n-1)+F(n-2));
}

int F(int n)
{
if(n==1||!n)
return 1;
else
return F(n-1)+F(n-2);
}
比较大小是用==，,n=1是先将n赋值为1再判断n是否不为0
n==0可简写为!n，||是逻辑运算符“或”
其实上面的程序是指数时间复杂度，下面程序则是线性时间复杂度的：
int F(int n)
{
int a=1,b=1;
for(int i=2;i<=n;i++)
{
int c=a+b;
a=b;
b=c;
}
return b;
}
其实还有一种方法，是利用二维矩阵{1 1}{1 0}的幂实现的，对数时间复杂度。如果感兴趣可以查一下，网上资料很多的。由于代码太长，我这里就不写出来了