1、遞歸算法與遞歸程序岳西中學:崔世義一、教學目標1、知識與技能(1)認識遞歸現象。(2)使用遞歸算法解決問題往往能使算法的描述乘法而易于表達(3)理解遞歸三要素：每次遞歸調用都要縮小規模；前次遞歸調用為后次作準備：遞歸調用必須有條件進行。(4)認識遞歸算法往往不是高效的算法。(5)了解遞歸現象的規律。(6)能夠設計遞歸程序解決適用于遞歸解決的問題。(7)能夠根據算法寫出遞歸程序。(8)了解生活中的遞歸現象，領悟遞歸現象的既有重復，又有變化的特點，并且從中學習解決問題的一種方法。2、方法與過程本節讓同學們玩漢諾塔的游戲，導入遞歸問題，從用普通程序解決斐波那契的兔子問題入手，引導學生用自定義了一個以

2、遞歸方式解決的函數過程解決問題，同時讓同學們做三個遞歸練習，穩固提高。然后讓學生做練習(2)和練習(3)這兩道題目的形式相差很遠，但方法和答案卻是完全相同的練習，體會其中的微妙，加深對遞歸算法的了解。最后用子過程解決漢諾塔的經典問題。3、情感態度和價值觀結合高中生想象具有較強的隨意性、更富于現實性的身心開展特點，綜合反映出遞歸算法的特點，以及遞歸算法解答某些實踐問題通常得很簡潔，從而激發學生對程序設計的追求和向往。二、重點難點1、教學重點1了解遞歸現象和遞歸算法的特點。2能夠根據問題設計出恰當的遞歸程序。2、教學難點(1)遞歸過程思路的建立。(2)判斷問題是否適于遞歸解法。(3)正確寫出遞歸程

3、序。三、教學環境1、教材處理教材選自?浙江省普通高中信息技術選修：算法與程序設計?第五章，原教材的編排是以本節以斐波那契的兔子問題引人，導出遞歸算法，從而自定義了一個以遞歸方式解決的函數過程。然后利用子過程解決漢諾塔的經典問題。教材經處理后，讓同學們玩漢諾塔的游戲，導入遞歸問題，從用普通程序解決斐波那契的兔子問題入手，引導學生用自定義了一個以遞歸方式解決的函數過程解決問題，同時讓同學們做三個遞歸練習，穩固提高。然后讓學生做練習(2)和練習(3)這兩道題目的形式相差很遠，但方法和答案卻都是完全相同的練習，體會其中的微妙，加深對遞歸算法的了解。最后用子過程解決漢諾塔的經典問題。教學方法采用講解、探

4、究、任務驅動和學生自主學習相結合2、預備知識學生已掌握了用計算機解決問題的過程，掌握了程序設計根底，掌握了解析法、窮舉法、查找法、排序法設計程序的技巧。 四、       教學過程導入：大家玩漢諾塔游戲： 這個游戲盤子在A、B、C三根柱子上不停運動，有沒有規律，和你在照過鏡子時遇到的情況相同嗎？當你往鏡子前面一站，鏡子里面就有一個你的像。但你試過兩面鏡子一起照嗎?如果甲、乙兩面鏡子相互面對面放著，你往中間一站，嘿，兩面鏡子里都有你的千百個“化身!為什么會有這么奇妙的現象呢?原來，甲鏡子里有乙鏡子的像，乙鏡子里也有甲

5、鏡子的像，而且這樣反反復復，就會產生一連串的“像中像。這是一種遞歸現象。由同學們總結出遞歸算法的概念遞歸算法：是一種直接或者間接地調用自身的算法。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。問題4-16：著名的意大利數學家斐波那契(Fibonacci)在他的著作?算盤書?中提出了一個“兔子問題：假定小兔子一個月就可以長成大兔子，而大兔子每個月都會生出一對小兔子。如果年初養了一對小兔子，問到年底時將有多少對兔子?  (當然得假設兔子沒有死亡而且嚴格按照上述規律長大與繁殖)我們不難用以前學過的知識設計出如下算法：輸入計算兔子的月份數：nI

