了解斐波那契数列
斐波那契数列的排列是：1，1，2，3，5，8，13，21，34，55，89，144……
依次类推下去，你会发现，它后一个数等于前面两个数的和。在这个数列中的数字，就被称为斐波那契数。
我们用递归的方式实现一遍，再代入一个具体的值，将简单的思路图展现出来
用递归的方法实现（代码）
#include <stdio.h> //函数声明及定义，返回值为int型 int Fib(int n) { //斐波那契数列第一个数和第二个数都为1 //故递归在n > 2 时开始 if (n > 2) //根据斐波那契数列的特点 //前两个数的和等于第三个数 //即第 n 个数等于 第 n - 1 个数加第 n - 2 个数 return Fib(n - 1) + Fib(n - 2); //所求的n <= 2时，直接返回1 else return 1; } int main() { int n; printf("请输入要求第几个斐波那契数："); scanf("%d", &n); printf("第%d个斐波那契数为%d\n", n,Fib(n)); return 0; }
用递归的方法实现（运行结果图）
递归方法思路图
求解第n个斐波那契数可以选择用递归的方式或者迭代的方式，我们再用学习得比较早的迭代（循环）的方式实现一遍
用迭代的方法实现（代码）
int Fib(int n) { int a = 1, b = 1, c = 1; for (;n > 2;n--) { c = a + b; a = b; b = c; } return c; } #include <stdio.h> int main() { int n; printf("请输入要求第几个斐波那契数："); scanf("%d", &n); printf("第%d个斐波那契数为%d\n", n,Fib(n)); return 0; }
用迭代的方法实现（运行结果图）
小结与对比思考
对比两个方法，发现：用迭代的方法效率会更高一些，在递归中，进行了大量重复的运算，导致效率比较慢。
下面我们验证一下
通过代码具体来看一下之前写的递归法中，n = 3被重复运算的次数
#include <stdio.h> int count ; int Fib(int n) { if (n > 2) { if (n == 3) { count++; } return Fib(n - 1) + Fib(n - 2); } else return 1; } int main() { int n; printf("请输入要求第几个斐波那契数："); scanf("%d", &n); printf("第%d个斐波那契数为%d\n", n, Fib(n)); printf("n = 3被重复运算的次数为：%d次\n", count); return 0; }
运行结果为：
越往后重复的次数会增加得更加多
由于重复的次数太多，当想要求第50个斐波那契数时，就需要等上十多分钟甚至更久......
如下图：一步步递归下去，就会发现很多数是重复参与了很多运算的
总结
函数递归往往能用简短的代码实现复杂的问题
其思想的最主要特点是：大事化小
而实际上，很多题都能够使用两种方法来实现，这时我们就需要通过自己判断
选择哪种方法就显得尤为重要了。
