分别用非递归和递归的方法编写函数求斐波那契数列第n项。斐波那契数列1，1，2，3，5，8，13，…

分别用非递归和递归的方法编写函数求斐波那契数列第n项。斐波那契数列1，1，2，3，5，8，13，…

#include 
#include 
typedef long long int int64;
//方法1，递归法
int64 Fibonacci(int n)
{
int64 sum;
if(n<=0)
{
printf("参数值非法!
");
exit(-1); //直接终止程序
}
if(n==1 || n==2)
return 1;
else
sum=Fibonacci(n-1)+Fibonacci(n-2);
return sum;
}
//方法2，非递归法
int64 Fibonacci2(int n)
{
int64 a,b,c;
if(n<=0)
{
printf("参数值非法!
");
exit(-1); //直接终止程序
}
if(n==1 || n==2)
return 1;
a=b=1;  //对前两项的值初始化
n=n-2; //因为是从第3项开始记次数，所以减2
while(n > 0)
{
c=a+b;
a=b;
b=c;
n--;
}
return c;
}
//测试主函数
int main()
{
int n;
scanf("%d",&n); //输入n
//printf("F(%d)=%lld
",n,Fibonacci(n));
printf("F(%d)=%lld
",n,Fibonacci2(n));
return 0;
}
//示例运行结果
F:c_work>a.exe
5
F(5)=5

F:c_work>a.exe
6
F(6)=8

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息