《用遞歸法解決問題》教學設計

龐霞+曹恒來

學習者分析

本節課的教學對象為高中二年級的學生。這個階段的學生具有很強的自主意識，具備一定的探究能力，喜歡自己動手實踐來獲得新知。多次經歷從問題到程序的思考過程，在面對現有軟件無法解決的問題時能夠編寫程序解決問題。在此之前，學生已經掌握了循環、數組、自定義函數的使用，為本課的學習做好了充分的準備。

學習內容分析

《用遞歸法解決問題》是高中選修教材《算法與程序設計》（科教版）第三章“算法的程序實現”第五小節的內容。在本課學習之前，學生已經學會了用循環的方法來解決問題，然而循環的方法往往并不會那么清晰地描述解決問題的步驟，遞歸法則可以非常直白地描述一個問題的求解過程，因此遞歸法也是最容易實現的算法。

遞歸的基本思想是把規模大的問題轉化為規模小的相類似的子問題來解決。在函數實現時，因為解決大問題的方法和解決小問題的方法往往是同一種方法，所以就產生了調用自身的情況。遞歸是利用系統的堆棧保存函數中的局部變量來解決問題的，因為函數調用的開銷比較大，遞歸常常會帶來效率問題。本節課學生不僅要學會用遞歸法解決問題，更重要的是領會遞歸思想的精髓。遞歸思想是計算機學科中的核心技術思想之一，其本質反映的是一種將復雜問題簡單化的思維方法。

學習目標

知識與技能目標：理解遞歸的含義，找出遞歸問題中縮小問題規模的遞歸處理方法及遞歸結束條件，了解遞歸算法的優缺點。

過程與方法目標：能用程序實現遞歸算法，學會用簡單模式解決復雜問題的方法。

情感態度與價值觀目標：領悟遞歸思想，體驗遞歸思想在實際生活中的應用。

教學重點、難點

重點：分析遞歸結束條件及縮小問題規模的方法，以及遞歸算法的程序實現。

難點：遞歸算法的程序實現。

教學策略

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

教學過程

1.呈現問題，初識遞歸

某電子購物平臺在15周年慶之際特別推出了簽到送積分活動?；顒泳唧w規則如下：從6月1日到6月15日，第1天、第2天簽到均可領取1個積分，第3天簽到可領取2個積分，第4天簽到可領取3個積分，第5天簽到可領取5個積分……請問，小麗從6月1日起就堅持每天簽到，那么，6月15日那天她將領到多少積分？你能找出這15天每天所領積分之間的關系嗎（如下頁圖1）？

觀察圖1，可以發現：第1天和第2天都只有1個積分，從第3天到第15天，每天領取的積分數就進入了一個重復的計算過程，即每天領取的積分是前兩天的積分之和。為了存放每天領取的積分數，可以定義一個數組Fib（15），該數組中，Fib（1）=1，Fib（2）=1，而從第3天開始的重復過程，可以利用循環來完成，代碼如下：

剛才計算的這一組數：1、1、2、3、5……是一個典型的斐波拉契數列，在解決這個問題的過程中，借助數組，從已知條件出發，利用循環的方式按照一定規則從前往后遞推，最后得出了結論，這種解決問題的方式稱之為遞推法。然而，在描述這組數時使用了“……”，在數學里經?？吹竭@種寫法，實際上這種寫法并不科學，是數學表述中常見的不精確性。因為它的意義依賴于人對省略號的理解和共識。所以，斐波拉契數列還可以這樣定義：

這種定義方式將問題分成了兩種情況：一種是可以直接求出結果；另一種是把問題分解成規模更小、與原問題相同解法的小問題。在用函數實現時，因為解決大問題的方法和解決小問題的方法是同一個方法，所以就產生了函數調用它自身的情況，我們稱之為遞歸法。遞歸通常使用自定義函數的形式來實現。這樣，求斐波那契數列就變成了一件極簡單的事情。

設計意圖：循環的方法并不會那么清晰地描述解決問題的步驟，針對問題描述中的不嚴謹之處，給出了一個較科學的定義。由斐波那契數列的定義引入遞歸的概念，并給出對應的遞歸程序代碼，以便學生理解遞歸代碼并深刻感受遞歸法描述問題的簡潔、直白。

2.模仿嘗試，體驗遞歸

活動1：請大家模仿上例，分別完善程序，嘗試用遞歸法解決下面三個問題。

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

（2）計算年齡：有5個人坐在一起，小華問第5個人多少歲？他說比第4個人大2歲。問第4個人歲數，他說比第3個人大2歲。問第3個人，又說比第2個人大2歲……一直問到第1個人，他說自己10歲。你能幫小華算出第5個人多少歲嗎？

遞歸定義：

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

釋疑：可將n-1個盤子進行捆綁，那么整個移動過程便“簡化”為“三步”：

a.將這n-1個盤子從①移動到②，需要hanoi（n-1）次；

b.將剩下的最后一個大盤移動到③，需要1次；

