Scrateh遞歸程序設計的教學探討

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

摘要：在常規的程序設計教學中，遞歸算法能在運行過程中實現自我調用，能將大問題層層轉化為小規模相似問題來進行求解，雖然其理解上抽象難懂但卻能夠輕巧地解決很多復雜問題，是結構化程序教學上重點和難點。通過對遞歸算法原理的分析，提出抓住三個要點及構造遞歸表達式的學習方法。結合Scratch簡潔的編程風格，通過舉例提出基于Scratch的遞歸算法教學引導思路，并分析探討更有效的遞歸教學方法。

關鍵詞：遞歸;回溯;遞推;Scratch;漢諾塔

中圖分類號：G642 文獻標識碼：A

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

1引言

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

2遞歸算法的編程要點

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

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

該兩個表達式中，第1行表示遞歸終止條件，即問題的最簡狀態。第2行表示遞歸自我調用的關系，用于表示“n問題”至“n-1或n-2問題”的轉換關系，并反映出調用趨勢是向著遞歸終止條件發展的。

3Scrateh的算法程序設計

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

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

3.1遞歸過程的實現——Hanoi（漢諾塔）問題

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

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

3.2遞歸函數的實現——賣鴨子問題

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

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

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

4結論

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