1.什么是递归？
知乎大佬们的回答简直是天秀……
https://www.zhihu.com/question/20507130
下面的图片也是转自上述链接。
那么到底什么是递归？
- 递归就是调用函数本身
int fun(n){
……
fun(n);
}
上面的代码就是fun()调用自己的情况。
但是如果这样就导致了死循环，是必然不能这么写的，那我们需要注意省略号部分，需要给一个终止条件。
int fun(n){
if(n == 1){
return 0;
}
fun(--n);
}
-
递归分为递推和回归两部分，不断深入调用之后必须返回给上一级
还是上面的代码，当ｎ不断减１，最终ｎ总会等于１，也就达到了终止的时机，然后开始return,带着return值找调用他的函数。
2.递归与循环的区别
递归：有去有回（有return）
循环：有去无回
某些情况（或者绝对情况？）递归和循环可以达到同样的效果，对于解决一个问题，循环更易于理解，且更省内存。但是递归是一种很简（zhuang）洁(B)的思想，有些时候用递归比用循环来的逻辑清晰，像斐波那契数列，快速排序等算法，就是递归的很优秀的算法。
同时递归在 算法：分治法 也是 main player, 递归和分治法是密不可分的。
3.递归的应用
在谈论应用之前，还是要提一下如何使用递归，不是说简单的自己调一下自己就行了，而是要考虑下面两个问题
- 边界条件：也就是最后的终止条件，没有这个条件，我们是没法解决这个问题的，这个条件也就是分治法中的最小子问题的解决方案，也称为递归出口
- 递归模式：我们用递归是为了将一个大问题分成好多个小问题来解决的，那么每个小问题如何解决就是递归模式，也称为递归体。
啰嗦一句：递归就像比如说你有一个项目，把一部分外包出去，接收到外包的公司又把一部分外包出去，不断外包，直到有一个公司觉得这么点小程序我还外包啥，自己做，写完了代码递交给下发任务的公司,然后下发任务的公司合并自己的代码，又交给上一级公司，不断递交，最后你拿到了项目，加上自己写的代码，合并成完整的项目。那么边界条件就是最后一个全部自己写的ＮＢ的公司，递归模式是把哪些任务交给下一级公司。
递归应用：
Fibonacci sequence 斐波那契数列
Merge Sort 归并排序
Quick Sort 快速排序
Tower of Hanoi 汉诺塔
4.汉诺塔
有三根相邻的柱子，标号为A,B,C，A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，要把所有盘子移动到柱子C上，一次只可以移动一个，可以借助Ｂ，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，打印出移动方案。
现在思考两个东西之间的联系：递归／汉诺塔
要回忆刚才我们说的 边界条件和递归模式
在这里我取知乎大佬的图片来用一下吧。
-
A.边界条件
边界条件一般就会考虑极端情况，对于这个题，就是当盘子只有有个的时候直接移动,那代码如下
if(n == 1){
System.out.println("从"+from+'到'+to);
return;
}
ｎ是盘子数，from赋值Ａ，to复制Ｃ
-
B.递归模式
也可以理解为如何求解子问题吧。
怎么理解这张图片?
也是知乎大佬的原话,汉诺塔永远只有三步，第一步，打开冰箱门，第二步把大象装进冰箱，第三步关上冰箱门。（这个梗不会不知道吧，不知道的可以去百度一下）当然这个是搞笑的，但是实际上汉诺塔就是这样子，第一步，把ｎ－１个碟子从from 移动到 helper(相当于打开冰箱门)，第二步，把最下面的碟子从from移动到to（相当于最大的碟子是大象，放进了冰箱），第三步，把ｎ－１个碟子从helper移动到to（相当于关上冰箱门），你可能会说了，不是说一次只能移动一个盘子么，对的，我把上面ｎ－１个外包出去了呀。那么ｎ－１就是被递归的部分。
n - 1 会把除了最底下的盘子都外包给n-2
n-2会把除了最底下的盘子都外包给n-3
……
也就是说，我们不需要管上面怎么移动的，我们只需要递归调用让子问题自行解决，解决完了把结果返回一下就行了。
那么，就是三步，我们已经确定了递归模式
代码如下
public class Hanoi {
public static void main(String[] args) {
//调用的时间分别传入了盘子的数目，from的杆子代号Ａ
//to的杆子代号Ｃ，helper的杆子代号Ｂ
Hanoi(4,"A","C","B");
}
static void Hanoi(int n,String from,String to,String helper){
//边界条件（对比第一张手绘图）
if(n == 1){
System.out.println("从"+from+'到'+to);
return;
}
//递归部分
//第一步：把n-1个从from挪到helper上，借助to
//这就叫打开冰箱门
Hanoi(n-1,from,helper,to);
//第二步：放入大象（这个大象就是ｎ）
move(from,to);
//第三步：把n-1个helper挪到from上借助to
//关上冰箱门
Hanoi(n-1,helper,to,from);
}
static void move(String from, String to) {
System.out.println("从"+from+'到'+to);
}
}
现在可能看这个代码就会一脸懵逼，当然大佬完全可以按照执行顺序一层一层找下去，看看是怎么运行状况。
小白的话，千万不要试图去理解到底是怎么移动了这么神奇的事情，不要去想移动从哪到哪的事情，怎么打印出这些情况的，就想简单的三步，对于不断缩减的规模总是进行了三步，
把ｎ-1部分（冰箱门）当做一个整体，直接运行
//第一步：把n-1个从from挪到helper上，借助to
//这就叫打开冰箱门
Hanoi(n-1,from,helper,to);
//第二步：放入大象（这个大象就是ｎ）
move(from,to);
//第三步：把n-1个helper挪到from上借助to
//关上冰箱门
Hanoi(n-1,helper,to,from);
部分，执行完就是两个碟子的情况。
递归的话是从第一步开始的，传入n-1又是一个新的子问题，打开冰箱门，放入大象,关上冰箱门，我们只需要管子问题执行结果，并且也不需要研究子问题里面是怎么执行的。
这样一直循环下去，我们顶多要再思考一下ｎ=1的情况（也就是把大象放入一个没有门的冰箱里……）
好了，到此为止，不能再多说了，越说越乱。哈哈，好好捋一捋吧，递归本身就是很绕的一件事情，所以不要烦躁以为自己是不是很笨都理解不了，其实大家都这样。再厉害的大神都要绕的。
//４个盘子的运行结果如下
从A到B
从A到C
从B到C
从A到B
从C到A
从C到B
从A到B
从A到C
从B到C
从B到A
从C到A
从B到C
从A到B
从A到C
从B到C
好了就这样吧。
喜欢研究递归的可以刷刷递归的题，绕不清汉诺塔的或者要验证汉诺塔的可以试试这个小游戏:http://www.3454.com/91990p
