《用遞歸法解決問(wèn)題》教學(xué)設(shè)計(jì)

龐霞+曹恒來(lái)

學(xué)習(xí)者分析

本節(jié)課的教學(xué)對(duì)象為高中二年級(jí)的學(xué)生。這個(gè)階段的學(xué)生具有很強(qiáng)的自主意識(shí)，具備一定的探究能力，喜歡自己動(dòng)手實(shí)踐來(lái)獲得新知。多次經(jīng)歷從問(wèn)題到程序的思考過(guò)程，在面對(duì)現(xiàn)有軟件無(wú)法解決的問(wèn)題時(shí)能夠編寫程序解決問(wèn)題。在此之前，學(xué)生已經(jīng)掌握了循環(huán)、數(shù)組、自定義函數(shù)的使用，為本課的學(xué)習(xí)做好了充分的準(zhǔn)備。

學(xué)習(xí)內(nèi)容分析

《用遞歸法解決問(wèn)題》是高中選修教材《算法與程序設(shè)計(jì)》（科教版）第三章“算法的程序?qū)崿F(xiàn)”第五小節(jié)的內(nèi)容。在本課學(xué)習(xí)之前，學(xué)生已經(jīng)學(xué)會(huì)了用循環(huán)的方法來(lái)解決問(wèn)題，然而循環(huán)的方法往往并不會(huì)那么清晰地描述解決問(wèn)題的步驟，遞歸法則可以非常直白地描述一個(gè)問(wèn)題的求解過(guò)程，因此遞歸法也是最容易實(shí)現(xiàn)的算法。

遞歸的基本思想是把規(guī)模大的問(wèn)題轉(zhuǎn)化為規(guī)模小的相類似的子問(wèn)題來(lái)解決。在函數(shù)實(shí)現(xiàn)時(shí)，因?yàn)榻鉀Q大問(wèn)題的方法和解決小問(wèn)題的方法往往是同一種方法，所以就產(chǎn)生了調(diào)用自身的情況。遞歸是利用系統(tǒng)的堆棧保存函數(shù)中的局部變量來(lái)解決問(wèn)題的，因?yàn)楹瘮?shù)調(diào)用的開(kāi)銷比較大，遞歸常常會(huì)帶來(lái)效率問(wèn)題。本節(jié)課學(xué)生不僅要學(xué)會(huì)用遞歸法解決問(wèn)題，更重要的是領(lǐng)會(huì)遞歸思想的精髓。遞歸思想是計(jì)算機(jī)學(xué)科中的核心技術(shù)思想之一，其本質(zhì)反映的是一種將復(fù)雜問(wèn)題簡(jiǎn)單化的思維方法。

學(xué)習(xí)目標(biāo)

知識(shí)與技能目標(biāo)：理解遞歸的含義，找出遞歸問(wèn)題中縮小問(wèn)題規(guī)模的遞歸處理方法及遞歸結(jié)束條件，了解遞歸算法的優(yōu)缺點(diǎn)。

過(guò)程與方法目標(biāo)：能用程序?qū)崿F(xiàn)遞歸算法，學(xué)會(huì)用簡(jiǎn)單模式解決復(fù)雜問(wèn)題的方法。

情感態(tài)度與價(jià)值觀目標(biāo)：領(lǐng)悟遞歸思想，體驗(yàn)遞歸思想在實(shí)際生活中的應(yīng)用。

教學(xué)重點(diǎn)、難點(diǎn)

重點(diǎn)：分析遞歸結(jié)束條件及縮小問(wèn)題規(guī)模的方法，以及遞歸算法的程序?qū)崿F(xiàn)。

難點(diǎn)：遞歸算法的程序?qū)崿F(xiàn)。

教學(xué)策略

