一、 教學目標1、 知識與技能(1)認識遞歸現象。(2)使用遞歸算法解決問題往往能使算法的描述乘法而易于表達(3)理解遞歸三要素：每次遞歸調用都要縮小規模；前次遞歸調用為后次作準備：遞歸調用必須有條件進行。(4)認識遞歸算法往往不是高效的算法。(5)了解遞歸現象的規律。(6)能夠設計遞歸程序解決適用于遞歸解決的問題。(7)能夠根據算法寫出遞歸程序。(8)了解生活中的遞歸現象，領悟遞歸現象的既有重復，又有變化的特點，并且從中學習解決問題的一種方法。2、 方法與過程本節讓同學們玩漢諾塔的游戲，導入遞歸問題，從用普通程序解決斐波那契的兔子問題入手，引導學生用自定義了一個以遞歸方式解決的函數過程解決問題，同時讓同學們做三個遞歸練習，鞏固提高。然后讓學生做練習(2)和練習(3)這兩道題目的形式相差很遠，但方法和答案卻是完全相同的練習，體會其中的奧妙，加深對遞歸算法的了解。最后用子過程解決漢諾塔的經典問題。3、 情感態度和價值觀結合高中生想象具有較強的隨意性、更富于現實性的身心發展特點，綜合反映出遞歸算法的特點，以及遞歸算法解答某些實踐問題通常得很簡潔，從而激發學生對程序設計的追求和向往。二、 重點難點1、 教學重點（1） 了解遞歸現象和遞歸算法的特點。（2） 能夠根據問題設計出恰當的遞歸程序。2、 教學難點(1)遞歸過程思路的建立。(2)判斷問題是否適于遞歸解法。(3)正確寫出遞歸程序。三、 教學環境1、 教材處理教材選自廣東省普通高中信息技術選修一：算法與程序設計第四章第五節，原教材的編排是以本節以斐波那契的兔子問題引人，導出遞歸算法，從而自定義了一個以遞歸方式解決的函數過程。然后利用子過程解決漢諾塔的經典問題。教材經處理后，讓同學們玩漢諾塔的游戲，導入遞歸問題，從用普通程序解決斐波那契的兔子問題入手，引導學生用自定義了一個以遞歸方式解決的函數過程解決問題，同時讓同學們做三個遞歸練習，鞏固提高。然后讓學生做練習(2)和練習(3)這兩道題目的形式相差很遠，但方法和答案卻都是完全相同的練習，體會其中的奧妙，加深對遞歸算法的了解。最后用子過程解決漢諾塔的經典問題。教學方法采用講解、探究、任務驅動和學生自主學習相結合2、 預備知識學生已掌握了用計算機解決問題的過程，掌握了程序設計基礎，掌握了解析法、窮舉法、查找法、排序法設計程序的技巧。3、 硬件要求建議本節課在多媒體電腦教室中完成，最好有廣播教學系統或投影儀，為拓展學習，學生機應允許上互聯網。4、 所需軟件學生機要安裝VB6.0或以上版本。5、 所需課時2課時（90分鐘）四、 教學過程導入：大家玩漢諾塔游戲： 圖4-5(1)漢諾塔游戲的部分界面這個游戲盤子在A、B、C三根柱子上不停運動，有沒有規律，和你在照過鏡子時遇到的情況相同嗎？當你往鏡子前面一站，鏡子里面就有一個你的像。但你試過兩面鏡子一起照嗎?如果甲、乙兩面鏡子相互面對面放著，你往中間一站，嘿，兩面鏡子里都有你的千百個“化身”!為什么會有這么奇妙的現象呢?原來，甲鏡子里有乙鏡子的像，乙鏡子里也有甲鏡子的像，而且這樣反反復復，就會產生一連串的“像中像”。這是一種遞歸現象。由同學們總結出遞歸算法的概念遞歸算法：是一種直接或者間接地調用自身的算法。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。問題4-16：著名的意大利數學家斐波那契(Fibonacci)在他的著作算盤書中提出了一個“兔子問題”：假定小兔子一個月就可以長成大兔子，而大兔子每個月都會生出一對小兔子。如果年初養了一對小兔子，問到年底時將有多少對兔子? (當然得假設兔子沒有死亡而且嚴格按照上述規律長大與繁殖)我們不難用以前學過的知識設計出如下算法： 輸入計算兔子的月份數：n If n 3 Then c = 1 Else a = 1: b = 1 i = 3 c = a + b：a = b：b = c i=i+1,如果in則返回 結束參考程序如下：Private Sub Command1_Click() n = Val(Text1.Text) If n 3 Then c = 1 Else a = 1: b = 1 For i = 3 To n c = a + b a = b b = c Next i Text2.Text = 第 & n & 月的兔子數目是： & cEnd Sub圖4-5(2)斐波那契兔子程序運行結果圖開動腦筋：我們有沒有更簡單的方法解決該問題呢？4.5.1 從斐波那契的兔子問題看遞歸算法1斐波那契的兔子問題子 (1)分析問題。我們可以根據題意列出表4-3來解決這個問題：表43兔子問題分析表1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合計1123581321345589144這個表格雖然解決了斐波那契的兔子問題(年底時兔子的總數是144只)，但仔細觀察一下這個表格，你會發現兔子的數目增長得越來越快，如果時間再長，只用列表的方法就會有困難。(例如，你愿意用列表的方法求出5年后兔子的數目嗎？)我們需要研究表中的規律，找出一般的方法，去解決這個問題。交流仔細研究表4-8，你有些什么發現？每一個月份的大兔數、小兔數與上一個月的數字有什么聯系，能肯定這個規律嗎？恭喜你，你快成功了？(2)設計算法。“兔子問題”很容易列出一條遞推式而得到解決。假設第N個月的兔子數目是F(N)，我們有：這是因為每月的大兔子數目一定等于上月的兔子總數，而每個月的小兔子數目一定等于上月的大兔子數目(即前一個月的兔子的數目)。由上述的遞推式我們可以設計出遞歸程序。遞歸程序的特點是獨立寫出一個函數(或子過程)，而這個函數只對極簡單的幾種情況直接給出解答，而在其余情況下通過反復的調用自身而把問題歸結到最簡單的情況而得到解答。空中加油站：自定義函數的定義格式:Function procedurename(arguments) As typeStatementsEnd Function其中的procedurename是函數名，arguments是函數中的參數表，type是函數返回值的數據類型，表示可有可無的部分，statements是過程中的代碼調用函數的格式：procedurename(arguments)(3)編寫程序。窗體中開設一個文本框Textl用于填人月數N，設置命令框Commandl，點擊它即執行程序求出第N月的兔子數。然后用文本框Text2輸出答案。 文本框2 根據遞推式可以寫出遞歸程序如下： Function Fib(ByVal N As Integer) As Long If N 3 Then Fib = 1 Else Fib = Fib(N - 1) + Fib(N - 2)End FunctionPrivate Sub Command1_Click() N = Val(Text1.Text) Text2.Text = 第 & N & 月的兔子數目是： & Fib(N)End Sub(4)調試程序因為這個算法的效率不高，建議在調試程序時月份數不要大于40。圖4-5(4)斐波那契兔子程序運行結果圖(5)檢測結果挑戰自我：（以下部分由學生自己完成）(1)利用遞歸方法編寫一求N的階乘。分析：根據N!=N*(N-1)*(N-2)*(N-3)*3*2*1可以推出下列式子：這是一個典型的遞歸算法，參考程序如下：Function F(ByVal n As Integer) As Long If n = 1 Then F = 1 Else F = n * F(n - 1)End FunctionPrivate Sub Form_Click() Dim n As Integer n = Val(InputBox(請輸入正整數N：, 求N的階乘) Print 輸入的正整數是; n; Print ，階乘是; F(n)End Sub圖4-5(5)求階乘程序的運行結果圖(2)對一正整數N，用數字l和2組成一條加法算式，使其和為N，共可以列出多少條不同的式子？(“l+2”和“2+1”看作是不同的式子)。算法設計：假設和為N時可列式子的方法數是F(N)，那么第一個加數可選擇1或2。當第一個加數為1時剩下加數的和為N一1，故方法數為F(N一1)；當第一個加數為2時，剩下加數的和為N-2，故方法數為F(N-2)。于是可以得到如下式子：這是一個典型的遞歸算法，參考程序如下：參考程序如下：Function F(ByVal n As Integer) As Long If n = 2 Then F = n Else F = F(n - 1) + F(n - 2)End FunctionPrivate Sub Form_Click() Dim n As Integer n = Val(InputBox(請輸入正整數N：, 輸入式子的總和) Print 當總和是; n; 時 Print 可以列出不同的由1和2組成的加法式子; F(n); 條End Sub圖4-5(6)書上P137練習2程序運行結果圖(3)羅光明在上樓梯時，有時一步一級樓梯，有時一步兩級。如果樓梯有N級，他上完這N級樓梯有多少種不同的方法？設計算法假設樓梯級數為N時的方法數是F(N)，那么第一步可選擇1或2級樓梯。當第一步為1級時剩下樓梯的級數為N-1，故方法數為F(N-1)；當第一步為2級時，剩下樓梯的級數為N-2，故方法數為F(N-2)。于是可以得到如下式子：這是一個典型的遞歸算法，參考程序如下：程序如下：Function F(ByVal n As Integer)As Long If n=2 Then F=n Else F=F(n-1)+F(n-2)End Functi 0nPrivate Sub Form_Click() Dim n As Integer n=Val(InputBox(請輸入樓梯級數N：，輸人樓梯級數) Print 當樓梯級數；n；時， Print 可以有；F(n)；種不同的上樓梯方法。End Sub同學們比較一下你們所做的練習(2)和(3)的程序代碼，不知同學們有沒有發現一個有趣的現象？為什么會這樣？本節小結：遞歸算法的特點遞歸過程一般通過函數或子過程來實現。遞歸算法：在函數或子過程的內部，直接或者間接地調用自己的算法。遞歸算法的實質：是把問題轉化為規?？s小了的同類問題的子問題。然后遞歸調用函數(或過程)來表示問題的解。遞歸算法解決問題的特點：(1) 遞歸就是在過程或函數里調用自身。(2) 在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。(3) 遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程序。(4) 在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。所以一般不提倡用遞歸算法設計程序。遞歸算法所體現的“重復”一般有三個要求：一是每次調用在規模上都有所縮小(通常是減半)；二是相鄰兩次重復之間有緊密的聯系，前一次要為后一次做準備(通常前一次的輸出就作為后一次的輸入)；三是在問題的規模極小時必須用直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的(以規模未達到直接解答的大小為條件)，無條件遞歸調用將會成為死循環而不能正常結束。第二課時：導入：大家玩漢諾塔游戲：圖4-5(7)漢諾塔程序運行界面圖4.5.2 一個應用遞歸算法解決的問題經典例子問題4-17：傳說在古代印度的貝拿勒斯神廟，有一塊黃銅板上插了3根寶石柱，在其中一根寶石柱自上而下由小到大地疊放著64個大小不等的金盤。一名僧人把這些金盤從一根寶石柱移到另外一根上。僧人在移動金盤時遵守下面3條規則：第一，一次只能移動一個金盤。第二，每個金盤只能由一根寶石柱移到另外一根寶石柱。第三，任何時候都不能把大的金盤放在小的金盤上。神話說，如果僧人把64個金盤完全地從一根寶石移到了另外一根上，世界的末日就要到了。當然，神話只能當故事來聽，世界不可以因為個別人的活動而導致末日。不過，從僧人搬完64個金盤所需時間的角度來說，即使僧人每秒都能移動一個金盤，那也得要幾千億年！試設計程序，模擬移動金盤的過程。(1)分析問題。我們把3根寶石柱分別命名為A、B、C。最初有N個金盤放在A，需要把它們全部按規則移動到B。當N=1時，直接把金盤從A搬到B就可以了，1次成功。當N2，那么需要利用C柱來過渡。我們假設已經找到一種把N1個金盤從一根柱搬到另外一根柱的方法，那么，我們只要把N1個金盤從A搬到C，然后把最大的金盤從A搬到B，最后把C上的N一1個金盤搬到B就可以了?？窟f歸的思想，我們輕而易舉地完成了整個搬動。(2)設計算法。我們定義一個過程Hanoi(N，A，B，C)，表示有N個金盤需要從A柱搬到B柱(以C柱為過渡)。那么完成它只需3步： Hanoi(N一1，A，C，B)它的意思是把A柱上的N一1個金盤搬到C柱； AB 它的意思是把一個(最大的)金盤從A柱搬到B柱； Hanoi(N1，C，B，A)它的意思是把c柱上的N一1個金盤搬到B柱?？罩屑佑驼荆哼^程定義的格式：Private Sub procedurename(arguments)statementsEnd Sub其中的procedurename是函數名，arguments是函數中的參數表，statements是過程中的代碼調用過程的格式：Call procedurename(arguments)Function函數與Sub過程的幾點區別： Function函數可以返回一個值到調用程序。 一般來說，讓較大的語句或表達式的右邊包含函數過程名和參數（returnvalue=function），這就調用了函數。 與變量完全一樣，函數過程有數據類型，這就決定了返回值的類型。（如果沒有AS子句，缺省的數據類型為Variant。）。 給procedurename自身賦一個值，就可返回這個值。Function函數返回一個值可成為較大表達式的一部分。(3)編寫程序（引導學生編寫程序）。根據所設計的算法，我們安排窗體如圖4-23： Private Sub Hanoi(n As Integer, ByVal A As String, ByVal B As String, ByVal C As String, t As Long)If n = 1 Then Text3.Text = Text3.Text + A + + B + vbCrLft = t + 1 增加變量t用來統計移動次數。Else Call Hanoi(n - 1, A, C, B, t) Text3.Text = Text3.Text + A + + B + vbCrLf t = t + 1 Call Hanoi(n - 1, C, B, A, t)End IfEnd SubPrivate Sub Command1_Click() Dim t As Long, n As Integer t = 0 n = Val(Text1.Text) A = A B = B C = C Call Hanoi(n, A, B, C, t) Text2.Text = tEnd Sub(4)測試程序在“金葉數目”的文本框中輸入4。圖4-5(9)Hanoi結果示意圖(5)檢測結果挑戰自我：（以下部分由學生自己完成）如來不用遞歸，可不可以用其它的解決