要理解递归，得先理解递归--用Java语言由浅入深讲解汉诺塔游戏

一、递归是什么?

定义:程序调用自身的编程技巧称为递归。它分为调用阶段和回退阶段，递归的回退顺序是它调用顺序的逆序。

递归使用的是选择结构：if/switch。而for，while，do while使用的是循环结构。

定义不明白不要紧，先思考以下表达式，要怎么写程序来计算呢？

1+2+3....+100=?

很多人第一反应使用for循环来解决：

或者二逼青年使用最简洁而且高效的公式(推荐使用,开销最小,且一步到位):

而递归代码如下:

通过初体验对比,不难发现以下递归有以下几个要点:

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。

现在，我们可以给出代码：

四、总结和展望

递归对于解决某些问题非常方便（比如递归读取文件路径），也易于理解。虽然用迭代不是不可以实现，只是同样为了解决某些特性问题，写出迭代的代码花费的时间和难度却比递归高。

前文提到，递归和数学中的归纳思想本质上是相同的，都是"将复杂的问题简化"。掌握递归思想的核心就在于"把握结构",因为把握结构是分解整个问题的突破口。