前言
1. 递归
递归其实是⼀种解决问题的⽅法，在C语⾔中，递归就是函数⾃⼰调⽤⾃⼰。
递归的思想：
把⼀个⼤型复杂问题层层转化为⼀个与原问题相似，但规模较⼩的⼦问题来求解；直到⼦问题不能再
被拆分，递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。
2. 递归的限制条件
有2个必要条件：
• 递归存在限制条件，当满⾜这个限制条件的时候，递归便不再继续。
• 每次递归调⽤之后越来越接近这个限制条件。
递归举例1：
n的阶乘的公式： n！ = n ∗ (n − 1)!
那我们就可以写出函数Fact求n的阶乘，假设Fact(n)就是求n的阶乘，那么Fact(n-1)就是求n-1的阶
乘，函数如下：
int Fact(int n) { if(n<=0)//这两个都是限制条件 return 1; else return n*Fact(n-1); } #include <stdio.h> int Fact(int n) { if(n<=0) return 1; else return n*Fact(n-1); } int main() { int n = 0; scanf("%d", &n); int ret = Fact(n); printf("%d\n", ret); return 0; }
案例2
顺序打印⼀个整数的每⼀位.
输⼊⼀个整数m，打印这个按照顺序打印整数的每⼀位。
n是超过1位数的话，就得拆分每⼀位
1234%10就能得到4，然后1234/10得到123，这就相当于去掉了4
然后继续对123%10，就得到了3，再除10去掉3，以此类推
不断的 %10 和 \10 操作，直到1234的每⼀位都得到；
但是这⾥有个问题就是得到的数字顺序是倒着的
但是我们有了灵感，我们发现其实⼀个数字的最低位是最容易得到的，通过%10就能得到
那我们假设想写⼀个函数Print来打印n的每⼀位，如下表⽰
用代码实现
void Print(int n) { if(n>9) { Print(n/10); } printf("%d ", n%10); }
举例3：求第n个斐波那契数
例子：1 1 2 3 5…
前面两个数的和等于第三个
int Fib(int n) { if(n<=2) return 1; else return Fib(n-1)+Fib(n-2); } #include <stdio.h> int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; }
当我们n输⼊为50的时候，需要很⻓时间才能算出结果，这个计算所花费的时间，是我们很难接受的，
这也说明递归的写法是⾮常低效的，那是为什么呢？
其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计算，⽽且递归层次越深，冗余计算就会越多。所以我们有时要注意选择，斐波那契数的计算，使⽤递归是⾮常不明智的，我们就得想迭代的⽅式解决。
如下：
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; }
迭代的⽅式去实现这个代码，效率就要⾼出很多了。
