1 引言

　　在計算機算法設計中，使用遞歸技術往往使函數(shù)的定義和算法的描述簡捷且易于理解。有些數(shù)據(jù)結構如二叉樹等由于其本身固有的遞歸特性，特別適合用遞歸的形式來描述。還有一些問題，雖然其本身并沒有明顯的遞歸結構，但用遞歸技術來求解使設計出的算法簡潔、易懂。因此深入掌握遞歸技術在算法設計過程中可以設計出更加有效的算法。

　　簡單地說，遞歸就是用自己定義自己。使用遞歸方法構造算法的基本思路是：當求解規(guī)模為n的問題時，先將其分解成若干個規(guī)模較小的與原問題具有相同特征的子問題，并找出子問題與原問題之間的組合關系，最后根據(jù)具體問題構造出遞歸算法。

　　遞歸算法的執(zhí)行過程分“遞推”和“回歸”兩個階段。在遞推階段，把較復雜問題(如：規(guī)模為n)的求解推理至較原問題簡單一些的問題(如規(guī)模為n-1)的求解;在回歸階段，把遞推結束時所得到的解，逐級返回，依次得到稍復雜問題的解，最終得到原問題的解。

　　Hanoi塔問題是一個典型的適合于利用遞歸技術得到簡潔算法的例子。Hanoi塔問題源自約19世紀末在歐洲出現(xiàn)的一種游戲，游戲中首先在一塊銅板上放置三根柱子，在第一根柱子上自上而下、由小到大順序串著64個盤子。游戲的目標是最后將所有盤子從第一根柱子上移到第三根柱子上，移動過程中可以用第二根柱子過渡。游戲規(guī)定一次只能移動一個盤子，并且任何時刻不允許大盤放在小盤的上面。

　　現(xiàn)在就給出關于Hanoi塔問題的程序，讓其將Hanoi塔問題的執(zhí)行過程動態(tài)演示出來，以幫助讀者加深理解遞歸技術。

　　2 算法設計

　　我們先利用遞歸技術對該問題進行算法設計。我們將三根柱子分別標號為A、B、C，目標是要將n個盤子從A柱子移動到C柱子。該問題可以設計如下的遞歸算法：

　　第一步 將A柱子上n-1個盤子借助C柱子移動到B柱子上;

　　第二步 將A柱子上剩余的第n個盤子移動到C柱子上;

　　第三步 將B柱子上的n-1個盤子借助A柱子移動到C柱子上。

　　對于第一步和第三步，我們又可以利用類似的方法繼續(xù)將其求解過程設計為一個規(guī)模為n-1的Hanoi塔遞歸算法。

　　3 遞歸算法動態(tài)演示過程的程序?qū)崿F(xiàn)

　　對于該算法的程序?qū)崿F(xiàn)有兩個關鍵的難點，其一是初始化部分如何將三根柱子和n個盤子按照問題要求在屏幕上繪制出來;其二是盤子移動過程的圖形實現(xiàn)。

　　3.1 form窗體設計及程序初始化

　　首先在form窗體中添加三個命令按鈕。

　　在開始執(zhí)行Hanoi塔問題求解過程之前，需要將三根柱子繪制在屏幕上，還需要接收用戶指定的盤子數(shù)及將盤子正確顯示至A柱子上。在本程序中接收盤子數(shù)是利用InputBox函數(shù)接收保存至全局變量number中，用實心矩形代表盤子。