呈現(xiàn)斐波那契數(shù)列問(wèn)題，由學(xué)生比較熟悉的遞推法入手，針對(duì)問(wèn)題描述中的不嚴(yán)謹(jǐn)之處，引入遞歸定義及其關(guān)鍵因素——遞歸結(jié)束條件和縮小問(wèn)題規(guī)模的遞歸處理。在遞歸的學(xué)習(xí)過(guò)程中，學(xué)生通過(guò)閱讀代碼、嘗試模仿、歸納提煉、拓展應(yīng)用等環(huán)節(jié)逐漸完成知識(shí)的內(nèi)化并達(dá)到應(yīng)用、遷移的目的。最后，學(xué)生通過(guò)實(shí)踐比較，體驗(yàn)遞推、遞歸兩種方法的運(yùn)行效率，并分析造成遞歸法運(yùn)行效率低下的原因，學(xué)會(huì)辯證地看待問(wèn)題，在應(yīng)用遞歸思想時(shí)逐漸形成一個(gè)意識(shí)——學(xué)習(xí)程序設(shè)計(jì)不僅僅是為了編程解決問(wèn)題，更重要的是形成正確的解決問(wèn)題的方法和態(tài)度。

教學(xué)過(guò)程

1.呈現(xiàn)問(wèn)題，初識(shí)遞歸

某電子購(gòu)物平臺(tái)在15周年慶之際特別推出了簽到送積分活動(dòng)?；顒?dòng)具體規(guī)則如下：從6月1日到6月15日，第1天、第2天簽到均可領(lǐng)取1個(gè)積分，第3天簽到可領(lǐng)取2個(gè)積分，第4天簽到可領(lǐng)取3個(gè)積分，第5天簽到可領(lǐng)取5個(gè)積分……請(qǐng)問(wèn)，小麗從6月1日起就堅(jiān)持每天簽到，那么，6月15日那天她將領(lǐng)到多少積分？你能找出這15天每天所領(lǐng)積分之間的關(guān)系嗎（如下頁(yè)圖1）？

觀察圖1，可以發(fā)現(xiàn)：第1天和第2天都只有1個(gè)積分，從第3天到第15天，每天領(lǐng)取的積分?jǐn)?shù)就進(jìn)入了一個(gè)重復(fù)的計(jì)算過(guò)程，即每天領(lǐng)取的積分是前兩天的積分之和。為了存放每天領(lǐng)取的積分?jǐn)?shù)，可以定義一個(gè)數(shù)組Fib（15），該數(shù)組中，F(xiàn)ib（1）=1，F(xiàn)ib（2）=1，而從第3天開(kāi)始的重復(fù)過(guò)程，可以利用循環(huán)來(lái)完成，代碼如下：

剛才計(jì)算的這一組數(shù)：1、1、2、3、5……是一個(gè)典型的斐波拉契數(shù)列，在解決這個(gè)問(wèn)題的過(guò)程中，借助數(shù)組，從已知條件出發(fā)，利用循環(huán)的方式按照一定規(guī)則從前往后遞推，最后得出了結(jié)論，這種解決問(wèn)題的方式稱之為遞推法。然而，在描述這組數(shù)時(shí)使用了“……”，在數(shù)學(xué)里經(jīng)?？吹竭@種寫法，實(shí)際上這種寫法并不科學(xué)，是數(shù)學(xué)表述中常見(jiàn)的不精確性。因?yàn)樗囊饬x依賴于人對(duì)省略號(hào)的理解和共識(shí)。所以，斐波拉契數(shù)列還可以這樣定義：

這種定義方式將問(wèn)題分成了兩種情況：一種是可以直接求出結(jié)果；另一種是把問(wèn)題分解成規(guī)模更小、與原問(wèn)題相同解法的小問(wèn)題。在用函數(shù)實(shí)現(xiàn)時(shí)，因?yàn)榻鉀Q大問(wèn)題的方法和解決小問(wèn)題的方法是同一個(gè)方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況，我們稱之為遞歸法。遞歸通常使用自定義函數(shù)的形式來(lái)實(shí)現(xiàn)。這樣，求斐波那契數(shù)列就變成了一件極簡(jiǎn)單的事情。

設(shè)計(jì)意圖：循環(huán)的方法并不會(huì)那么清晰地描述解決問(wèn)題的步驟，針對(duì)問(wèn)題描述中的不嚴(yán)謹(jǐn)之處，給出了一個(gè)較科學(xué)的定義。由斐波那契數(shù)列的定義引入遞歸的概念，并給出對(duì)應(yīng)的遞歸程序代碼，以便學(xué)生理解遞歸代碼并深刻感受遞歸法描述問(wèn)題的簡(jiǎn)潔、直白。

