求斐波那契数列的某一项，常用的两种方法（C语言实现）

#include

//求斐波那契数列的第n项 
//递归复杂度高，不推荐使用 
int vibonaqiI(int n);
int vibonaqiII(int n);
int main(){
	
	while(1){
		int n = 0;
		printf("请输入一个数字:n");
		scanf("%d",&n);
		if(n == 886){
			break;
		}
		int result = vibonaqiII(n-1);//时间复杂度为O(n); 
//		int result = vibonaqiI(n-1);//时间复杂度为O(2^n)
		printf("第%d项为：%dn",n,result);
	}
	printf("再见n");
	
	return 0;
}
//递归实现 
int vibonaqiI(int n){
	if(n<=0){
		return 0;
	}
	else if(n<=2){
		return 1;
	}
	else{
		return vibonaqiI(n-1)+vibonaqiI(n-2);//每次都会执行到n=0，
											//然后全部弹栈消失才能得出结果 ，方法调用了2*2*2...次 
	}
}

//循环实现 
int vibonaqiII(int n){
	int result = 1;
	int num = 0;
	int i;
	if(n<=0){
		return num;
	}
	else if(n<=2){
		return result;
	}
	else{
		for(i = 0;i