周鑫

摘要：該文對(duì)遞歸算法的實(shí)質(zhì)進(jìn)行了探討。以漢諾塔問題為例，提出一種圖解的方式，直觀地展示了遞歸算法的具體執(zhí)行過程，有助于初學(xué)者對(duì)遞歸思想的深入理解。

關(guān)鍵詞：遞歸；圖解；漢諾塔

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）07-1444-02

遞歸是一種有效的算法設(shè)計(jì)方法，它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對(duì)象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。遞歸是高中信息學(xué)奧賽必須掌握的基本算法思想，但在實(shí)際教學(xué)中卻發(fā)現(xiàn)，初學(xué)者對(duì)程序執(zhí)行的具體過程和參數(shù)傳遞過程難以理解，無法領(lǐng)會(huì)遞歸的實(shí)質(zhì)。為此，筆者根據(jù)自己多年的教學(xué)實(shí)踐，以漢諾塔——遞歸的典型例題為例，提出一種圖解的方式，展開遞歸算法的具體執(zhí)行過程。

1 漢諾塔問題描述

漢諾塔是一個(gè)經(jīng)典的數(shù)學(xué)問題，其具體描述如下：有三根相鄰的柱子，標(biāo)號(hào)為A，B，C，A 柱上從下到上按金字塔狀疊放著n 個(gè)不同大小的圓盤，現(xiàn)在把所有盤子借助于A，B，C 三個(gè)柱子一個(gè)一個(gè)移動(dòng)到C柱上，并且每次移動(dòng)在同一根柱子上都不能出現(xiàn)大盤在小盤上方的現(xiàn)象。根據(jù)問題描述得到以下規(guī)則：

1）圓盤必須一個(gè)一個(gè)的移動(dòng)；

2）大的圓盤必須在小圓盤的下方或單一圓盤；

3）滿足規(guī)則2）的序列可以出現(xiàn)在A，B，C 任意一根塔上。傳說布拉馬圣

2 漢諾塔問題的算法分析

漢諾塔問題中盤子的移動(dòng)過程雖然繁瑣，卻有規(guī)律性可循。要想將A柱上的N個(gè)盤子移動(dòng)至C柱，可以通過以下三個(gè)步驟實(shí)現(xiàn)：1）以C柱為過渡柱，從A柱將1至N- 1號(hào)盤移至B柱。2）將A柱中剩下的第N號(hào)盤移至C柱。3） 以A柱為過渡柱，從B柱將1至N- 1號(hào)盤移至C柱。這明顯是一個(gè)遞歸的過程，不斷深入，不斷細(xì)小化，最終，將到達(dá)僅有一個(gè)盤的情形，這時(shí)， 遞歸也就終止了，問題也得到了解決。我們看到，整個(gè)遞歸過程可分解為兩個(gè)問題，即最小子問題和漢諾塔問題。其中，步驟2是遞歸的終止條件，是一個(gè)能直接求解的最小子問題，只需移動(dòng)一個(gè)盤子就完成任務(wù)。步驟1、3均是n-1階的漢諾塔問題，不同階的區(qū)別在于各柱的作用不同。這樣，原問題被轉(zhuǎn)換為與原問題性質(zhì)相同、規(guī)模變小的子問題。即：將Hanoi（N，A，B，C） 轉(zhuǎn)化為Hanoi（N- 1，A，C，B） 與Hanoi（N- 1，B，A，C） 。其中Hanoi（）中的參數(shù)分別表示需移動(dòng)的盤子數(shù)、起始柱、過渡柱與目標(biāo)柱。

4 結(jié)束語

本文提出的圖解方式，較為直觀地描述了遞歸執(zhí)行的具體過程，詳細(xì)描述了如何利用它來解釋遞歸的實(shí)現(xiàn)過程。清晰明了地展現(xiàn)了遞歸過程中參數(shù)傳遞，局部變量的變化情況及過程調(diào)用和過程返回的執(zhí)行情況，是一種科學(xué)有效的說明遞歸問題的方法，有助于初學(xué)者深入理解遞歸的思想。經(jīng)過前后兩屆學(xué)生的教學(xué)實(shí)踐驗(yàn)證，教學(xué)滿意度提高，對(duì)理解遞歸的效果顯著。

參考文獻(xiàn)：

[1] 譚浩強(qiáng). C 程序設(shè)計(jì)[M].北京： 清華大學(xué)出版社，2011.

[2] 嚴(yán)蔚敏.吳偉民.數(shù)據(jù)結(jié)構(gòu)（ C 語言版）. 北京清華大學(xué)出版社，2011.

[3] 王挺，周會(huì)平. C+ + 程序設(shè)計(jì)[M].北京： 清華大學(xué)出版社， 2005.

[4] 白會(huì)波， 高瑞平. 漢諾塔問題的算法分析及C 語言演示程序的實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)， 2010（18）.