1 引言
在计算机算法设计中，使用递归技术往往使函数的定义和算法的描述简捷且易于理解。有些数据结构如二叉树等由于其本身固有的递归特性，特别适合用递归的形式来描述。还有一些问题，虽然其本身并没有明显的递归结构，但用递归技术来求解使设计出的算法简洁、易懂。因此深入掌握递归技术在算法设计过程中可以设计出更加有效的算法[1]。
简单地说，递归就是用自己定义自己。使用递归方法构造算法的基本思路是：当求解规模为n的问题时，先将其分解成若干个规模较小的与原问题具有相同特征的子问题，并找出子问题与原问题之间的组合关系，最后根据具体问题构造出递归算法。
递归算法的执行过程分“递推”和“回归”两个阶段。在递推阶段，把较复杂问题（如：规模为n）的求解推理至较原问题简单一些的问题（如规模为n-1）的求解；在回归阶段，把递推结束时所得到的解，逐级返回，依次得到稍复杂问题的解，最终得到原问题的解[2]。
Hanoi塔问题是一个典型的适合于利用递归技术得到简洁算法的例子。Hanoi塔问题源自约19世纪末在欧洲出现的一种游戏，游戏中首先在一块铜板上放置三根柱子，在第一根柱子上自上而下、由小到大顺序串着64个盘子。游戏的目标是最后将所有盘子从第一根柱子上移到第三根柱子上，移动过程中可以用第二根柱子过渡。游戏规定一次只能移动一个盘子，并且任何时刻不允许大盘放在小盘的上面。
现在就给出关于Hanoi塔问题的程序，让其将Hanoi塔问题的执行过程动态演示出来，以帮助读者加深理解递归技术。
2 算法设计
我们先利用递归技术对该问题进行算法设计。我们将三根柱子分别标号为A、B、C，目标是要将n个盘子从A柱子移动到C柱子。该问题可以设计如下的递归算法：
第一步 将A柱子上n-1个盘子借助C柱子移动到B柱子上；
第二步 将A柱子上剩余的第n个盘子移动到C柱子上；
第三步 将B柱子上的n-1个盘子借助A柱子移动到C柱子上。
对于第一步和第三步，我们又可以利用类似的方法继续将其求解过程设计为一个规模为n-1的Hanoi塔递归算法。
3 递归算法动态演示过程的程序实现
对于该算法的程序实现有两个关键的难点，其一是初始化部分如何将三根柱子和n个盘子按照问题要求在屏幕上绘制出来；其二是盘子移动过程的图形实现。
3.1 form窗体设计及程序初始化
首先在form窗体中添加三个命令按钮
在开始执行Hanoi塔问题求解过程之前，需要将三根柱子绘制在屏幕上，还需要接收用户指定的盘子数及将盘子正确显示至A柱子上。在本程序中接收盘子数是利用InputBox函数接收保存至全局变量number中，用实心矩形代表盘子。
这一部分的初始化工作在准备按钮的click事件过程中实现，其核心代码如下：
Dim i As Integer
'设置Form窗体属性
Form1.Caption = "准备..."
Form1.Cls
'设置三个柱子的标记
CurrentX = 4000
CurrentY = hLevel + 61
Form1.FontSize = 16
Form1.ForeColor = vbRed
Form1.FontBold = True
Print "A"
CurrentX = 8000
CurrentY = hLevel + 61
Print "B"
CurrentX = 12000
CurrentY = hLevel + 61
Print "C"
Form1.ForeColor = &H80000012
Form1.FontSize = 10
Form1.FontBold = False
'画底线
Form1.Line (0, hLevel)-(15360, hLevel + 100), vbGreen, BF
'画三根柱子,A柱子的柱底坐标是(4000,10300)
'纵坐标减10只是为了显示时看的效果更好一些，其实是不应该减的，减了后柱子底端纵坐标与底线上沿纵坐标就不一致了，但屏幕视觉是一致的
Form1.Line (3995, 700)-(4005, hLevel - 10), vbBlack, BF
Form1.Line (7995, 700)-(8005, hLevel - 10), vbBlack, BF
Form1.Line (11995, 700)-(12008, hLevel - 10), vbBlack, BF
number = Val(InputBox("请输入盘子数：", "输入数据", "3"))
Form1.Caption = "共有" & number & "个盘子"
'盘子宽400*i,高度200
'相邻盘子之间的高度差设置为210，如果设置为相差200的话，当把上面一个盘子移走时两个盘子重叠部分无法重新修复
For i = 1 To number
Form1.Line ((4000 - (i * 400) / 2), (hLevel - (number + 1 - i) * 210))-((4000 + (i * 400) / 2), (hLevel - (number - i) * 210 - 10)), , BF
Next i
baseCoordinateY(1) = hLevel - number * 210
baseCoordinateY(2) = hLevel
baseCoordinateY(3) = hLevel
3.2 盘子移动的实现
盘子的移动过程主要有两种类型的移动，一种是垂直移动（包括自上而下和自下而上），另一种是水平移动（包括从左至右和从右至左）。盘子移动过程程序实现的主要思想是将每一次盘子从原位置移动到目标位置的路线分割成足够多的子路径，每个子路径的距离足够小，盘子从某子路径一端移动至另一端通过两个步骤来实现：第一步将原位置上的套友丈设置为form窗体背景色Form1.
BackColor，以达到将盘子从原位置移开的显示效果；第二步在盘子将要到达的新位置重新绘制该盘子，从而达到盘子移动到另一端的显示效果。
例如某个用Form1.Line (4000, i)-( 4000 +400), i + 200)语句绘制的长为400像素、宽为200像素的盘子需要从矩形左上角坐标为（4000, i）的位置垂直向上移动到下一位置，则可能将该矩形在原位置重新绘制成窗体背景色，在矩形左上角坐标为（4000, i-stepC）位置重新绘制一个矩形来达到将该矩形从位置（4000, i）移动到位置（4000, i-stepC）的目的，其中stepC是移动步长，也即子路径的长度。stepC值不能设置的过大，如果设置的太大，则盘子移动过程中将会出现不连续的移动效果。盘子移动过程程序实现的核心代码如下：
Dim i As Integer, j As Integer, k As Integer 'i、k表示纵坐标，j表示横坐标
Form1.Caption = "汉诺塔问题-第" & n & "个盘子正在移动..."
'向上移动到first柱子顶端
For i = baseCoordinateY(pillarnum(getone)) To 600 - 210 Step -stepC
'把矩形本次移动前的图形擦掉
Form1.Line ((pillarnum(getone) * 4000 - (n * 400) / 2), i)-((pillarnum(getone) * 4000 + (n * 400) / 2), i + 200), Form1.BackColor, BF
fixpillar (getone)
Form1.Line ((pillarnum(getone) * 4000 - (n * 400) / 2), i - stepC)-((pillarnum(getone) * 4000 + (n * 400) / 2), i - stepC + 200), , BF
delay
Next i
'当前i =600-200-stepC，此时i值表示盘子的当前纵坐标
'向左、右平移到third柱子顶端
If pillarnum(getone) < pillarnum(putone) Then
'向右移
For j = (pillarnum(getone) * 4000 - (n * 400) / 2) To (pillarnum(putone) * 4000 - (n * 400) / 2) - stepC Step stepC
Form1.Line (j, i)-(j + n * 400, i + 200), Form1.BackColor, BF
Form1.Line (j + stepC, i)-(j + stepC + n * 400, i + 200), , BF
delay
Next j
Else
'向左移
For j = (pillarnum(getone) * 4000 - (n * 400) / 2) To (pillarnum(putone) * 4000 - (n * 400) / 2) + stepC Step -stepC
Form1.Line (j, i)-(j + n * 400, i + 200), Form1.BackColor, BF
Form1.Line (j - stepC, i)-(j - stepC + n * 400, i + 200), , BF
delay
Next j
End If
'向下移动到third柱子底端
For k = i To baseCoordinateY(pillarnum(putone)) - 210 - stepC Step stepC
'把矩形本次移动前的图形擦掉
Form1.Line ((pillarnum(putone) * 4000 - (n * 400) / 2), k)-((pillarnum(putone) * 4000 + (n * 400) / 2), k + 200), Form1.BackColor, BF
fixpillar (putone)
Form1.Line ((pillarnum(putone) * 4000 - (n * 400) / 2), k + stepC)-((pillarnum(putone) * 4000 + (n * 400) / 2), k + stepC + 200), , BF
delay
Next k
'最后在柱子底端再补画一次高度为210的矩形,
'因为k循环最后一次执行循环体时，k值未必正好等于循环终值baseCoordinateY(pillarnum(putone)) - 210 - stepC,
'所以要补一个上沿纵坐标为baseCoordinateY(pillarnum(putone)) - 210 - stepC矩形
Form1.Line ((pillarnum(putone) * 4000 - (n * 400) / 2), k)-((pillarnum(putone) * 4000 + (n * 400) / 2), k + 200), Form1.BackColor, BF
fixpillar (putone)
Form1.Line ((pillarnum(putone) * 4000 - (n * 400) / 2), baseCoordinateY(pillarnum(putone)) - 210)-((pillarnum(putone) * 4000 + (n * 400) / 2), baseCoordinateY(pillarnum(putone)) - 210 + 200), , BF
'更新各柱子最面一个盘子上沿的纵坐标
baseCoordinateY(pillarnum(getone)) = baseCoordinateY(pillarnum(getone)) + 210
baseCoordinateY(pillarnum(putone)) = baseCoordinateY(pillarnum(putone)) - 210
End Sub
Private Function pillarnum(ch As String) As Integer
pillarnum = Asc(ch) + 1 - Asc("A")
End Function
Private Sub fixpillar(pillarABC As String)
'纵坐标减10只是为了显示时看的效果更好一些，其实是不应该减的，减了后柱子底端纵坐标与底线上沿纵坐标就不一致了
If pillarnum(pillarABC) < 3 Then
Form1.Line (pillarnum(pillarABC) * 4000 - 5, 700)-(pillarnum(pillarABC) * 4000 + 5, hLevel - 10), vbBlack, BF '修补柱子
Else
Form1.Line (pillarnum(pillarABC) * 4000 - 5, 700)-(pillarnum(pillarABC) * 4000 + 8, hLevel - 10), vbBlack, BF '修补柱子
End If
另外，需要注意的一点是当盘子垂直移动时，在盘子的原位置重新绘制盘子为窗体背景色时，由于会导致一段柱子也会被覆盖成窗体背景色，因此在原位置绘制盘子为背景色之后应立即重新绘制一次柱子。
由于目前技术水平下PC机的CPU性能比较高，程序的执行时间非常短，为了得到一个适度缓慢的盘子移动速度，在盘子移动到下一个位置时应该暂停一个时间段。本程序中通过设置一个延迟函数以达到目的，当盘子从子路径的一端移动到另一端时立即调用自定义延迟函数delay（），delay（）函数只是起到暂停程序执行的作用，不执行任何改变盘子现状的指令。一个delay（）函数的例子如下：
Private Sub delay()
Dim tt As Double
tt = Timer
While Timer - tt < 0.001 '延迟
DoEvents
Wend
End Sub
4 结束语
本文实现了一个完整的Hanoi塔问题动态演示程序，由用户输入盘子数，盘子数目限定在1至10之间，盘子太多，屏幕显示不下。程序编写、运行环境为windows xp+vb6.0，屏幕分辩率为1024×768。
3COME考试频道为您精心整理，希望对您有所帮助，更多信息在http://www.reader8.net/exam/