递归算法（下）

上文讲了递归算法比较简单的用法，相信对递归算法有一定的概念了。这篇文章再来试试两个相对复杂一点点的案例，最后在总结一下使用递归的一般方法已经需要注意的地方。

汉诺塔

汉诺塔是一种移动圆盘的游戏，同时也是一个简单易懂的递归算法应用示例。（案例及图片来源于《我的第一本算法书》）

游戏规则

移动一个盘子：

直接移动 盘子1 从A-->C

移动两个盘子：

需要通过B临时中转，先将盘子 1 从A移到B，然后将盘子2从A移动到C，最后再将盘子1从B移到C。

步骤：

1.移动 盘子1 从A-->B 2.移动 盘子2 从A-->C 3.移动 盘子1 从B-->C

移动三个盘子：

三个盘子一步步来看也是非常容易理解，先将盘子12用之前的方法移动到B（之前是移到C)，然后将3移动C，最后将在B位置的12在按照之前的方法移动C。

步骤：

1.移动 盘子1 从A-->C 2.移动 盘子2 从A-->B 3.移动 盘子1 从C-->B 4.移动 盘子3 从A-->C 5.移动 盘子1 从B-->A 6.移动 盘子2 从B-->C 7.移动 盘子1 从A-->C

通过上面的方法，可以看出规律，其实不管多少个圆盘，方法都是一样的，如果要想移动 n 个圆盘，只需要按照移动 n -1 个圆盘 时的方法移动即可。而要移动 n -1 个圆盘，就需要按照移动 n -2 个圆盘时的方法移动。这样追溯下去，最终就会回到移动 1 个圆盘时的操作方法上。

代码

理解

n =3时的详细流程图理解，红色部分表示会递归调用函数，黄色部分是结果。每到一个函数调用的位置，程序就会一直进行下去，直到n=1,然后返回之前的位置继续往后，竖着的可以看成程序主线，横着的是分支。

分形树

通过下面的图片，可以看出来，每到一个节点位置就一分为2。

如果要用turtle库绘制这样一个图形，可能会有点不知道从哪里下手。仔细观察可以发现，树的分支都是一样的，具有相同的结构，这种具有相同结构的方法，利用递归的思路，找到最小部分的解决方法，就可以解决整个大问题了。

分析

每一个节点处都可以看作是一个小树，小树由左右枝干组成，这里角度设置的是20度。前进先绘制主干，然后右转准备绘制右边枝干，绘制完右侧的，左转40度绘制左侧的树干，最后在回到之前的树枝。

代码

理解

进入程序后，先绘制右侧的数枝，当l小于5时，说明当前的数枝就绘制完毕了，程序接着会回答原来的位置，左转绘制右侧的树枝。

总结

通过这篇的两个案例，以及之前的，我们再来一起总结一下。

使用方法

终止条件和解决方法比较容易找到，主要是找到解决步骤和缩小规模，一般格式按照下面，具体问题会有些变化。

递归的三要素

1. 明确递归终止条件。

2. 给出递归终止时的处理办法，一般地，在这种情境下，问题的解决方案是直观的、容易的。

3.. 提取重复的逻辑，缩小问题规模。递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。