正确的递归算法（算法基础递归）

递归是指在函数的定义中使用函数自身的方法，直观上来看，就是某个函数自己调用自己。

递归的两层含义：

1. 递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题。并且这些子问题可以用完全相同的解题思路来解决；
2. 递归问题的演化过程是一个对原问题从大到小进行拆解的过程，并且会有一个明确的终点（临界点）。一旦原问题到达了这个临界点，就不用再往更小的问题上拆解了。最后，从这个临界点开始，把小问题的答案按照原路返回，原问题便得以解决。

递归的基本思想就是把规模大的问题转化为规模小的相同的子问题来解决。在函数实现时，因为大问题和小问题是一样的问题，因此大问题的解决方法和小问题的解决方法也是同一个方法。这就产生了函数调用它自身的情况，而这个函数必须有明确的结束条件，否则就会导致无限递归的情况。

递归的实现包含了两个部分，一个是递归主体，另一个是终止条件。

递归的数学模型其实就是数学归纳法。

当采用递归算法解决问题时，需要围绕这 2 个步骤：

1. 面对一个大规模问题时，如何把它分解为几个小规模的同样的问题；
2. 把问题通过多轮分解后，最终的结果，也就是终止条件如何定义。

当一个问题同时满足以下 2 个条件时，就可以使用递归的方法求解：

1. 可以拆解为除了数据规模以外，求解思路完全相同的子问题；
2. 存在终止条件。

写出递归代码的关键在于，写出递推公式和找出终止条件。首先找到将大问题分解成小问题的规律，并基于此写出递推公式；然后找出终止条件，就是当找到最简单的问题时，如何写出答案；最终将递推公式和终止条件翻译成实际代码。

对树中的任意结点来说，先中序遍历它的左子树，然后打印这个结点，最后中序遍历它的右子树。当某个结点没有左子树和右子树时，则直接打印结点，完成终止。由此可见，树的中序遍历完全满足递归的两个条件：

1. 由根部开始，每一层的结点可以看成是一次中序遍历，这样一层层下去，每一层的求解思路完全相同。所以一个大规模的中序遍历问题拆分为几个小规模的中序遍历。
2. 到达树的叶子即为终止条件。

public static void inOrderTraverse(Node node) { if (node == null) { return; } inOrderTraverse(node.left); System.out.print(node.data " "); inOrderTraverse(node.right); }

汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上，并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

把这个问题抽象为一个数学问题。从左到右有 x、y、z 三根柱子，其中 x 柱子上面有从小叠到大的 n 个圆盘。现要求将 x 柱子上的圆盘移到 z 柱子上去。要求是，每次只能移动一个盘子，且大盘子不能被放在小盘子上面。求移动的步骤。

这是一个大规模的复杂问题，如果要采用递归方法去解决的话，就要先把问题化简。

原问题是，把从小到大的 n 个盘子，从 x 移动到 z。可以将这个大问题拆解为以下 3 个小问题：

1. 把从小到大的 n-1 个盘子，从 x 移动到 y；
2. 接着把最大的一个盘子，从 x 移动到 z；
3. 最后把从小到大的 n-1 个盘子，从 y 移动到 z。

三个小问题的第 1 个小问题和第 3 个小问题其实本身就是汉诺塔问题，只是移动目标不一样。这三个小问题会按顺序解决，假设第 1 个小问题被解决的情况下，第 2 个小问题就很简单了，直接移动就可以了。

所以很容易看到汉诺塔问题满足了递归的两个条件：

1. 大问题所化简出来的第 1 个小问题和第 2 个小问题的求解思路和大问题本身完全相同，从而小问题也可以继续化简下去。
2. 随着递归体不断缩小范围，汉诺塔问题由原来“移动从小到大的 n 个盘子”的大问题，分解为“移动从小到大的 n-1 个盘子”的小问题，继续分解下去，直到分解为“移动从小到大的 1 个盘子”。移动从小到大的 1 个盘子，就是移动最小的那个盘子。根据规则可以发现，最小的盘子是可以自由移动的，就不需要继续分解出小问题来帮助它移动了，因此这个就是终止条件。

具体代码如下所示，在代码中，hanio(n, x, y, z)，代表了把 n 个盘子由 x 移动到 z。递归体包含 3 个步骤：

0. 把从小到大的 n-1 个盘子从 x 移动到 y，那么代码就是 hanio(n-1, x, z, y)；
1. 再把最大的一个盘子从 x 移动到 z，那么直接完成一次移动的动作就可以了；
2. 再把从小到大的 n-1 个盘子从 y 移动到 z，那么代码就是 hanio(n-1, y, x, z)。对于终止条件则需要判断 n 的大小。如果 n 等于 1，那么同样直接移动就可以了。

public static void main(String[] args) { String x = "x"; String y = "y"; String z = "z"; hanio(3, x, y, z); } /** * 定义汉诺塔的递归函数为 hanio() * 3 根柱子的标记 x、y、z * 待移动的盘子数量 n */ public void hanio(int n, String x, String y, String z) { if (n < 1) { System.out.println("汉诺塔的层数不能小于1"); return; } if (n == 1) { System.out.println("移动: " x " -> " z); return; } hanio(n - 1, x, z, y); System.out.println("移动: " x " -> " z); hanio(n - 1, y, x, z); }

在主函数中，执行了 hanio(3, "x", "y", "z")。发现 3 比 1 要大，则进入递归体。分别先后执行了 hanio(2, "x", "z", "y")、"移动: x->z"、hanio(2, "y", "x", "z")。

其中的 hanio(2, "x", "z", "y")，又先后执行了 hanio(1, "x", "y", "z")、"移动: x->y"、hanio(1, "z", "x", "y")。在这里，hanio(1, "x", "y", "z") 的执行结果是 "移动: x->z"，hanio(1, "z", "x", "y") 的执行结果是 "移动: z->y"。

另一边，hanio(2, "y", "x", "z") 则要先后执行 hanio(1, "y", "z", "x")、"移动: y->z"、hanio(1, "x", "y", "z")。在这里，hanio(1, "y", "z", "x") 的执行结果是 "移动: y->x"，hanio(1, "x", "y", "z") 的执行结果是 "移动: x->z"。

代码执行的结果就是：

移动: x->z 移动: x->y 移动: z->y 移动: x->z 移动: y->x 移动: y->z 移动: x->z

递归的核心思想是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况。递归的应用非常广泛，很多数据结构和算法的编码实现都要用到递归，例如分治策略、快速排序等等。