一、递归定义
程序调用自身的编程技巧称为递归（recursion）。
递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的。
void recursion(){ statements; recursion();}函数调用函数本身。
C 语言支持递归，即一个函数可以调用其自身。但在使用递归时，程序员需要注意定义一个从函数退出的条件，否则会进入死循环。
递归函数在解决许多数学问题上起了至关重要的作用，比如计算一个数的阶乘、生成斐波那契数列，等等。
二、递归的必要条件
存在限制条件，当满足这个限制条件的时候，递归便不再继续。
每次递归调用之后越来越接近这个条件。
例1：输入一个整数，按顺序打印每一位数字
#include void PrintDigit(int n){if (n > 9){PrintDigit(n / 10);}printf("%d ",n % 10);}int main(){int num = 0;scanf("%d",&num);PrintDigit(num);return 0;}打印结果是1 2 3 4
就是相当于用这个函数一直除10，除到只有一位数的时候就打印。
先递后归，名为递归
先递：先除以10到个位，后归：再从后往前依次打印。
递归是嵌套的调用函数，进入函数的过程是递去，函数返回来的过程是归来；递进结束时开始回归。
递归应当存在限制条件，当逐渐接近并达到这个条件时函数就开始回归；如果没有这个限制条件，函数就会一直递下去，直至栈溢出(Stack overflow)才会结束。
每一次函数调用都要在栈区申请空间，无限递进就导致栈区空间被占满。
例2、写一个函数求字符串长度，要求使用递归
#include int StringLength(char* str) //传来的参数str是数组首元素的地址{if (*str == '\0')//只要遇到\0就结束递去，开始归来{return 0;}return 1 + StringLength(str + 1);//只要不是\0返回值就加一//(str + 1)可以实现数组元素的遍历}//此处不能使用str++，因为str++是先使用再运算，会导致无限递归 //最好也不要使用++str，虽然++str可以实现功能，但它会导致str的值发生变化int main(){char ch[] = "abc";int len = StringLength(ch);printf("%d",len);return 0;}三、递归与迭代
迭代是函数内某段代码实现循环，迭代与普通循环的区别是，迭代中参与运算的变量同时是保存结果的变量。
引例：写一个函数计算斐波那契数列的某一项
递归
#include int Fibonacci(int n){if (n == 0){return 0;}else if (n == 1){return 1;}return Fibonacci(n - 1) + Fibonacci(n - 2);}int main(){int i = 0;scanf("%d",&i);printf("%d\n", Fibonacci(i));return 0;}在要计算的项数较低时，没有太大问题，但是项数较大时，我们就会发现程序运行的时间很长。原因是这段代码的效率很低，时间复杂度是O(2^n)。
对于每一个非基本情况的输入n，函数Fibonacci(n)都会调用自身两次：Fibonacci(n-1)和Fibonacci(n-2)。这意味着计算量随着n的增加呈现指数增长。
对于每个n值，以下是递归调用的情况：
- Fibonacci(n) 调用 Fibonacci(n-1) 和 Fibonacci(n-2)
- Fibonacci(n-1) 调用 Fibonacci(n-2) 和 Fibonacci(n-3)
- Fibonacci(n-2) 调用 Fibonacci(n-3) 和 Fibonacci(n-4)
- 以此类推…
可以注意到，对于大于等于3的n，Fibonacci(n-2)被计算了两次，其中一次是直接递归调用，另一次是通过Fibonacci(n-1)的调用。这种重复计算随着n的增长急剧增加，因此，这个函数的时间复杂度是指数级别的，具体来说是O(2^n)。
我们创建一个全局变量counter来计算第三项被计算了几次
#include int counter = 0;int Fibonacci(int n){if (n == 3){counter++;}if (n == 0){return 0;}else if (n == 1){return 1;}return Fibonacci(n - 1) + Fibonacci(n - 2);}int main(){int i = 0;scanf("%d", &i);printf("%d\n", Fibonacci(i));printf("%d ",counter);return 0;}我们发现，要计算第四十项的值，要计算39088169次第三项，可见此代码效率很低下。
想要算40 项
就要算3938 项
就要算38 373736项
就要算37 36 36 35 36 35 35 34项
就要算……
迭代
#include int Fibonacci(int n){int c = 1, a = 1, b = 1;for (int i = 1; i <= n - 2; i++){c = a + b;a = b;b = c;}return c;}int main(){int n = 0;scanf("%d",&n);int res = Fibonacci(n);printf("Fibonacci(%d) = %d",n,res);return 0;}四、栈溢出
引例：写一个函数计算阶乘
递归
#include int Factorial(int n){if (n == 0){return 1;}else if (n == 1){return 1;}return n * Factorial(n - 1);}int main(){int num = 0;scanf("%d", &num);int res = Factorial(num);printf("%d",res);return 0;}
在调试Factorial函数的时候，如果你的参数比较大，就会报错：stack overflow(栈溢出)这样的信息。
系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者(死递归)，这样有可能导致一直开辟栈空间，最终导致栈空间耗尽的情况，这样的现象我们称为栈溢出。
那如何解决这个问题呢
1、将递归改写成非递归。
2、使用static对象代替nonstatic局部对象。在递归函数设计中，可以使用static对象代替nonstatic局部变量(即栈对象，因为局部变量是保存在栈区的)，这不仅可以减少每次递归调用和返回时产生和释放nonstatic对象的开销，而且static对象还可以保存递归调用的中间状态，并且可为各个调用层所访问。
迭代
#include int Factorial(int n){int mul = 1;for (int i = 1; i <= n; i++){mul = mul * i;//mul既参加运算又保存结果}return mul;}int main(){int n = 1;scanf("%d", &n);int res = Factorial(n);printf("%d", res);return 0;}五、例题
汉诺塔
例1、汉诺塔问题，输入有几个盘，输出最优步数为几次
汉诺游戏规则如下：
1、有三根相邻的柱子，标号为A,B,C。
2、A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘。
3、现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。
为了方便理解我们将柱子重新命名，以下用柱子的新名称
1、如果只有一个盘
我们用了一步
2、如果有两个盘
我们用了三步
其实我们可以把这个2个盘的情况转换成较少盘的情况，在这里是转化成1个盘的情况
可以把2个盘的情况转化成三次1个盘的情况
第一次1个盘
把甲盘移到辅助柱
第二次1个盘
把乙盘移到目的柱
第三次1个盘
把甲盘移到目的柱
把2个盘的情况转化成三次1个盘的情况，而1个盘的情况是需要一步的，所以2个盘的情况需要三步。
在这里我们发现，可以把较多盘的情况转换成较少盘的情况
下面再来看三个盘的情况
3、如果有三个盘
我们发现3个盘的情况需要七步
3个盘的情况可以转化为两次2个盘的情况+一次1个盘的情况
第一次2个盘的情况
这里的甲乙盘移动到辅助柱的中间步骤暂时省略
一次1个盘的情况
把丙盘移到目的柱
第二次2个盘的情况
这里的甲乙盘移动到目标柱的中间步骤暂时省略
在前面我们知道了2个盘的情况要三步，1个盘的情况需要一步
所以3个盘的情况就需要 2 * (2个盘的情况的步数) + 1个盘的情况的步数 = 2 * 3 + 1 = 7
所以3个盘的情况需要七步
这里，我们就大概发现了一些规律：
n个盘的情况就可以转化为两个(n – 1)个盘的情况 + 一个1个盘的情况
3个盘的情况
转换为(2个盘的情况+ 2个盘的情况) + 1个盘的情况
转化为(1个盘的情况 + 1个盘的情况 + 1个盘的情况 )+ (1个盘的情况 + 1个盘的情况 + 1个盘的情况) + 1个盘的情况
到最后都转化为了1个盘的情况，而1一个盘的情况只需要一步，所以就可以算出步数。
代码实现：
#include int Hanoi(int n){if (n == 1){return 1;}return 2 * Hanoi(n - 1) + 1;}int main(){int n = 0;scanf("%d",&n);int res = Hanoi(n);printf("%d",res);return 0;}小知识
汉诺塔最优步数的公式是pow(2,n) – 1，也就是2^n – 1
汉诺塔原题是出自印度传说，原题是有64个圆盘。
64个圆盘最优步数为2^64 – 1 =18446744073709551615，这是个非常大的数
大约1.8E19，也就是1.8 * 10^19
我们知道unsigned long long的最大值为18446744073709551615
所以以下代码
#include unsigned long long Hanoi(int n){if (n == 1){return 1;}return 2 * Hanoi(n - 1) + 1;}int main(){int n = 0;scanf("%d",&n);unsigned long long res = Hanoi(n);printf("%llu",res);return 0;}运行结果是
也可以
#include double Hanoi(int n){if (n == 1){return 1;}return 2 * Hanoi(n - 1) + 1;}int main(){int n = 0;scanf("%d",&n);double res = Hanoi(n);printf("%e",res);return 0;}运行结果是
在这里我们稍微计算一下
假设一个人玩这个64阶的汉诺塔，假设他一秒只能移动好一个盘，而且每一步都是最优解，则它需要的时间是
年
是不是很令人震惊？
例2、汉诺塔问题，输入有几个盘，输出最优步数的具体操作流程
例如有三个盘就输出
初始柱->目的柱，
初始柱->辅助柱，
目的柱->辅助柱，
初始柱->目的柱，
辅助柱->初始柱，
辅助柱->目的柱，
初始柱->目的柱
这样就完成了游戏
这里的某个柱->另个柱是指把某个柱上第一个盘移动到另个柱的最上面
代码实现：
#include void MovePrint(char position1[], char position2[]){ //控制打印位置1到位置2//这里的位置1和位置2都是不确定的//取决于传来的参数//只有打印的作用，使每一步具象化printf("%s->%s\n", position1, position2);} void Hanoi(int n, char position1[], char position2[], char position3[]){//我们发现Hanoi函数在递归的归来过程//中，只能实现position1->position3的//操作，原因是下面的if(n == 1)的代码//块中的MovePrint函数中的参数只有两个//所以下面再次调用Hanoi函数时，参数的//位置改变了，这样使传给MovePrint函数的//参数也改变了//函数有三个char[]参数的原因是，这三个参数//表示三个柱子，这三个柱子都被需要if (n == 1)//如果n是1，就直接初始柱->目的柱{MovePrint(position1, position3);}else//如果n不是1，按照我们之前的理论，{//直接把n个盘的情况转化成 //两次(n - 1)盘的情况 +1个盘的情况//依据我们之前画的图，这几个情况的顺序是//(n - 1)个盘的情况//1个盘的情况//(n - 1)个盘的情况//由此得下列代码Hanoi(n - 1, position1, position3, position2);//这一步可以理解为通过目的柱//把初始柱上的(n - 1)个盘放到辅助柱//中间的过程暂时忽略//其实中间的过程又转化为了//两次(n - 2)个盘的//情况 + 一次1个盘的情况//然后就这样一直转化，直//到最后全部转化为1个盘的//情况，递归就可以回归了MovePrint(position1, position3);//这一步可以理解为//上一步把初始柱上的(n - 1)个盘放到辅助柱后//初始柱上只有一个盘，//这一步就是把初始柱上剩余的一个盘移动到//目标柱Hanoi(n - 1, position2, position1, position3);//这一步可以理解为通过初始柱//把辅助柱上的(n - 1)个盘放到目标柱//中间的过程暂时忽略//其实中间的过程又转化为了//两次(n - 2)个盘的//情况 + 一次1个盘的情况//然后就这样一直转化，直//到最后全部转化为1个盘的//情况，递归就可以回归了}}int main(){char initial[] = "初始柱";char auxiliary[] = "辅助柱";char goal[] = "目的柱";int n = 0;scanf("%d",&n);Hanoi(n,initial,auxiliary,goal);return 0;}无注释版：
#include void MovePrint(char position1[], char position2[]){printf("%s->%s\n", position1, position2);} void Hanoi(int n, char position1[], char position2[], char position3[]){if (n == 1){MovePrint(position1, position3);}else{Hanoi(n - 1, position1, position3, position2);MovePrint(position1, position3);Hanoi(n - 1, position2, position1, position3);}}int main(){char initial[] = "初始柱";char auxiliary[] = "辅助柱";char goal[] = "目的柱";int n = 0;scanf("%d",&n);Hanoi(n,initial,auxiliary,goal);return 0;}运行结果：
青蛙跳台阶
题目：一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
| 台阶数 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 需要步数 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
我们发现这与斐波那契数列非常像
所以得到下列代码
递归
#include int frogJump(int n){if (n == 0){return 1;}if (n == 1){return 1;}return frogJump(n - 1) + frogJump(n - 2);}int main(){int n = 0;scanf("%d",&n);int step = frogJump(n);printf("%d",step);return 0;}但是这段代码很低效，可以改用迭代
迭代
#include int frogJump(int n){int c = 1, a = 1, b = 1;for (int i = 1; i <= n - 1; i++){c = a + b;a = b;b = c;}return c;}int main(){int n = 0;scanf("%d",&n);int step = frogJump(n);printf("%d",step);return 0;}