递归
简介
递归是我们在学C语言的时候，就已经接触到了的一个概念，相信大家的递归都是从这里开始的：
但是，在老师念ppt的时候，伴随着一些前轱辘不转后轱辘转的语言，我们往往都没有太去了解递归的工作原理和性质。我们听的最多的便是：
- 递归用来处理子问题
- 递归的本质是调用自身函数
- 递归一定要有结束条件
光有这些死概念是理解不了问题的，我们还是分开来分别讲
子问题这个概念，我们在动态规划中接触过。
比如斐波那契数列，我们想知道第i项，就必须知道第i-1项和第i-2项。而想知道第i-1项，就要知道第i-2项和第i-3项。
每一项的求法都是相同的，而求出前一项，是求出后面的项的先制条件，所以求解前置条件的过程，就叫做求解子问题。
因为求解每一项的方法是相同的，假如我们通过一个函数来求解这个问题：
//求解第i项 int fib(int i)那么求解第i-1项和第i-2项，也会去调用这个函数：
//求解第i-1项 fib(i-1); //求解第i-2项 fib(i-2);而看题目的条件，第i项为前两项的和，我们就直接表达出这个关系：
//第i项为前两项的和： fib(i)=fib(i-1)+fib(i-2) //所以，fib(i)的返回值就为fib(i-1)+fib(i-2) int fib(int i) { return fib(i-1)+fib(i-2); }这就是在函数内部调用了函数自己。
但是，上面这个方法也会有很大的问题：函数会无休止重复下去。
想求fib(3)，会调用fib(2)和fib(1)；想求fib(1)，会调用fib(0)和fib(-1)；想求fib(-1)，会调用fib(-2)和fib(-3)……
就像你要找同桌抄作业，同桌说我要去抄前桌的；同桌去找前桌，前桌说去抄他的前桌的……一直找来找去，都想抄作业，但是如果没有一个人去写作业，那到最后都抄不成。
所以，递归一定要有一个条件，让递归终止不再继续，也就是递归的结束条件。int fib(int i) { //递归的终止 if(i==0) return 1; if(i==1) return 1; return fib(i-1)+fib(i-2); }
我们换一个视角来看递归：递归就像一个流水线，每一个车间只做3件事，
而对最底层的递归，只办一件事：直接把结果给上一层
这便是递归。
解决问题公式
所以，我们在面对一个递归问题的时候，也只需要考虑三件事：
- 什么是子问题？
- 解决这个问题需要哪些条件，怎么处理？
- 递归的结束条件是什么？
也就是我们解决算法问题常考虑的三步：
对于第一个问题，这确确实实是考语文了，你套公式总得把题目先看懂吧。
对于第二个问题，我们会有一个思想：无条件相信下一层递归给你的结果值。我们只要做好自己这块就可以了，至于这一层递归以外会如何处理如何发展，我们丝毫不关心。
当然，这么说有点难理解，我们还是待会从题目来详细讲这个问题。对于第三个问题，如果前两步做好了，那么结束条件只会有两种情况：
- 题目给了
- 在研究函数体的时候，为了防止一些像越界等异常情况，不得不终止。
一样因题而异，但是一样在公式以内。
OK，公式讲完了，直接来看题目吧：
汉诺塔
面试题 08.06. 汉诺塔问题 - 力扣（LeetCode）
一道很经典的递归题，甚至在小学其实就可能接触过。但是因为题目没有图，我们还是稍微翻译一下：
题目翻译
现在有三个蛤蟆洞ABC，蛤蟆洞A有几只蛤蟆仙人，小蛤蟆压在大蛤蟆身上，现在要把蛤蟆全部移到蛤蟆洞C里，并且：
- 每次只能把每个蛤蟆洞里，最上面那一只蛤蟆移到另外一个蛤蟆洞
- 大蛤蟆不能压小蛤蟆身上，不然会被压死
问在这种限制条件下，怎么借助蛤蟆洞B，把所有蛤蟆全移到蛤蟆洞C里去
解题步骤
第一次看到这种炸肛的题目，手足无措很正常，我们还是通过公式来解决这个问题。
1.什么是子问题
我们思考这个问题，最难解决的一步是什么？怎么将大蛤蟆放在小蛤蟆下面。因为小蛤蟆会先挪走，然后再挪走大蛤蟆，正常情况一定是小蛤蟆被放在大蛤蟆下面：
此时，解决方案只有一种：先把小蛤蟆挪到另一个蛤蟆洞，
此刻，问题便得到了解决。
至少，我们找到了解决最难的一步的关键方案：将小蛤蟆们全部移到蛤蟆洞B，然后将大蛤蟆移到蛤蟆洞C，最后将小蛤蟆们移到蛤蟆洞C中大蛤蟆的身上。
有人可能要说了，不是一次只能移动一个蛤蟆吗？你这么做不是违反了第一条规则吗？
别急，我们再来看第一步：将所有小蛤蟆们全部移到蛤蟆洞B。
那将小蛤蟆们全部移到蛤蟆洞B应该干什么？将更小的小蛤蟆们全部移到蛤蟆洞C，然后将中蛤蟆移到蛤蟆洞B，最后将更小的小蛤蟆们移到蛤蟆洞B。
食德，子问题就被我们这样给找到了。我们来总结一下子问题：
假设蛤蟆洞A有n个蛤蟆，先将n-1只小蛤蟆借助蛤蟆洞C移到蛤蟆洞B，再将第n只大蛤蟆移动到蛤蟆洞C，最后将蛤蟆洞B中的蛤蟆借助蛤蟆洞A移动到蛤蟆洞C。
2.函数条件和函数体
函数条件是在我们分析子问题的时候，顺带分析出来的。有人可能要问了，我们刚刚分析了个集贸啊，但是我们再往回看，我们一直在利用哪些条件？
- 三个蛤蟆洞中的蛤蟆
- 所需要移动蛤蟆的数量
所以，我们的函数条件就是这些：三个蛤蟆洞，和这一步需要移动蛤蟆的数量。
而函数体，也即是在我们分析子问题的时候，一直在分析的解决方案。我们每一步在干什么？
先将n-1只小蛤蟆借助蛤蟆洞C移到蛤蟆洞B，再将第n只大蛤蟆移动到蛤蟆洞C，最后将蛤蟆洞B中的蛤蟆借助蛤蟆洞A移动到蛤蟆洞C。
所以，直接把他转换成编程语言，就可以了。
//移动蛤蟆的函数
void move(vector<int>& initial,vector<int>& destination)
{
int move_num=initial[initial.size()-1];
initial.pop_back();
destination.push_back(move_num);
}
//函数条件，需要移动的蛤蟆数量n，三个蛤蟆洞ABC
//A表示初始的洞，就是蛤蟆在挪动之前，最开始的洞
//B表示借助的空的洞
//C表示最终需要被挪到的洞
void _hanota(int n,vector<int>& A, vector<int>& B, vector<int>& C)
{
//借助蛤蟆洞C，将n-1只小蛤蟆挪动到蛤蟆洞B
_hanota(n-1,A,C,B);
//将最底下的大蛤蟆移动到蛤蟆洞C
move(A,C);
//将n-1只小蛤蟆借助蛤蟆洞A，从蛤蟆洞B移动到蛤蟆洞C
_hanota(n-1,B,A,C);
}有人可能要问了，就这么简简单单三行代码，真的可以完成题目要求吗？
这就是我们最开始所说的：无条件相信下一层递归给你的结果值。我们相信递归一定可以完成我们交给他的任务，我们只需要做好自己的那一层任务，也就是把A中仅存的大蛤蟆移到C中，剩下的我们不去关心，因为那是我们这一层以外的事情。
而其实往往，我们处理递归问题感觉棘手，其实就是太过关注每一层递归以外是否可以完成任务，而考虑来考虑去，将一个很简单的问题想的无比复杂，最终只会导致一个结果：
3.结束条件
我们在公式里就已经说了，递归的结束条件只有两种情况：
题目没给，那我们就思考第二种情况，什么是异常情况？
其实也很简单，当没有蛤蟆的时候，那我们还挪个集贸啊。
所以，_henota(0,A,B,C)是无法处理的，如果遇到n==0，我们直接结束就好了。
void _hanota(int n,vector<int>& A, vector<int>& B, vector<int>& C)
{
//n==0，处理不了，直接结束递归
if(n==0)
return;
_hanota(n-1,A,C,B);
move(A,C);
_hanota(n-1,B,A,C);
}当然，这是可以被优化成n==1或者n==2的时候结束的，具体方法就是展开，小学生都会。
解题代码
class Solution {
public:
void move(vector<int>& initial,vector<int>& destination)
{
int move_num=initial[initial.size()-1];
initial.pop_back();
destination.push_back(move_num);
}
void _hanota(int n,vector<int>& A, vector<int>& B, vector<int>& C)
{
if(n==1)
{
move(A,C);
return;
}
_hanota(n-1,A,C,B);
move(A,C);
_hanota(n-1,B,A,C);
}
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
int num=A.size();
_hanota(num,A,B,C);
}
};或者骗OJ的解题方法：
void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
{
C=A;
}
