一、引例
描述
给定一个数字 n(范围在0~10)，求 n 的阶乘
样例
输入：0 输出：1
输入：5输出：120
算法设计
首先最容易想到的就是利用循环做，即进行 n-1 次循环，然后每次循环中进行累乘，最后输出结果，再加一个特殊值判断(0! = 1)，那么很容易编写代码如下：
#include <iostream>int main(){int n = 0,num = 1;std::cin >> n;while(n > 0)num *= n--;std::cout << num;}
接下来看看递归的版本
二、原理
1.定义(引自维基百科)
递归（英语：Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。递归一词还较常用于描述以自相似方法重复事物的过程。例如，当两面镜子相互之间近似平行时，镜中嵌套的图像是以无限递归的形式出现的。也可以理解为自我复制的过程。
2.观察题目特征
在求阶乘的过程中，while循环中的语句不断的执行，这就跟递归定义中自我复制的概念很像，即不断地进行乘法运算，将其定义为规律1，每次乘的数字不一样，如果可以找到数字变化的规律，将其称为规律2，那么我们就可以将规律1和规律2组合起来，描述求阶乘这一问题。
显然，此题中规律1和规律2都是确定的，分别是进行乘法运算和变量值减一。那么什么时候这一过程会终止？显然是由规律2决定的，当变量减到 0 的时候就会停止。那么现在就有了一个完整的表述：有一个函数描绘了这一过程，函数自己调用自己实现累乘，每次需要函数传入变量的值，当变量的值为 0 时，函数停止调用自己。
3.代码表述
#include <iostream>int Factorial(int n) {if (n == 0)return 1;return n * Factorial(n - 1);}int main(){int n = 0;std::cin >> n;std::cout << Factorial(n);}
三、如何写递归
1.找规律(整体与局部的思想)
找到问题呈现的一般规律对于写出递归是非常重要的，这里再利用求阶乘的例子，不妨这样想，当 n = 2 时，可以看成两个数相乘，当 n = 10 时，能否看成两个数相乘，稍加思考会发现是可以的，n = 10 时 n! 可以看成 10 * 9!，而 9! = 9 * 8!。接下来用数学归纳法证明其正确性(注：数学归纳在递归中使用广泛，是寻找递归规律和证明递归正确性的重要手段)：
当 n = 1时，显然有 1! = 1*1!假设当 n = k 时，有 n! = k*(k-1)! = k!则当 n = k+1 时，n! = (k+1)*(k)*(k-1)*...*1而k*(k-1)*...*1 = k!故有当n = k+1时，n! = (k+1)! = (k+1)*k!
接下来考虑递归函数的作用，即递归函数用于模拟阶乘这一过程，则可以写出递推方程：Factorial(n) = n * Factorial(n-1)，这就是将n看成单个数，(n-1)!看成另一个数的思想方法，至于(n-1)!的过程，我们不需要关注，这是计算机该完成的任务。因此问题就简化成了计算 n 和 (n-1)! 这两个数的乘积这么简单，即 Factorial(n) = n * Factorial(n-1)。
2.找递归基
接下来需要搞清楚这个递归需要在什么时候结束，按道理来说，当 n = 1 的时候，递归就可以结束了，因为 1 乘任何数还是任何数，但是在阶乘中，规定了 0! = 1，因此在编写程序时，省略额外的判断语句，即当 n = 0 时，再停止递归。所谓递归基，即控制递归结束的条件，无休止的递归是没有意义的。
3.递归的一般写法
递归可以理解为函数自己进行的一系列操作，可以是运算，可以是赋值等等，在编写递归程序时，不需要在脑海中模拟递归栈的样子，因为对于稍大的数据来说，模拟递归栈确实是比较麻烦的事情，因此只适合数据量较小，辅助找规律的时候再进行模拟。只需要你在写之前确定递归程序的作用，即明确写出递归过程的表达式，剩下的统统交给计算机就行。可能现在不太好理解，接下来通过几个例子理解一下。
四、小试牛刀
1.汉诺塔问题(递归模拟过程)
题目描述
从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
样例
输入：1输出：A->C 1
输入：3输出：A->C A->B C->B A->C B->A B->C A->C 7
分析
对于1个圆盘，只需要将 A->C对于2个圆盘，需要利用 B 进行中转，即A->B A->C B->C对于n个圆盘，利用整体与部分的思想，看成3个圆盘，n-1(看成一个)个圆盘先移动到B，A->B，然后最底下的移动A->C，最后把n-1个移动到C，B->C接下来计算次数，依然是利用整体与部分的思想，这时候需要稍微模拟一下当 n = 1 时，显然只需要移动 1 次n = 2 时，相当于先把上面的移动好，再移动最下面的，最上面的盘数量是 1，移动好需要 1 次，然后移动最下面的盘，需要 1 次，最后把上面的盘移动到 C，需要 1 次，故需要 3 次n = 3 时，相当于先把上面两个移动好，需要 3 次(n = 2时)，然后移动最下面的盘，需要 1 次，最后再把上面两个移动到 C，需要 3 次可见在完整的移动过程中，需要先将其上面的 n-1 个移动好(相当于先解决 n-1 层盘的移动问题)，再移动最底下的，这只需要 1 步，最后把移动好的 n-1 个再移动到 C 上(还是解决 n-1 层盘的移动问题)，相当于进行了两次上一步操作的过程。
证明
不妨假设需要移动 an = an-1 + 1 + an-1利用数学归纳法证明n = 1 时，a1 = 1当 n = 2 时，显然有 a2 = a1 + 1 + a1 = 1 + 1 + 1 = 3假设当 n = k 时有 ak = ak-1 + 1 + ak-1则当 n = k+1 时，前 k 层盘移动好需要 ak 步，再移动最底下的盘，需要 1 步，再把此时在 B 上的前 k 层盘移动到 C 上(又转化成了移动 k 层盘需要的步数)，因此有 ak+1 = ak + 1 +ak因此有 an = 2*an-1 + 1两边同时 + 1an + 1 = 2*(an-1 + 1)有 (an + 1) / (an-1 + 1) = 2(an-1 + 1) / (an-2 + 1) = 2...(a3 + 1) / (a2 + 1) = 2(a2 + 1) / (a1 + 1) = 2全部乘起来，(an + 1) / (a1 + 1) = 2^(n-1)an = 2^n - 1
编写递归程序
有了上面的推导，接下来理解整体局部就比较容易了，相当于将 n-1 个盘移动到 B，第 n 个盘移动到 C，再将 n-1 个盘移动到 C，并明确递归函数的作用就是模拟这一过程，需要传入的参数有：盘数量 n，起点 begin，中转点 mid 和终点 end。1. 写出表达这一过程的递归式，即 先把 n-1 个盘移动到中间 B：Hanoi(n-1,begin,end,mid)，最后一个盘移动到 C：printf(begin->end)，再把 n-1 个盘移动到 C：Hanoi(n-1,mid,begin,end)2. 找到递归基，显然当 n = 1 时，递归停止，只需打印 begin->end。
代码
#include <iostream>#include <math.h>void Hanoi(int n,char begin,char mid,char end) {if (n == 1){std::cout << begin << " -> " << end << std::endl;return;}Hanoi(n - 1, begin, end, mid);std::cout << begin << " -> " << end << std::endl;Hanoi(n - 1, mid, begin, end);return;}int main(){int n = 0;std::cin >> n;Hanoi(n, 'A', 'B', 'C');std::cout << pow(2,n)-1;}
2.爬楼梯问题(递归模拟计算)
题目描述
有个人爬楼梯，每次可以走 1 级台阶或 2 级，输入楼梯的级数，求不同的走法数
样例
输入：3输出：3
输入：5输出：8
输入：8输出：34
分析
n = 1 时，只能走 1 级n = 2 时，可以走 1 级，然后只能选择 n = 1 的走法，也可以先走 2 级n = 3 时，先走 1 级，然后选择 n = 2 的走法，先走 2 级，然后只能选择 n = 1 时的走法运用整体与局部的思想对于 n = k 层台阶，先走第 1 步有两种选择，分别是 1 级和 2 级，走 1 级之后可以重复 k-1 时进行过的所有走法，走 2 级之后可以重复 k-2 时进行过的所有的走法不难推出 f(n) = f(n-1) + f(n-2)
证明
当 n = 1 时 a1 = 1，n = 2时，a2 = 2n = 3时，显然有 a3 = a1 + a2 = 3假设 n = k 时，有 ak = ak-1 + ak-2则 n = k+1 时，ak+1先走 1 级，问题变成了 k 阶台阶走法，有 ak 种，先走 2 级，问题变成了 k-1 级台阶走法，有 ak-1 = ak - ak-2 种，故有 ak+1 = ak + ak - ak-2 = ak + ak-1
编写递归程序
1. 表达这一过程的递归式，很明显就是f(n) = f(n-1) + f(n-2)2. 寻找递归基，因为有 n-1 和 n-2，因此设定边界为n < 0 return 0n = 0 return 1
代码
#include <iostream>int f(int n) {if (n < 0)return 0;if (n == 0)return 1;return f(n - 1) + f(n - 2);}int main(){int n;std::cin >> n;std::cout << f(n);}
结语
不难发现，当一个问题可以被分解为规模更小的子问题时，可以考虑使用递归求解，但是递归在调用过程中，会占用大量的内存，因此就需要更好的算法在其基础上进行优化，这个之后再谈，理解了递归，对程序设计的思想还是有较大帮助的。
如果觉得《如何通俗易懂地理解递归》对你有帮助，请点赞、收藏，并留下你的观点哦！