6、f n < 3 Then c = 1 Else a = 1: b = 1i = 3c = a + b：a = b：b = ci=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&

7、#160; Text2.Text = "第" & n & "月的兔子數目是：" & cEnd Sub 開動腦筋：我們有沒有更簡單的方法解決該問題呢？ 4.5.1  從斐波那契的兔子問題看遞歸算法1斐波那契的兔子問題子 (1)分析問題。我們可以根據題意列出表4-3來解決這個問題：表43兔子問題分析表  1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合計1123581321345589144這個表格雖然解決了

8、斐波那契的兔子問題(年底時兔子的總數是144只)，但仔細觀察一下這個表格，你會發現兔子的數目增長得越來越快，如果時間再長，只用列表的方法就會有困難。(例如，你愿意用列表的方法求出5年后兔子的數目嗎？)我們需要研究表中的規律，找出一般的方法，去解決這個問題。交流仔細研究表4-8，你有些什么發現？每一個月份的大兔數、小兔數與上一個月的數字有什么聯系，能肯定這個規律嗎？恭喜你，你快成功了？(2)設計算法。“兔子問題很容易列出一條遞推式而得到解決。假設第N個月的兔子數目是F(N)，我們有：這是因為每月的大兔子數目一定等于上月的兔子總數，而每個月的小兔子數目一定等于上月的大兔子數目(即前一個月的兔子的數

9、目)。由上述的遞推式我們可以設計出遞歸程序。遞歸程序的特點是獨立寫出一個函數(或子過程)，而這個函數只對極簡單的幾種情況直接給出解答，而在其余情況下通過反復的調用自身而把問題歸結到最簡單的情況而得到解答。前面學過：自定義函數的定義格式:Function 函數名(參數表  ) As type過程中的代碼End Function調用函數的格式：函數名(參數表) (3)編寫程序。窗體中開設一個文本框Textl用于填人月數N，設置命令框Commandl，點擊它即執行程序求出第N月的兔子數。然后用文本框Text2輸出答案。根據遞推式可以寫出遞歸程序如下：  Function

10、 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)調試程序因為這個算

11、法的效率不高，建議在調試程序時月份數不要大于40。4.5.2  一個應用遞歸算法解決的問題經典例子問題4-17：傳說在古代印度的貝拿勒斯神廟，有一塊黃銅板上插了3根寶石柱，在其中一根寶石柱自上而下由小到大地疊放著64個大小不等的金盤。一名僧人把這些金盤從一根寶石柱移到另外一根上。僧人在移動金盤時遵守下面3條規那么：第一，一次只能移動一個金盤。第二，每個金盤只能由一根寶石柱移到另外一根寶石柱。第三，任何時候都不能把大的金盤放在小的金盤上。神話說，如果僧人把64個金盤完全地從一根寶石移到了另外一根上，世界的末日就要到了。當然，神話只能當故事來聽，世界不可以因為個別人的活動而導致

12、末日。不過，從僧人搬完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就可以了。靠遞歸的思想，我們輕而易舉地完成了整個搬動。(2)設計算法。我們定義一個過程Hanoi(N，A，B，C)，表示有N個金盤需要從A

13、柱搬到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 過程名 (參數表)代碼End Sub調用過程的格式：Call過程名(參數表) (3)編寫程序引導學生編寫程序。Private Sub Hanoi(n As Integer, ByVal A As String, ByVal B As String, ByV

14、al 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 S

15、ub 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。 小結：遞歸算法的特點遞歸過程一般通過函數或子過程來實現。遞歸算法：在函數或子過程的內部，直接或者間接地調用自己的算法。遞歸算法的實質：是把問題轉化為規模縮小了的同類問題的子問題。然后遞歸調用函數(或過程)來表示問題的解。遞歸算法解決問題的特點：(1)遞歸就是在過程或函數里調用自身。(2)在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。(3)遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程序。(4)在遞歸調用的過程當中系統為每一層的返回點、局