1.什么是递归
递归是学习C语⾔函数绕不开的⼀个话题，那什么是递归呢？
递归其实是⼀种解决问题的⽅法，在C语⾔中，递归就是函数⾃⼰调⽤⾃⼰。
写⼀个史上最简单的C语⾔递归代码：
#include<stdio.h>
int main() {
printf("hollow,world");
main();//在main函数调用main
return 0;
}
上述就是⼀个简单的递归程序，只不过上⾯的递归只是为了演⽰递归的基本形式，不是为了解决问
题，代码最终也会陷⼊死递归，导致栈溢出（Stack overflow）；
递归的思想：
把⼀个⼤型复杂问题层层转化为⼀个与原问题相似，但规模较小的⼦问题来求解；直到⼦问题不能再被拆分，递归就结束了。所以递归的思考⽅式就是把⼤事化小的过程。
递归中的递就是递推的意思，归就是回归的意思，接下来慢慢来体会。
2.递归的限制条件：
递归在书写的时候，有2个必要条件：
- 递归存在限制条件，当满足这个限制条件的时候，递归便不再继续。
- 每次递归调⽤之后越来越接近这个限制条件。
在下⾯的例⼦中，我们逐步体会这2个限制条件。
3.递归举例
例1：求n的阶乘
———————————————————————————————————————————
#include<stdio.h>
int fact(int x) {
if (x <= 0) {
return 1;
}
else
{
return x * fact(x - 1);
}}
int main() {
int a=0;
scanf("%d", &a); //n的阶乘
int ret = fact(a); //函数将a的值传过去
printf("%d", ret);
return 0;
}
分析
我们知道n的阶乘的公式： n ！ = n ∗ ( n − 1)!
举例：
5! = 5*4*3*2*1
4! = 4*3*2*1
所以:5! = 5*4
n!—> n*(n-1)! (n-1)! —> (n-1)*(n-2)!
......直到n=1 or n=0，将不再分解
再稍微分析⼀下，当 n<=1 的时候，n的阶乘是1，其余n的阶乘都是可以通过上述公式计算。
n的阶乘的递归公式如下：
画图推演
为了理解递归的运行方式，我们画图推演一下吧
例2：顺序打印一个整数的每⼀位
void Print(int n)
{
if (n > 9)
{
Print(n / 10);
}
printf("%d ", n % 10);
}int main()
{
int m = 0;
scanf("%d", &m);
Print(m);
return 0;
}
输出结果 ：
画图推演
迭代与递归
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。
int Fact(int n)
{
int i = 0;
int ret = 1;
for(i=1; i<=n; i++)
{
ret *= i;
}
return ret;
}
上述代码是能够完成任务，并且效率是⽐递归的⽅式更好的。
事实上，我们看到的许多问题是以递归的形式进行解释的，这只是因为它⽐⾮递归的形式更加清晰， 但是这些问题的迭代实现往往⽐递归实现效率更⾼。
当⼀个问题⾮常复杂，难以使⽤迭代的⽅式实现时，此时递归实现的简洁性便可以补偿它所带来的运 ⾏时开销。
注意：
有时候，递归虽好，但是也会引发⼀些问题，所以我们⼀定不要迷恋递归，适可而止就好
———————————————————————————————————————————