2.模仿嘗試，體驗(yàn)遞歸

活動(dòng)1：請(qǐng)大家模仿上例，分別完善程序，嘗試用遞歸法解決下面三個(gè)問(wèn)題。

（1）求階乘。階乘的遞歸定義如下：

（2）計(jì)算年齡：有5個(gè)人坐在一起，小華問(wèn)第5個(gè)人多少歲？他說(shuō)比第4個(gè)人大2歲。問(wèn)第4個(gè)人歲數(shù)，他說(shuō)比第3個(gè)人大2歲。問(wèn)第3個(gè)人，又說(shuō)比第2個(gè)人大2歲……一直問(wèn)到第1個(gè)人，他說(shuō)自己10歲。你能幫小華算出第5個(gè)人多少歲嗎？

遞歸定義：

（3）漢諾塔：如圖2所示，你能借助②號(hào)桿將①號(hào)桿上的盤子移動(dòng)到③號(hào)桿上而不改變盤子的次序嗎？最少移動(dòng)多少次？移動(dòng)規(guī)則：每次只能移動(dòng)一個(gè)盤子，大盤不能放置在小盤之上。

釋疑：可將n-1個(gè)盤子進(jìn)行捆綁，那么整個(gè)移動(dòng)過(guò)程便“簡(jiǎn)化”為“三步”：

a.將這n-1個(gè)盤子從①移動(dòng)到②，需要hanoi（n-1）次；

b.將剩下的最后一個(gè)大盤移動(dòng)到③，需要1次；

c.將②上的n-1個(gè)盤子移動(dòng)到③，又需要hanoi（n-1）次。

因此，可通過(guò)如下的遞歸定義來(lái)縮小問(wèn)題規(guī)模：

Private Function hanoi（ByVal n As Integer） As long

End Function

展示學(xué)生程序，調(diào)試運(yùn)行并分析其縮小問(wèn)題規(guī)模的遞歸處理辦法和遞歸結(jié)束條件，以及函數(shù)調(diào)用的方式。

設(shè)計(jì)意圖：以半成品代碼填空的方式，有目的地將代碼的核心部分留白，引導(dǎo)學(xué)生從不同角度進(jìn)行模仿，嘗試使用遞歸的方法解決問(wèn)題。

3.歸納提升，認(rèn)識(shí)遞歸

通過(guò)實(shí)踐，可以總結(jié)出遞歸實(shí)現(xiàn)的基本模式，如圖3所示（以斐波那契數(shù)列的遞歸程序?yàn)槔?/p>

小結(jié)：①遞歸法通過(guò)自定義函數(shù)來(lái)實(shí)現(xiàn)；②函數(shù)體內(nèi)通過(guò)分支來(lái)判斷是否滿足遞歸結(jié)束條件，不滿足則進(jìn)一步縮小規(guī)模，遞歸處理。

設(shè)計(jì)意圖：進(jìn)一步歸納總結(jié)，對(duì)所學(xué)知識(shí)進(jìn)行提煉，逐步形成遞歸解決問(wèn)題的基本模式。通過(guò)對(duì)具體的語(yǔ)言、算法中發(fā)現(xiàn)的解決問(wèn)題的規(guī)律進(jìn)行提煉，更有助于學(xué)生對(duì)知識(shí)進(jìn)行內(nèi)化，并能夠?qū)⒋艘?guī)律運(yùn)用于解決新的問(wèn)題，從而真正達(dá)到應(yīng)用、遷移的目的。

4.實(shí)例拓展，應(yīng)用遞歸

掌握了遞歸法解決問(wèn)題的一般格式，學(xué)會(huì)分析遞歸結(jié)束條件和縮小問(wèn)題規(guī)模的表達(dá)式后，再利用遞歸法來(lái)解決一些問(wèn)題。

