迭代（非递归）：循环就是一种迭代，迭代可以理解成循环
我们什么时候优先用迭代呢？
（1）递归层次太深时，栈溢出程序会崩溃
（2）递归的过程中有很多计算在一直重复，程序效率低
7.3.1 练习3
求n的阶乘。（不考虑溢出）
代码1——用递归写
#include<stdio.h> int Fac(int n) { if (n <= 1) { return 1; } else { return n * Fac(n - 1); } } int main() { int n = 0; scanf("%d", &n); int ret = Fac(n); printf("%d", ret); return 0; }
《函数栈帧》
每一个函数调用都会为本次函数调用分配内存空间（是内存的栈区），为本次函数调用分配的内存空间就被称为这函数调用的栈帧空间。
函数栈帧的创建和递归！
递归层次太深，就会栈溢出程序崩溃！
例如：使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。
更改：代码2——迭代
#include<stdio.h> int Fac(int n) { int i = 0; int ret = 1; for (i = 1; i <= n; i++) { ret *= i; } return ret; } int main() { int n = 0; scanf("%d", &n); int ret = Fac(n); printf("%d\n", ret); return 0; }
好处：这时程序是不会栈溢出，也就不会崩溃！（虽然结果是错的，但是不会崩——int的数据范围小了，这讲的是思想）
当递归层次太深时——非递归
7.3.2 练习4
求第n个斐波那契数
代码1——递归
#include<stdio.h> int Fib(int n) { if (n <= 2) { return 1; } else { return Fib(n - 1) + Fib(n - 2); } } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; }
发现在使用 fib 这个函数的时候如果我们要计算第 50 个斐波那契数字的时候特别耗费时间
为什么呢？
我们发现 fib 函数在调用的过程中很多计算其实在一直重复。
我们更改一下代码——看看第3个斐波那契数被重复计算了多少次
#include<stdio.h> int count = 0; int Fib(int n) { if (3 == n)//统计第三个斐波那契数被计算的次数 { count++; } if (n <= 2) { return 1; } else { return Fib(n - 1) + Fib(n - 2); } } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); printf("%d\n", count); return 0; }
从代码结果：第3个斐波那契数重复了39088169次，——效率低
改成迭代
代码2——迭代
减少了重复运算，提高了效率
#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() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; }
总结：
1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销
递归存在的问题：
（1）递归层次太深时， 那就会报错： stack overflow （栈溢出） 这样的信息。
系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。
（2）递归的过程中存在大量的重复计算（效率低）
那如何解决上述的问题：
1. 将递归改写成非递归。（迭代就是非递归）
2. 使用 static 对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代
nonstatic 局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放nonstatic 对象的开销，而且 static 对象还可以保 存递归调用的中间状态，并且可为各个调用层所访问。（static是存放在静态区的）
