1 引言

　　 在计算机算法设计中，使用递归技术往往使函数的定义和算法的描述简捷且易于理解。有些数据结构如二叉树等由于其本身固有的递归特性，特别适合用递归的形式来描述。还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁、易懂。因此深入掌握递归技术在算法设计过程中可以设计出更加有效的算法^[1]。

　　 简单地说，递归就是用自己定义自己。使用递归方法构造算法的基本思路是：当求解规模为n的问题时，先将其分解成若干个规模较小的与原问题具有相同特征的子问题，并找出子问题与原问题之间的组合关系，最后根据具体问题构造出递归算法。

　　 递归算法的执行过程分“递推”和“回归”两个阶段。在递推阶段，把较复杂问题（如：规模为n）的求解推理至较原问题简单一些的问题（如规模为n-1）的求解；在回归阶段，把递推结束时所得到的解，逐级返回，依次得到稍复杂问题的解，最终得到原问题的解^[2]。

　　 Hanoi塔问题是一个典型的适合于利用递归技术得到简洁算法的例子。Hanoi塔问题源自约19世纪末在欧洲出现的一种游戏，游戏中首先在一块铜板上放置三根柱子，在第一根柱子上自上而下、由小到大顺序串着64个盘子。游戏的目标是最后将所有盘子从第一根柱子上移到第三根柱子上，移动过程中可以用第二根柱子过渡。游戏规定一次只能移动一个盘子，并且任何时刻不允许大盘放在小盘的上面。

　　 现在就给出关于Hanoi塔问题的程序，让其将Hanoi塔问题的执行过程动态演示出来，以帮助读者加深理解递归技术。

　　2 算法设计

　　 我们先利用递归技术对该问题进行算法设计。我们将三根柱子分别标号为A、B、C，目标是要将n个盘子从A柱子移动到C柱子。该问题可以设计如下的递归算法：