1 引言
    在計(jì)算機(jī)算法設(shè)計(jì)中，使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡(jiǎn)捷且易于理解。有些數(shù)據(jù)結(jié)構(gòu)如二叉樹(shù)等由于其本身固有的遞歸特性，特別適合用遞歸的形式來(lái)描述。還有一些問(wèn)題，雖然其本身并沒(méi)有明顯的遞歸結(jié)構(gòu)，但用遞歸技術(shù)來(lái)求解使設(shè)計(jì)出的算法簡(jiǎn)潔、易懂。因此深入掌握遞歸技術(shù)在算法設(shè)計(jì)過(guò)程中可以設(shè)計(jì)出更加有效的算法[1]。
    簡(jiǎn)單地說(shuō)，遞歸就是用自己定義自己。使用遞歸方法構(gòu)造算法的基本思路是：當(dāng)求解規(guī)模為n的問(wèn)題時(shí)，先將其分解成若干個(gè)規(guī)模較小的與原問(wèn)題具有相同特征的子問(wèn)題，并找出子問(wèn)題與原問(wèn)題之間的組合關(guān)系，最后根據(jù)具體問(wèn)題構(gòu)造出遞歸算法。
    遞歸算法的執(zhí)行過(guò)程分“遞推”和“回歸”兩個(gè)階段。在遞推階段，把較復(fù)雜問(wèn)題（如：規(guī)模為n）的求解推理至較原問(wèn)題簡(jiǎn)單一些的問(wèn)題（如規(guī)模為n-1）的求解；在回歸階段，把遞推結(jié)束時(shí)所得到的解，逐級(jí)返回，依次得到稍復(fù)雜問(wèn)題的解，最終得到原問(wèn)題的解[2]。
    Hanoi塔問(wèn)題是一個(gè)典型的適合于利用遞歸技術(shù)得到簡(jiǎn)潔算法的例子。Hanoi塔問(wèn)題源自約19世紀(jì)末在歐洲出現(xiàn)的一種游戲，游戲中首先在一塊銅板上放置三根柱子，在第一根柱子上自上而下、由小到大順序串著64個(gè)盤(pán)子。游戲的目標(biāo)是最后將所有盤(pán)子從第一根柱子上移到第三根柱子上，移動(dòng)過(guò)程中可以用第二根柱子過(guò)渡。游戲規(guī)定一次只能移動(dòng)一個(gè)盤(pán)子，并且任何時(shí)刻不允許大盤(pán)放在小盤(pán)的上面。
    現(xiàn)在就給出關(guān)于Hanoi塔問(wèn)題的程序，讓其將Hanoi塔問(wèn)題的執(zhí)行過(guò)程動(dòng)態(tài)演示出來(lái)，以幫助讀者加深理解遞歸技術(shù)。
    2 算法設(shè)計(jì)
    我們先利用遞歸技術(shù)對(duì)該問(wèn)題進(jìn)行算法設(shè)計(jì)。我們將三根柱子分別標(biāo)號(hào)為A、B、C，目標(biāo)是要將n個(gè)盤(pán)子從A柱子移動(dòng)到C柱子。該問(wèn)題可以設(shè)計(jì)如下的遞歸算法：
    第一步 將A柱子上n-1個(gè)盤(pán)子借助C柱子移動(dòng)到B柱子上；
    第二步 將A柱子上剩余的第n個(gè)盤(pán)子移動(dòng)到C柱子上；
    第三步 將B柱子上的n-1個(gè)盤(pán)子借助A柱子移動(dòng)到C柱子上。
    對(duì)于第一步和第三步，我們又可以利用類似的方法繼續(xù)將其求解過(guò)程設(shè)計(jì)為一個(gè)規(guī)模為n-1的Hanoi塔遞歸算法。
    3 遞歸算法動(dòng)態(tài)演示過(guò)程的程序?qū)崿F(xiàn)
    對(duì)于該算法的程序?qū)崿F(xiàn)有兩個(gè)關(guān)鍵的難點(diǎn)，其一是初始化部分如何將三根柱子和n個(gè)盤(pán)子按照問(wèn)題要求在屏幕上繪制出來(lái)；其二是盤(pán)子移動(dòng)過(guò)程的圖形實(shí)現(xiàn)。
    3.1 form窗體設(shè)計(jì)及程序初始化
    首先在form窗體中添加三個(gè)命令按鈕
    在開(kāi)始執(zhí)行Hanoi塔問(wèn)題求解過(guò)程之前，需要將三根柱子繪制在屏幕上，還需要接收用戶指定的盤(pán)子數(shù)及將盤(pán)子正確顯示至A柱子上。在本程序中接收盤(pán)子數(shù)是利用InputBox函數(shù)接收保存至全局變量number中，用實(shí)心矩形代表盤(pán)子。
    這一部分的初始化工作在準(zhǔn)備按鈕的click事件過(guò)程中實(shí)現(xiàn)，其核心代碼如下：
    Dim i As Integer
    '設(shè)置Form窗體屬性
    Form1.Caption = "準(zhǔn)備..."
    Form1.Cls
    '設(shè)置三個(gè)柱子的標(biāo)記
    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
    '畫(huà)底線
    Form1.Line (0, hLevel)-(15360, hLevel + 100), vbGreen, BF
    '畫(huà)三根柱子,A柱子的柱底坐標(biāo)是(4000,10300)
    '縱坐標(biāo)減10只是為了顯示時(shí)看的效果更好一些，其實(shí)是不應(yīng)該減的，減了后柱子底端縱坐標(biāo)與底線上沿縱坐標(biāo)就不一致了，但屏幕視覺(jué)是一致的
    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("請(qǐng)輸入盤(pán)子數(shù)：", "輸入數(shù)據(jù)", "3"))
    Form1.Caption = "共有" & number & "個(gè)盤(pán)子"
    '盤(pán)子寬400*i,高度200
    '相鄰盤(pán)子之間的高度差設(shè)置為210，如果設(shè)置為相差200的話，當(dāng)把上面一個(gè)盤(pán)子移走時(shí)兩個(gè)盤(pán)子重疊部分無(wú)法重新修復(fù)
    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 盤(pán)子移動(dòng)的實(shí)現(xiàn)
    盤(pán)子的移動(dòng)過(guò)程主要有兩種類型的移動(dòng)，一種是垂直移動(dòng)（包括自上而下和自下而上），另一種是水平移動(dòng)（包括從左至右和從右至左）。盤(pán)子移動(dòng)過(guò)程程序?qū)崿F(xiàn)的主要思想是將每一次盤(pán)子從原位置移動(dòng)到目標(biāo)位置的路線分割成足夠多的子路徑，每個(gè)子路徑的距離足夠小，盤(pán)子從某子路徑一端移動(dòng)至另一端通過(guò)兩個(gè)步驟來(lái)實(shí)現(xiàn)：第一步將原位置上的套友丈柚夢(mèng)猣orm窗體背景色Form1.
    BackColor，以達(dá)到將盤(pán)子從原位置移開(kāi)的顯示效果；第二步在盤(pán)子將要到達(dá)的新位置重新繪制該盤(pán)子，從而達(dá)到盤(pán)子移動(dòng)到另一端的顯示效果。
    例如某個(gè)用Form1.Line (4000, i)-( 4000 +400), i + 200)語(yǔ)句繪制的長(zhǎng)為400像素、寬為200像素的盤(pán)子需要從矩形左上角坐標(biāo)為（4000, i）的位置垂直向上移動(dòng)到下一位置，則可能將該矩形在原位置重新繪制成窗體背景色，在矩形左上角坐標(biāo)為（4000, i-stepC）位置重新繪制一個(gè)矩形來(lái)達(dá)到將該矩形從位置（4000, i）移動(dòng)到位置（4000, i-stepC）的目的，其中stepC是移動(dòng)步長(zhǎng)，也即子路徑的長(zhǎng)度。stepC值不能設(shè)置的過(guò)大，如果設(shè)置的太大，則盤(pán)子移動(dòng)過(guò)程中將會(huì)出現(xiàn)不連續(xù)的移動(dòng)效果。盤(pán)子移動(dòng)過(guò)程程序?qū)崿F(xiàn)的核心代碼如下：
    Dim i As Integer, j As Integer, k As Integer 'i、k表示縱坐標(biāo)，j表示橫坐標(biāo)
    Form1.Caption = "漢諾塔問(wèn)題-第" & n & "個(gè)盤(pán)子正在移動(dòng)..."
    '向上移動(dòng)到first柱子頂端
    For i = baseCoordinateY(pillarnum(getone)) To 600 - 210 Step -stepC
    '把矩形本次移動(dòng)前的圖形擦掉
    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
    '當(dāng)前i =600-200-stepC，此時(shí)i值表示盤(pán)子的當(dāng)前縱坐標(biāo)
    '向左、右平移到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
    '向下移動(dòng)到third柱子底端
    For k = i To baseCoordinateY(pillarnum(putone)) - 210 - stepC Step stepC
    '把矩形本次移動(dòng)前的圖形擦掉
    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
    '最后在柱子底端再補(bǔ)畫(huà)一次高度為210的矩形,
    '因?yàn)閗循環(huán)最后一次執(zhí)行循環(huán)體時(shí)，k值未必正好等于循環(huán)終值baseCoordinateY(pillarnum(putone)) - 210 - stepC,
     '所以要補(bǔ)一個(gè)上沿縱坐標(biāo)為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
    '更新各柱子最面一個(gè)盤(pán)子上沿的縱坐標(biāo)
    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)
    '縱坐標(biāo)減10只是為了顯示時(shí)看的效果更好一些，其實(shí)是不應(yīng)該減的，減了后柱子底端縱坐標(biāo)與底線上沿縱坐標(biāo)就不一致了
    If pillarnum(pillarABC) < 3 Then
    Form1.Line (pillarnum(pillarABC) * 4000 - 5, 700)-(pillarnum(pillarABC) * 4000 + 5, hLevel - 10), vbBlack, BF '修補(bǔ)柱子
    Else
    Form1.Line (pillarnum(pillarABC) * 4000 - 5, 700)-(pillarnum(pillarABC) * 4000 + 8, hLevel - 10), vbBlack, BF '修補(bǔ)柱子
    End If
    另外，需要注意的一點(diǎn)是當(dāng)盤(pán)子垂直移動(dòng)時(shí)，在盤(pán)子的原位置重新繪制盤(pán)子為窗體背景色時(shí)，由于會(huì)導(dǎo)致一段柱子也會(huì)被覆蓋成窗體背景色，因此在原位置繪制盤(pán)子為背景色之后應(yīng)立即重新繪制一次柱子。
    由于目前技術(shù)水平下PC機(jī)的CPU性能比較高，程序的執(zhí)行時(shí)間非常短，為了得到一個(gè)適度緩慢的盤(pán)子移動(dòng)速度，在盤(pán)子移動(dòng)到下一個(gè)位置時(shí)應(yīng)該暫停一個(gè)時(shí)間段。本程序中通過(guò)設(shè)置一個(gè)延遲函數(shù)以達(dá)到目的，當(dāng)盤(pán)子從子路徑的一端移動(dòng)到另一端時(shí)立即調(diào)用自定義延遲函數(shù)delay（），delay（）函數(shù)只是起到暫停程序執(zhí)行的作用，不執(zhí)行任何改變盤(pán)子現(xiàn)狀的指令。一個(gè)delay（）函數(shù)的例子如下：
    Private Sub delay()
    Dim tt As Double
    tt = Timer
    While Timer - tt < 0.001 '延遲
    DoEvents
    Wend
    End Sub
    4 結(jié)束語(yǔ)
    本文實(shí)現(xiàn)了一個(gè)完整的Hanoi塔問(wèn)題動(dòng)態(tài)演示程序，由用戶輸入盤(pán)子數(shù)，盤(pán)子數(shù)目限定在1至10之間，盤(pán)子太多，屏幕顯示不下。程序編寫(xiě)、運(yùn)行環(huán)境為windows xp+vb6.0，屏幕分辯率為1024×768。