【C语言】函数的系统化精讲（三）1：https://developer.aliyun.com/article/1474657
3.1递归的思考
递归是一种有用的编程技巧，但像其他技巧一样，也容易被误用。举例来说，看到推导的公式，很容易就被写成递归的形式犹如数学函数一样。
int Fact(int n) { if(n<=0) return 1; else return n*Fact(n-1); } • 1 • 2 • 3 • 4 • 5 • 6 • 7
Fact函数是可以产⽣正确的结果，但是在递归函数调⽤的过程中涉及⼀些运⾏时的开销。
什么是运行时的开销呢？
在C语言中，每次函数调用都需要在栈区为本次函数调用申请一块内存空间，用来保存函数调用期间的各种局部变量的值。这块空间被称为运行时堆栈，或者函数栈帧。如果函数没有返回，对应的栈帧空间就会一直被占用。因此，如果函数调用中存在递归调用，每次递归函数调用都会开辟属于自己的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。因此，如果采用函数递归的方式完成代码，递归层次太深就会浪费太多的栈帧空间，也可能引起栈溢出（stack overflow）的问题。
所以如果不想使用递归就得想其他的办法，通常就是迭代的方式（通常就是循环的方式）。
⽐如：计算n的阶乘，也是可以产⽣1~n的数字累计乘在⼀起的。
int Fact(int { 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 = Fact(n); printf("%d\n", ret); return 0; }
上述代码是能够完成任务，并且效率是⽐递归的⽅式更好的。
事实上，我们看到的许多问题是以递归的形式进⾏解释的，这只是因为它⽐⾮递归的形式更加清晰，
但是这些问题的迭代实现往往⽐递归实现效率更⾼。
当⼀个问题⾮常复杂，难以使⽤迭代的⽅式实现时，此时递归实现的简洁性便可以补偿它所带来的运⾏时开销。
3.2求第n个斐波那契数
我们还可以举出更极端的例子，比如计算第n个斐波那契数，不适合使用递归求解，但是斐波那契数的问题通常是用递归的形式描述的，如下:
看到这公式，很容易想到这还不简单啊，将代码递归的形式走起，如：
int Fib(int n) { if(n<=2) return 1; else return Fib(n-1)+Fib(n-2); }
当我们输入为50时，光标还在闪烁需要很长时间才能算出结果，这个计算所花费的时间，是我们很难接受的，这也说明递归的写法是非常低效的，那是为什么呢？ 
此时程序并没有停止，而是不断的计算，我们可以Ctrl+Shift+Esc打开任务管理器，我们可以看到我们的程序的CPU占比13.7%（这个13.7%不是最高的），（由于代码运行起来后，电脑便会风扇转起，直接CPU干起来，博主电脑无法立刻截不了图，所以导致截图不到想要的高CPU运行百分比，推荐你们也可以尝试一下）
其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计算，⽽且递归层次越深，冗余计算就会越多。
这里我们发现，在计算第40个斐波那契数时，使用递归方式会导致第3个斐波那契数被重复计算了39088169次，这些计算是非常冗余的。因此，斐波那契数的计算采用递归是非常不明智的，我们应该考虑使用迭代的方式来解决。
我们知道斐波那契数的前2个数都是1，然后前2个数相加就是第3个数，那么我们从前往后，从小到大计算就可以了。
这样就有下⾯的代码 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; }
总结
递归虽好，但是也会引⼊⼀些问题，所以我们⼀定不要迷恋递归，适当就好。
递归和循环的选择：
1，如果使用递归写代码，非常容易，写出的代码没问题，那就使用递归。
2，如果递归写出的问题，是存在明显的缺陷，那就不能使用递归，得用迭代的方式处理。
