要理解递归，得先理解递归--用Java语言由浅入深讲解汉诺塔游戏
一、递归是什么?
定义:程序调用自身的编程技巧称为递归。它分为调用阶段和回退阶段，递归的回退顺序是它调用顺序的逆序。
递归使用的是选择结构：if/switch。而for，while，do while使用的是循环结构。
定义不明白不要紧，先思考以下表达式，要怎么写程序来计算呢？
1+2+3....+100=?
很多人第一反应使用for循环来解决：
int sum =0;
for (int i = 1; i <= 100; i++) {
sum+=i;
}
System.out.println(sum);//5050或者二逼青年使用最简洁而且高效的公式(推荐使用,开销最小,且一步到位):
int start =1;
int end = 100;
int sum =(start+end)*end/2;//首项加末项乘以项数除以二
System.out.println(sum);//5050而递归代码如下:
static int recursion(int n){
if(n==1){//递归出口
return 1;
}else{
return n+recursion(n-1);
}
}通过初体验对比,不难发现以下递归有以下几个要点:
1.优点:使程序结构更清晰,更简洁,更容易让人理解,
2.缺点:使用递归调用时，如果过多的调用容易造成java.lang.StackOverflowError即栈溢出和程序执行过慢。这是一个潜在Bug和影响程序执行效率问题，需要谨慎使用。对于互联网这种以速度和效率来维护用户量，不得以用递归时，可以把处理的数据放入缓存，或者直接使用迭代等方式来解决。
3.规律：递归要有出口，不然成了死循环。解出递归的要点在于求出n-1，求出了n-1才能求解出n,这是为什么呢?
二、递归的执行过程
前文对于递归的定义中说，递归分为调用阶段和回退阶段，递归的回退顺序是它调用顺序的逆序。为了理解执行过程，这里配合实例讲解。请思考如何写出它的递归代码：
n!=n*(n-1)*(n-2)...*3*2*1
这里给出数学表达式：
从表达式中可以明显的可以看出：1.递归有出口。2.递归是选择结构。递归代码也不难：
它的调用顺序是怎么样的呢？
当你传入5时，方法内会去调用方法factorial（4），然后又调用方法factorial（3）直到factorial（0）=1时开始返回，下面为更详细的图解:
调用阶段
回退阶段
图中红色箭头为调用阶段，绿色箭头为回退阶段。这就是递归的要点在于求出n-1，求出了n-1才能求解出n，它思想其实和数学中的归纳本质上是相同的。
三、汉诺塔游戏讲解
游戏规则：有三根柱子，最左边的一根柱子从下往上按照大小顺序摞着64片圆盘。需要你借助中间的柱子把左边的所有圆盘移动到最右边的柱子上。并且规定，下面圆盘始终要比上面的大，在三根柱子之间一次只能移动一个圆盘。求出最少移动的次数。
如果要把X柱上得3个圆盘移动到Z柱，步骤如下：
①把X柱最上面的小圆盘移动到Z柱。②再把X柱中间大的圆盘移动到Y柱。③把Z柱上最小的圆盘移动到Y柱上。
这三次操作如图所示：
再加上步骤④⑤⑥⑦，所以3个圆盘至少需要移动7次。如果移动6个圆盘时：
所以可以推出,当n个从x柱，经由y柱中转，移动到z柱(解出n层汉诺塔时)，有:
当n=0时，
不用做任何操作
当n>0时，
首先,将n-1个盘子从x借助z移动到y
然后,将1个盘子从x移动到z
最后,将在中间y上的n-1个盘子借助x移动到z
为了解出n层汉诺塔，需要先使用n-1层汉诺塔的解法。
从推到过程中我们可以发现：解出递归的要点在于求出n-1，求出了n-1才能求解出n。此外，从数学角度也可以归纳出 0,1,3,7,15,63...表达式为:f(n)=2^n - 1。
现在，我们可以给出代码：
static int t=0;//最少移动次数
public static void main(String[] args) {
hanio(3,"x","y","z");
System.out.println(t);
}
static void hanio(int n ,String src,String mid,String dest){
if(n==1){
System.out.println(src+"-->"+dest);//移动过程
t++;
}else{
hanio(n-1,src,dest,mid);//将n-1个盘子从x借助z移动到y
hanio(1,src,"",dest);//因为中间柱子没用到,所以可以填""或者填mid,然后将最大的盘子从x直接移动到z
hanio(n-1,mid,src,dest);//将在中间y柱上的n-1个盘子借助x移动到z
}
}四、总结和展望
递归对于解决某些问题非常方便（比如递归读取文件路径），也易于理解。虽然用迭代不是不可以实现，只是同样为了解决某些特性问题，写出迭代的代码花费的时间和难度却比递归高。
前文提到，递归和数学中的归纳思想本质上是相同的，都是"将复杂的问题简化"。掌握递归思想的核心就在于"把握结构",因为把握结构是分解整个问题的突破口。
