C语言题目：斐波那契数

斐波那契数列是什么？就是第一个数＋第二个数＝第三个数

例如：１＋１＝２　１＋２＝３

所以该去怎么设计呢，正好这几天正在学递归，我就想用递归的方式先写

１.递归写法

那我们怎么去求呢，假设我想求第４个斐波那契数我可以先把第三个求出来，再把第二个求出来

然后加在一起就是第四个，第三个可以用第二个和第一个求出来，这样就可以实现递归写法

代码：

int Fin(int a)
{
	if(a <= 2)//当a<2的时,返回1
	{
		return 1;
	}
	else
	return Fin(a-1)+Fin(a-2);//求第４个斐波那契数可以先把第三个和第二个求出来
}
int main()
{
	int a = 0;
	int ret = 0;
	printf("请输入n");
	scanf("%d",&a);
	ret = Fin(a);
	printf("ret = %d",ret);

}

看来成功了，但是它有一个巨大的弊端，假设我想求第100个斐波那契数，我就要把第99个斐波那契数和第98个斐波那契数给求出来，而第99个斐波那契数又要求第98、97个。。。一直求下去需要很大的计算量，所以并不是所有的题目都适合用递归，要分清楚形势。

2.不递归

不递归的写法就是循环嘛，蛮简单的

代码：

int fin2(int num) {
	int a = 1;
	int b = 1;
	int c = 1;//初始值为1方便输出第一个第二个斐波那契数
	while (num > 2) {
		c = a + b;
		a = b;
		b = c;
		num--;
	}
	return c;
}
int main() {
	int num = 0;
	int ret = 0;
	printf("请输入n");
	scanf("%d", &num);
	ret = fin2(num);
	printf("ret = %dn", ret);
}

 不管它值是否溢出，但它算出来了

你学废了吗