江玉珍 朱映輝 鄧清華 王曉輝 陸錫聰

摘要：在常規(guī)的程序設(shè)計教學(xué)中，遞歸算法能在運(yùn)行過程中實現(xiàn)自我調(diào)用，能將大問題層層轉(zhuǎn)化為小規(guī)模相似問題來進(jìn)行求解，雖然其理解上抽象難懂但卻能夠輕巧地解決很多復(fù)雜問題，是結(jié)構(gòu)化程序教學(xué)上重點和難點。通過對遞歸算法原理的分析，提出抓住三個要點及構(gòu)造遞歸表達(dá)式的學(xué)習(xí)方法。結(jié)合Scratch簡潔的編程風(fēng)格，通過舉例提出基于Scratch的遞歸算法教學(xué)引導(dǎo)思路，并分析探討更有效的遞歸教學(xué)方法。

關(guān)鍵詞：遞歸;回溯;遞推;Scratch;漢諾塔

中圖分類號：G642 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）15-0158-02

1引言

在計算機(jī)各種語言的程序設(shè)計教學(xué)上，學(xué)生掌握了循環(huán)和函數(shù)應(yīng)用后，就會接觸到遞歸算法程序設(shè)計。遞歸算法是程序教學(xué)中的一個難點，因為它太抽象，不像循環(huán)那樣具體，學(xué)生往往會因難以深入地跟蹤到函數(shù)自我調(diào)用中各層次間參數(shù)的傳遞關(guān)系，而對它產(chǎn)生抗拒的情緒。然而，遞歸算法又是程序教學(xué)中的一個不能規(guī)避的重點，因為它是一種優(yōu)雅的問題解決方法，許多多重循環(huán)難以實現(xiàn)的問題，用遞歸算法卻總能輕巧地迎刃而解。雖然所有的遞歸算法最終都可以使用非遞歸方法來實現(xiàn)，而且當(dāng)同一問題同時用循環(huán)和遞歸解決時，遞歸算法通常沒有性能上的優(yōu)勢，因為它在自我調(diào)用時必須使用堆棧來輔助處理。但是，當(dāng)一些復(fù)雜問題面臨解決時，使用遞歸算法卻總能在第一時間獲得解決方法，而且程序簡潔直觀，這正是它無可比擬的優(yōu)勢，也是它作為編程教學(xué)重點的原因。

2遞歸算法的編程要點

遞歸函數(shù)的調(diào)用過程又分成兩個部分，回溯階段和遞推階段。前半部分是回溯階段，就是把大問題層層轉(zhuǎn)化為較小的問題，每次遞歸調(diào)用都會簡化原始問題，讓它不斷地接近最簡狀態(tài)，這樣一旦達(dá)到最簡狀態(tài)時就結(jié)束遞歸調(diào)用，進(jìn)入遞推階段，將小問題求解結(jié)果又層層轉(zhuǎn)換為大問題求解結(jié)果，直到初始問題獲解。因此，在遞歸算法設(shè)計中，有以下三個要點：（1）要有明確的遞歸終止條件，防止程序陷入無限調(diào)用;（2）要有明顯的判斷語句來引導(dǎo)遞歸調(diào)用走向;（3）過程或函數(shù)自身的調(diào)用要趨向遞歸的終止條件。

對此，在教學(xué)上，可以引導(dǎo)學(xué)生先對復(fù)雜問題進(jìn)行剖析、寫成遞歸表達(dá)式，遞歸表達(dá)式必須具備上述三個要點，然后再進(jìn)行程序編寫，這樣可以起到事半功倍的作用。比如，對于n！的遞歸函數(shù)，可以寫成式（1）表達(dá)式。

該兩個表達(dá)式中，第1行表示遞歸終止條件，即問題的最簡狀態(tài)。第2行表示遞歸自我調(diào)用的關(guān)系，用于表示“n問題”至“n-1或n-2問題”的轉(zhuǎn)換關(guān)系，并反映出調(diào)用趨勢是向著遞歸終止條件發(fā)展的。

3Scrateh的算法程序設(shè)計

Scratch是麻省理工學(xué)院（MIT）設(shè)計開發(fā)的一款面向編程初學(xué)者的圖形化編程工具，其功能豐富易學(xué)易用，有助于學(xué)生邏輯計算思維的鍛煉嘲。對于程序初學(xué)者尤其青少年而言，學(xué)習(xí)編程其實并不是為了會寫代碼，而是為了將想法變成現(xiàn)實，實現(xiàn)一個完整的問題解決方法。Scratch就提供這樣一個便利的平臺，它可以不用花太多精力去關(guān)注那些易出錯的語法表達(dá)和數(shù)據(jù)結(jié)構(gòu)，讓開發(fā)者更專注于解決方法的運(yùn)用。Scratch自推出至今已經(jīng)歷多次改版升級，Scratch3.0具備自定義模塊（過程）功能，既適合常規(guī)圖形互動類程序設(shè)計，也非常適合算法類的程序設(shè)計。而且，Scratch與其他程序語言一樣，能夠支持帶參的自定義模塊的自我調(diào)用，所以利用Scratch可以更容易地實現(xiàn)遞歸算法。