c.將②上的n-1個盤子移動到③，又需要hanoi（n-1）次。

因此，可通過如下的遞歸定義來縮小問題規模：

Private Function hanoi（ByVal n As Integer） As long

End Function

展示學生程序，調試運行并分析其縮小問題規模的遞歸處理辦法和遞歸結束條件，以及函數調用的方式。

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

3.歸納提升，認識遞歸

通過實踐，可以總結出遞歸實現的基本模式，如圖3所示（以斐波那契數列的遞歸程序為例）。

小結：①遞歸法通過自定義函數來實現；②函數體內通過分支來判斷是否滿足遞歸結束條件，不滿足則進一步縮小規模，遞歸處理。

設計意圖：進一步歸納總結，對所學知識進行提煉，逐步形成遞歸解決問題的基本模式。通過對具體的語言、算法中發現的解決問題的規律進行提煉，更有助于學生對知識進行內化，并能夠將此規律運用于解決新的問題，從而真正達到應用、遷移的目的。

4.實例拓展，應用遞歸

掌握了遞歸法解決問題的一般格式，學會分析遞歸結束條件和縮小問題規模的表達式后，再利用遞歸法來解決一些問題。

活動2：求兩個數的最大公約數。輾轉相除法，又名歐幾里德算法（Euclidean algorithm），是求兩個正整數的最大公約數的算法。設兩數為a、b（a>b），求a和b最大公約數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，則繼續用r1除以r2，……如此重復求除數與余數的余數，直到能整除為止。

遞歸定義：

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

End Function

提示學生分析遞歸結束條件和如何縮小問題規模，注意遞歸函數的書寫形式。

設計意圖：學以致用，利用學生熟悉的數學問題以降低學習的難度?；顒?與活動1相比，其難點在于函數的參數變成了兩個，在學生分析問題時教師應當給予適當的引導。

5.實驗比較，再認遞歸

活動3：遞推法和遞歸法的實驗比較。

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

（2）分析原因。以Fib（5）的計算情況為例，嘗試完成圖4所示的調用關系，直至遞歸結束。

通過這幅圖可以發現在程序運行過程中存在著大量重復的函數調用，且參數越小，調用次數越多。正因為大量重復的調用，遞歸函數的使用相當耗費計算機資源，運行效率較低。

遞歸法雖然運行效率較低，但它的程序結構清晰、易懂，是循環無法替代的。不僅如此，遞歸思想反映出的一種跳躍性的思維方法也為我們打開了解決問題的全新思路。遞歸思想啟迪我們要善于發現事物的整體與局部間的規律，學會從不同的視角去理解問題的整體和局部。

在我們的學習、生活中也存在著很多遞歸思想的應用。圖5所示的就是用遞歸法繪制的分形圖。

在生命科學中，當以不同的放大倍數觀察小腸結構時，從左到右較大的形態與較小的形態之間存在著自相似（如圖6）。

設計意圖：通過實踐對比，學生感悟到遞歸的運行效率問題及其運行效率低下的原因。雖然遞歸運行效率不高，但其跳躍性的思維方式、用簡單模式解決復雜問題的思想卻廣泛地存在于程序設計乃至其他學科中。本環節實現了基礎知識到思想方法的提升。

點 評

長期以來，我國中小學非常注重“雙基”教育，然而，隨著時代的發展和知識的激增，基礎知識和基本技能可能很快就會老化、過時，無法構成學生未來發展的基礎。反之，學生在一門課程學習中形成的相對穩定的思考問題、解決問題的思維方法和價值觀——學科思維，則會伴隨學生一生。起源于計算機科學的計算思維，不僅是運用計算機科學的基礎概念求解問題的方式，更是理解世界的方式，甚至是做事、探究、協作的方式，充分彰顯了基礎教育課程的基礎性特征，從而構成了信息技術課程思想的完整體系。

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

另外，程序設計具有強烈的工程屬性，對同一問題常會得到許多合理而正確的不同程序。在尋找可能的解決方案時，需要對各種方案作出評價和選擇，對所做選擇的優點和缺點應有清醒認識。這一點在遞歸程序設計中體現得尤為明顯，遞歸描述的程序很容易閱讀和理解，卻也有一個很大的缺陷——其中可能存在著大量的重復計算。許多學生可能認為，今天的計算機這么快，多算幾次花不了多少時間，本節課通過試驗，對比遞推法和遞歸法計算不同數值斐波那契數列所耗費的時間，提高了學生對計算“復雜性”的認識。

當前，程序設計教學中“個性化”方法比較嚴重，同一個算法在不同問題中的描述往往是不同的，學生即使編寫了“大量”的程序，也無法遷移到相似問題的解決過程之中。本節課，教師通過對多個個別程序的歸納，形成遞歸解決問題的基本模式，并推廣到更廣泛的問題解決與應用中，這種基于模式建構的程序設計學習有助于學生建立良好的程序設計思維和方法，也有助于學生對知識進行內化。