Scrateh遞歸程序設(shè)計(jì)的教學(xué)探討

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

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

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

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

文章編號(hào)：1009-3044（2020）15-0158-02

1引言

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

2遞歸算法的編程要點(diǎn)

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

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

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

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

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

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

3.1遞歸過(guò)程的實(shí)現(xiàn)——Hanoi（漢諾塔）問(wèn)題

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

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

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

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

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

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

4結(jié)論

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