根據(jù)自調(diào)用模塊的返值情況，遞歸算法可分為遞歸過程（沒有返值）和遞歸函數(shù)（有返值）。Scratch3.0自定義模塊本身可以帶參，但不能返值，因此在遞歸過程和遞歸函數(shù)的處理方法上略有不同，以下分別通過2個經(jīng)典遞歸案例來分析說明各自實現(xiàn)方法的要點。

3.1遞歸過程的實現(xiàn)——Hanoi（漢諾塔）問題

漢諾塔是經(jīng)典的遞歸算法問題，該問題若用非遞歸方法進(jìn)行求解會非常煩瑣，但使用遞歸方法求解卻簡單明了。設(shè)ha-noi（n，A，B，c）表示有n個盤子要從A座借助B座移動至c座，move（A，C）表示將最上面一個盤子從x座移動至Y座，則該問題的遞歸表達(dá)式如式f3）。

Hanoi（漢諾塔）n盤子問題的Scratch遞歸程序如圖l所示。由圖可見，該程序定義了2個模塊：“漢諾塔”和“搬”分別對應(yīng)式（3）中的“hainoi（）”和“move（）”，其中“漢諾塔”除調(diào)用“搬”模塊外，還調(diào)用了2次自身，即“漢諾塔”，注意此時參數(shù)上的變動。借助列表對每次搬動狀態(tài)的記錄，程序運(yùn)行后，用戶輸入初始盤子個數(shù)，列表將顯示需搬動的總次數(shù)和搬動序列。

3.2遞歸函數(shù)的實現(xiàn)——賣鴨子問題

遞歸算法更普遍的用法是遞歸函數(shù)。如n！、Fibonacci數(shù)列等在表達(dá)成遞歸函數(shù)時均有一個函數(shù)返回值，這個返回值在遞推階段也起到重要的向上層傳值的作用。既然Scratch自定義模塊不能像普通函數(shù)那樣獲得返回值，那么又該如何實現(xiàn)帶返值的遞歸函數(shù)呢？對于這個問題，解決的辦法其實并不難，只需增設(shè)一個外部變量來代替函數(shù)值，在模塊遞歸調(diào)用后對該變量進(jìn)行迭代賦值即可。

賣鴨子問題：農(nóng)夫趕著鴨子去每個村莊賣，每經(jīng)過一個村子賣去所趕鴨子的一半又一只。這樣他經(jīng)過了m個村子后還剩n只鴨子，問他出發(fā)時共有多少只鴨子？若用ducks（x）表示經(jīng)過m個村子前鴨子的總數(shù)，那么該問題的遞歸表達(dá)式如式（4）。

Scratch程序?qū)崿F(xiàn)時，自定義遞歸模塊方法和主調(diào)程序如圖2所示。由圖2可知，“算鴨子”是自定義的遞歸模塊，即其內(nèi)部又調(diào)用了“算鴨子”。為傳遞內(nèi)外遞歸模塊的返回值，“算鴨子”模塊內(nèi)部使用了一個外部變量“原有鴨子總數(shù)”，每次遞歸調(diào)用后該變量值均做迭代更新，所以該變量實際上就起到函數(shù)返回值的作用。

4結(jié)論

遞歸算法雖然運(yùn)行效率不高，但它的程序設(shè)計效率高且程序結(jié)構(gòu)簡潔清晰，教學(xué)上，重點是引導(dǎo)學(xué)生理解遞歸的實質(zhì)是“分而治之”，即“大問題分解為本質(zhì)相同的小問題”的思想。實際上在遞歸算法設(shè)計中，只要能找出問題內(nèi)在的自我遞推關(guān)系，緊緊抓住“遞歸終止條件”“判斷引導(dǎo)”和“有趨向的自我調(diào)用”這三個要點、構(gòu)建出其遞歸表達(dá)式，就能輕巧地將問題轉(zhuǎn)化為遞歸功能模塊并實現(xiàn)程序調(diào)用。在遞歸算法的掌握上，解決思路理解和運(yùn)用遠(yuǎn)比程序編碼更為重要，以c++為代表大多數(shù)的程序語言都能支持遞歸表示，但這些程序語言在編寫遞歸程序時往往還要考慮大量語法表示、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)等多種因素，程序也容易出現(xiàn)算法以外的錯誤從而加大編程者的調(diào)試負(fù)擔(dān)。Scratch簡單的程序設(shè)計方法一定程度上屏蔽了編程中在語法、數(shù)據(jù)結(jié)構(gòu)等方面的諸多限制，讓編程者更專注于算法設(shè)計本身，并在算法基礎(chǔ)上實現(xiàn)程序的快速構(gòu)建。因此，在算法程序教學(xué)上，它可以成為認(rèn)知、理解及應(yīng)用遞歸算法的一個良好的引導(dǎo)平臺。