我们前一篇文章介绍了利用函数的递归来实现斐波那契数
代码如下：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<windows.h>
int Fib(int n){
if (n <= 2){
return 1;
}
else{
return Fib(n - 1) + Fib(n-2);
}
}
int main(void){
int n = 0;
int ret = 0;
printf("请输入：");
scanf("%d",&n);
ret = Fib(n);
printf("ret=%d\n",ret);
return 0;
}但是我们还有一个问题就是当我们输入一个50或者更加大的数字的时候程序就会出现卡死的情况，今天我们就来着重解决这个问题，首先我们再来熟悉一下什么是斐波那契数，说白了就是 当前值等于前两个数字的和，如 1 1 2 3 5 8，当我们输入一个数字的时候，程序便会去找这个数字的前面两个数，但是前面两个数字也是未知的，所以还需要倒推，如我们输入了一个50，程序就要执行下列的运算：
50 ---> 49 48
49 ---> 48 47
48 ---> 47 46
47 ---> 46 45
`````我们可以发现，在程序计算的时候有很多的操作是重复在做的，这些重复的运算量是巨大的，我们以40为例，将代码修改成如下形式：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int count = 0;
int Fib(int n){
if (n == 3){
count++;
}
if (n <= 2){
return 1;
}
else{
return Fib(n - 1) + Fib(n-2);
}
}
int main(void){
int n = 0;
int ret = 0;
printf("请输入：");
scanf("%d",&n);
ret = Fib(n);
printf("ret=%d\n",ret);
printf("count=%d\n",count);
return 0;
}我们创建一个全局变量count来帮助我们计数，在Fib()函数中加入
if(n==3){
count++;
}这个语句将会帮助我们计数程序重复计算的次数，最后在main()函数中输出count的值，如图所示：
我们可以看到仅仅是计算第40个斐波那契数，count变量统计到的重复运算次数就高达3900万次，随着用户输入的增大，重复的次数也将成指数倍增长，这也就是我们为什么输入更大一点的数字时候，程序会不响应，那有什么办法解决这个问题呢？
其实我们除了使用到递归还可以使用迭代，所谓迭代可以理解为重复的计算某一段代码，那么我们该怎么具体实现呢?
我们可以创建三个变量，这里使用a b c 作为变量名称，变量a与变量b用来存前两个斐波那契数，变量c用来存两数之和，算完之后我们将b的值放到a中，将c的值放到b中，如图所示：
a b c为第一次计算时候的值，当计算完成后原先b的值被a取代，c的值被b取代，所以我们可以写一个while()循环，来循环执行上述步骤，如以下代码：
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int Fib(int n){
int a = 1;
int b = 1;
int c = 1;
while (n > 2){
c = a + b;
a = b;
b = c;
n--;
}
return c;
}
int main(void){
int n = 0;
int ret = 0;
printf("请输入：");
scanf("%d",&n);
ret = Fib(n);
printf("ret=%d\n",ret);
return 0;
}c的值我们定为1，因为若c=0，当n的值小于等于2的时候则会跳过while()循环直接返回c的值，我们之前已经说过了，n小于等于2的时候应该返回1，所以将c的值确定为1是最好的，我们编译并运行上述代码，当我们再输入60的时候可以发现结果一下子就出来了，虽然结果可能是错误的，因为数字已经超过了int类型所能容纳的最大值，发生了溢出，如图所示：
2023/8/19
王起舟