活動(dòng)2：求兩個(gè)數(shù)的最大公約數(shù)。輾轉(zhuǎn)相除法，又名歐幾里德算法（Euclidean algorithm），是求兩個(gè)正整數(shù)的最大公約數(shù)的算法。設(shè)兩數(shù)為a、b（a>b），求a和b最大公約數(shù)gcd（a，b）的步驟如下：r1=a mod b（r1≥0）。如果r1=0，則gcd（a，b）=b；如果r1<>0，則r2=b mod r1（r2≥0）。如果r2=0，則gcd（a，b）=r1，若r2<>0，則繼續(xù)用r1除以r2，……如此重復(fù)求除數(shù)與余數(shù)的余數(shù)，直到能整除為止。

遞歸定義：

Private Function gcd（ByVal a As Integer，b as integer） As integer

End Function

提示學(xué)生分析遞歸結(jié)束條件和如何縮小問(wèn)題規(guī)模，注意遞歸函數(shù)的書寫形式。

設(shè)計(jì)意圖：學(xué)以致用，利用學(xué)生熟悉的數(shù)學(xué)問(wèn)題以降低學(xué)習(xí)的難度。活動(dòng)2與活動(dòng)1相比，其難點(diǎn)在于函數(shù)的參數(shù)變成了兩個(gè)，在學(xué)生分析問(wèn)題時(shí)教師應(yīng)當(dāng)給予適當(dāng)?shù)囊龑?dǎo)。

5.實(shí)驗(yàn)比較，再認(rèn)遞歸

活動(dòng)3：遞推法和遞歸法的實(shí)驗(yàn)比較。

（1）用遞推和遞歸分別求Fib數(shù)列的第15、25、35個(gè)數(shù)，測(cè)試大致運(yùn)行的時(shí)間，比較兩種算法的效率（如上表）。

（2）分析原因。以Fib（5）的計(jì)算情況為例，嘗試完成圖4所示的調(diào)用關(guān)系，直至遞歸結(jié)束。

通過(guò)這幅圖可以發(fā)現(xiàn)在程序運(yùn)行過(guò)程中存在著大量重復(fù)的函數(shù)調(diào)用，且參數(shù)越小，調(diào)用次數(shù)越多。正因?yàn)榇罅恐貜?fù)的調(diào)用，遞歸函數(shù)的使用相當(dāng)耗費(fèi)計(jì)算機(jī)資源，運(yùn)行效率較低。

遞歸法雖然運(yùn)行效率較低，但它的程序結(jié)構(gòu)清晰、易懂，是循環(huán)無(wú)法替代的。不僅如此，遞歸思想反映出的一種跳躍性的思維方法也為我們打開(kāi)了解決問(wèn)題的全新思路。遞歸思想啟迪我們要善于發(fā)現(xiàn)事物的整體與局部間的規(guī)律，學(xué)會(huì)從不同的視角去理解問(wèn)題的整體和局部。

在我們的學(xué)習(xí)、生活中也存在著很多遞歸思想的應(yīng)用。圖5所示的就是用遞歸法繪制的分形圖。

在生命科學(xué)中，當(dāng)以不同的放大倍數(shù)觀察小腸結(jié)構(gòu)時(shí)，從左到右較大的形態(tài)與較小的形態(tài)之間存在著自相似（如圖6）。

設(shè)計(jì)意圖：通過(guò)實(shí)踐對(duì)比，學(xué)生感悟到遞歸的運(yùn)行效率問(wèn)題及其運(yùn)行效率低下的原因。雖然遞歸運(yùn)行效率不高，但其跳躍性的思維方式、用簡(jiǎn)單模式解決復(fù)雜問(wèn)題的思想?yún)s廣泛地存在于程序設(shè)計(jì)乃至其他學(xué)科中。本環(huán)節(jié)實(shí)現(xiàn)了基礎(chǔ)知識(shí)到思想方法的提升。

點(diǎn) 評(píng)

