目录
递归是什么
先看一下什么叫递归。
递归，就是在运行的过程中不断调用自己，直到满足某个条件。
构成递归需具备的条件：
- 子问题须与原始问题干同样的事，且更为简洁明了
- 不能无限制地调用本身，须有个出口结束递归。
递归模板
我们知道递归必须具备两个条件，一个是调用自己，一个是有终止条件。这两个条件必须同时具备，且一个都不能少。并且终止条件必须是在递归最开始的地方，也就是下面这样：
int fun()
{
if(终止条件)
return ;
else
return fun();
} 不能把终止条件写在递归结束的位置，下面这种写法是错误的，因为它这样就会先递归再判断，永远不会出递归了，是死递归，就会出现堆栈溢出异常。
int fun()
{
return fun();
if(终止条件)
return ;
}但实际上递归可能调用自己不止一次，并且很多递归在调用之前或调用之后都会有一些逻辑上的处理，比如下面这样。
int fun()
{
if (终止条件)
return ;
逻辑运算
fun();
逻辑运算
fun();
}
实例分析
我对递归的理解是先往下一层层传递，当碰到终止条件的时候会返回值，最终会返回到调用处。下面我们就以3个最常见的示例来分析下
1，阶乘
我们先来看一个最简单的递归调用-阶乘，代码如下
int fun(int n)
{
if(n==1)
return 1;
else
return n*fun(n-1);
}这个递归在熟悉不过了，第2-3行是终止条件，第4行是调用自己。我们可以用n等于5的时候来画个图看一下递归究竟是怎么调用的吧
如果看不清，图片可点击放大。
这种递归还是很简单的，我们求f(5)的时候，只需要求出f(4)即可，如果求f(4)我们要求出f(3)……，一层一层的调用，当n=1的时候，我们直接返回1，然后再一层一层的返回，直到返回f(5)为止。
递归的目的是把一个大的问题细分为更小的子问题，我们只需要知道递归函数的功能即可，不要把递归一层一层的拆开来想，如果同时调用多次的话这样你很可能会陷入循环而出不来。比如上面的题中要求f(5)，我们只需要计算f(4)即可，即f(5)=5*f(4)；至于f(4)是怎么计算的，我们就不要管了。因为我们知道f(n)中的n可以代表任何正整数，我们只需要传入4就可以计算f(4)。
2，斐波那契数列
我们再来看另一道经典的递归题，就是斐波那契数列，数列的前几项如下所示
1，1，2，3，5，8，13……
递归的两个条件，一个是终止条件，还一个是调用自己。我们知道斐波那契数列当前的值是前两个值的和，我们参照递归的模板来写下，首先终止条件是当n等于1或者2的时候返回1，也就是数列的前两个值是1，代码如下
int fun(int n)
{
if(n==1||n==2)
return 1;
else
return fun(n-1)+fun(n-2);
}3，汉诺塔
通过前面两个示例的分析，我们对递归有一个大概的了解，下面我们再来看另一个示例-汉诺塔。
汉诺塔的原理这里再简单提一下，就是有3根柱子A，B，C。A柱子上由上至下依次由小至大排列的圆盘。把A柱子上的圆盘借B柱子全部移动到C柱子上，并且移动的过程始终是小的圆盘在上，大的在下。我们还是用递归的方式来解这道题，先来定义一个函数
void fun(int n,char a,char c,int b)//把n个圆盘从A借助C移动到B
我们先来回顾一下递归的条件，一个是终止条件，一个是调用自己。我们先来看下递归的终止条件就是当n等于1的时候，也就是A柱子上只有一个圆盘的时候，我们直接把A柱子上的圆盘移动到C柱子上即可。
再来看一下,如果n不等于1，我们要分3步，
- 先把n-1个圆盘从A借助C成功的移动到B
- 然后再把第n个圆盘从A移动到C
- 最后再把n-1个圆盘从B借助A成功的移动到C。
那代码该怎么写呢？还原上面的描述代码应为：
fun(n-1,a,b,c);
cout<<a<<"->"<<n<<"->"<<b<<endl;
fun(n-1,c,a,b);所以最终代码如下：
void fun(int n,char a,char c,char b)
{
if(n==1)
cout<<a<<"->"<<n<<"->"<<b<<endl;
else
{
fun(n-1,a,b,c);
cout<<a<<"->"<<n<<"->"<<b<<endl;
fun(n-1,c,a,b);
}
}所以我们写递归的时候完全可以套用上面的模板，先写出终止条件，然后在写递归的逻辑调用。还有一点非常重要，就是一定要明白递归函数中每个参数的含义，这样在逻辑处理和函数调用的时候才能得心应手，函数的调用我们一定不要去一步步拆开去想，这样很有可能你会怀疑人生的。
通过上面的分析，是不是感觉递归很简单，但其实递归看起来简单，真正实现代码时，会使程序员无从下手的，有一句话阐明的十分到位：人了解迭代，神了解递归。说的就是递归的难以理解。
你的点赞、关注是我创作的最大动力(^_^)
如果有不懂的的问题，可以留在评论区里，我会尽快回复的(✪ω✪)