C/C++フィボナッチ(Fibonacci)の再帰と非再帰の実現

フィボナッチ数列(Fibonacci sequence)は、黄金分割数列とも呼ばれ、数学者レオナルド・フィボナッチ(Leonardoda Fibonacci)がウサギの繁殖を例に導入したことから「ウサギ数列」とも呼ばれ、1、1、2、3、5、8、13、21、34、・・・を指す.数学的には,フィボナッチ数列は,F(1)=1,F(2)=1,F(n)=F(n−1)+F(n−2)(n≧3,n∈N*)という繰返し法で定義される.この数列は3項目から始まり、各項は前の2項の和に等しい.
コード:再帰実装:nの前項をすべて算出し,最終的にn項目を得る.nが比較的大きいと,時間的複雑度が高くなる.

#include
#include
#include
#include
 
const int maxn=1e5+10;
long long Fib[maxn];
 
long long Fibonacci(int x)
{
	if(Fib[x]!=0)
	return Fib[x];
	else
		return Fib[x]=Fibonacci(x-1)+Fibonacci(x-2);
}
 
int main()
{
	memset(Fib,0,sizeof(Fib));
	Fib[0]=1;Fib[1]=1;Fib[2]=1;Fib[3]=2;
	int x;
	printf("          n      :(        50)
");
	scanf("%d",&x);
	printf("%d
",Fibonacci(x));
	return 0;
}

非再帰的な実装:

#include
#include
 
long long Fib[50];
 
int main()
{
	memset(Fib,0,sizeof(Fib));
	Fib[0]=1,Fib[1]=1,Fib[2]=1,Fib[3]=2;
	int x;
	printf("        50  ，            :
");
	scanf("%d",&x);
	for(int i=4;i<=x;i++)
		Fib[i]=Fib[i-1]+Fib[i-2];
	printf("%lld
",Fib[x]);
	return 0;
}