長(zhǎng)期以來(lái)，我國(guó)中小學(xué)非常注重“雙基”教育，然而，隨著時(shí)代的發(fā)展和知識(shí)的激增，基礎(chǔ)知識(shí)和基本技能可能很快就會(huì)老化、過(guò)時(shí)，無(wú)法構(gòu)成學(xué)生未來(lái)發(fā)展的基礎(chǔ)。反之，學(xué)生在一門課程學(xué)習(xí)中形成的相對(duì)穩(wěn)定的思考問(wèn)題、解決問(wèn)題的思維方法和價(jià)值觀——學(xué)科思維，則會(huì)伴隨學(xué)生一生。起源于計(jì)算機(jī)科學(xué)的計(jì)算思維，不僅是運(yùn)用計(jì)算機(jī)科學(xué)的基礎(chǔ)概念求解問(wèn)題的方式，更是理解世界的方式，甚至是做事、探究、協(xié)作的方式，充分彰顯了基礎(chǔ)教育課程的基礎(chǔ)性特征，從而構(gòu)成了信息技術(shù)課程思想的完整體系。

作為計(jì)算思維的一種關(guān)鍵思想，遞歸首先是一種解決問(wèn)題的方式，其核心是按照一定的規(guī)則不斷縮小問(wèn)題規(guī)模直至遞歸結(jié)束條件出現(xiàn)，關(guān)鍵是要從整體上把握，通過(guò)“遞”把主問(wèn)題分解成子問(wèn)題，而“歸”就是利用子問(wèn)題的解逐步向上求解，根據(jù)這樣的思路可以利用相對(duì)簡(jiǎn)單的方法來(lái)解決復(fù)雜的問(wèn)題。本節(jié)課教師十分注重引導(dǎo)學(xué)生構(gòu)造問(wèn)題的遞歸定義，尋找到了遞歸定義，基本上就可以直接翻譯成程序了。求斐波那契數(shù)列、階乘和漢諾塔三個(gè)問(wèn)題，由教師直接給出遞歸定義，而求最大公約數(shù)則在算法分析的基礎(chǔ)上引導(dǎo)學(xué)生自主嘗試定義遞歸，進(jìn)而拓展到分形圖的繪制。生命科學(xué)中具有分形特征的小腸結(jié)構(gòu)，引導(dǎo)學(xué)生運(yùn)用遞歸思想發(fā)現(xiàn)事物的整體與局部間的規(guī)律，體會(huì)遞歸思想在社會(huì)意義和教育意義上的普遍價(jià)值。

另外，程序設(shè)計(jì)具有強(qiáng)烈的工程屬性，對(duì)同一問(wèn)題常會(huì)得到許多合理而正確的不同程序。在尋找可能的解決方案時(shí)，需要對(duì)各種方案作出評(píng)價(jià)和選擇，對(duì)所做選擇的優(yōu)點(diǎn)和缺點(diǎn)應(yīng)有清醒認(rèn)識(shí)。這一點(diǎn)在遞歸程序設(shè)計(jì)中體現(xiàn)得尤為明顯，遞歸描述的程序很容易閱讀和理解，卻也有一個(gè)很大的缺陷——其中可能存在著大量的重復(fù)計(jì)算。許多學(xué)生可能認(rèn)為，今天的計(jì)算機(jī)這么快，多算幾次花不了多少時(shí)間，本節(jié)課通過(guò)試驗(yàn)，對(duì)比遞推法和遞歸法計(jì)算不同數(shù)值斐波那契數(shù)列所耗費(fèi)的時(shí)間，提高了學(xué)生對(duì)計(jì)算“復(fù)雜性”的認(rèn)識(shí)。

當(dāng)前，程序設(shè)計(jì)教學(xué)中“個(gè)性化”方法比較嚴(yán)重，同一個(gè)算法在不同問(wèn)題中的描述往往是不同的，學(xué)生即使編寫了“大量”的程序，也無(wú)法遷移到相似問(wèn)題的解決過(guò)程之中。本節(jié)課，教師通過(guò)對(duì)多個(gè)個(gè)別程序的歸納，形成遞歸解決問(wèn)題的基本模式，并推廣到更廣泛的問(wèn)題解決與應(yīng)用中，這種基于模式建構(gòu)的程序設(shè)計(jì)學(xué)習(xí)有助于學(xué)生建立良好的程序設(shè)計(jì)思維和方法，也有助于學(xué)生對(duì)知識(shí)進(jìn)行內(nèi)化。