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

/**

已知Fibonacci数列：1,1,2,3,5,8,……，F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)

*/

#include

#include

typedef long long int int64;

//方法1，递归法

int64 Fibonacci(int n)

{

int64 sum;

if(n<=0)

{

printf("参数值非法!\n");

exit(-1); //直接终止程序

}

if(n==1 || n==2)

return 1;

else

sum=Fibonacci(n-1)+Fibonacci(n-2);

return sum;

}

非递归法

int64 Fibonacci2(int n)

{

int64 a,b,c;

if(n<=0)

{

printf("参数值非法!\n");

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",n,Fibonacci(n));

printf("F(%d)=%lld\n",n,Fibonacci2(n));

return 0;

}

//示例运行结果

F:\c_work>a.exe

5

F(5)=5

F:\c_work>a.exe

6

F(6)=8

program fibo;var n,i:integer; rs:extended;function fib(m:integer):extended;var a,b:extended;

begin

a:=1;b:=1;if m<=2 then exit(1)else while m>3 do begin

fib:=a+b;a:=b;b:=fib;m:=m-1;end;exit(fib);end;

begin

read(n);writeln(fib(n));end.

扩展资料：

从第二项开始，每个偶数项的平方都比前后两项之积少1，每个奇数项的平方都比前后两项之积多1。

如：第二项1的平方比它的前一项1和它的后一项2的积2少1，第三项2的平方比它的前一项1和它的后一项3的积3多1。

（注：奇数项和偶数项是指项数的奇偶，而并不是指数列的数字本身的奇偶，比如从数列第二项1开始数，第4项5是奇数，但它是偶数项，如果认为5是奇数项，那就误解题意，怎么都说不通）

证明经计算可得：[f(n)]^2-f(n-1)f(n+1)=(-1)^(n-1)

参考资料来源：百度百科-斐波那契数列

/**
已知Fibonacci数列：1,1,2,3,5,8,……，F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)
*/
#include 
#include 
typedef long long int int64;
//方法1，递归法
int64 Fibonacci(int n)
{
	int64 sum;
	if(n<=0)
	{
		printf("参数值非法!\n");
		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("参数值非法!\n");
		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",n,Fibonacci(n));
	printf("F(%d)=%lld\n",n,Fibonacci2(n));
	return 0;
}
//示例运行结果
F:\c_work>a.exe
5
F(5)=5

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