遞歸算法與遞歸程序教學(xué)設(shè)計(jì)

1、遞歸算法與遞歸程序岳西中學(xué)：崔世義一、教學(xué)目標(biāo)1知識(shí)與技能(1) 認(rèn)識(shí)遞歸現(xiàn)象。(2) 使用遞歸算法解決冋題往往能使算法的描述乘法而易于表達(dá)(3) 理解遞歸三要素：每次遞歸調(diào)用都要縮小規(guī)模；前次 遞歸調(diào)用為后次 作準(zhǔn)備：遞歸調(diào)用必須有條件進(jìn)行。(4) 認(rèn)識(shí)遞歸算法往往不是咼效的算法。(5) 了解遞歸現(xiàn)象的規(guī)律。(6) 能夠設(shè)計(jì)遞歸程序解決適用于遞歸解決的問題。(7) 能夠根據(jù)算法寫出遞歸程序。(8) 了解生活中的遞歸現(xiàn)象，領(lǐng)悟遞歸現(xiàn)象的既有重復(fù)，又有變化的特點(diǎn)， 并且從中學(xué)習(xí)解決問題的一種方法。2、方法與過程本節(jié)讓同學(xué)們玩漢諾塔的游戲，導(dǎo)入 遞歸問題，從用普通程序解決斐波 那契的兔子問題入手，

2、引導(dǎo)學(xué)生用自定義了一個(gè)以 遞歸方式解決的函數(shù)過程 解決問題，同時(shí)讓同學(xué)們做三個(gè) 遞歸練習(xí)，鞏固提高。然后讓學(xué)生做練習(xí)(2) 和練習(xí)(3)這兩道題目的形式相差很遠(yuǎn)，但方法和答案卻是完全相同的練習(xí)， 體會(huì)其中的奧妙，加深對(duì) 遞歸算法的了解。最后用子過程解決漢諾塔的經(jīng)典 問題。3、情感態(tài)度和價(jià)值觀結(jié)合高中生想象具有較強(qiáng)的隨意性、更富于現(xiàn)實(shí)性的身心發(fā)展特點(diǎn)，綜 合反映出遞歸算法的特點(diǎn)，以及遞歸算法解答某些實(shí)踐問題通常得很簡(jiǎn)潔， 從而激發(fā)學(xué)生對(duì)程序設(shè)計(jì)的追求和向往。二、重點(diǎn)難點(diǎn)1、教學(xué)重點(diǎn)(1) 了解遞歸現(xiàn)象和遞歸算法的特點(diǎn)。(2) 能夠根據(jù)問題設(shè)計(jì)出恰當(dāng)?shù)?遞歸程序。2、教學(xué)難點(diǎn)(1) 遞歸過程思路的

3、建立。(2) 判斷冋題是否適于 遞歸解法。(3) 正確寫出遞歸程序。三、教學(xué)環(huán)境1、教材處理教材選自浙江省普通高中信息技術(shù)選修：算法與程序設(shè)計(jì)第五章，原教材的編排是以本節(jié)以斐波那契的兔子問題引人，導(dǎo)出遞歸算法，從而自定義了一個(gè)以遞歸方式解決的函數(shù)過程。然后利用子過程解決漢諾塔的經(jīng)典 問題。教材經(jīng)處理后，讓同學(xué)們玩漢諾塔的游戲，導(dǎo)入 遞歸問題，從用普通程 序解決斐波那契的兔子問題入手，引導(dǎo)學(xué)生用自定義了一個(gè)以 遞歸方式解決 的函數(shù)過程解決問題，同時(shí)讓同學(xué)們做三個(gè) 遞歸練習(xí)，鞏固提高。然后讓學(xué) 生做練習(xí) 和練習(xí) 這兩道題目的形式相差很遠(yuǎn)，但方法和答案卻都是完 全相同的練習(xí)，體會(huì)其中的奧妙，加深對(duì)

4、遞歸算法的了解。最后用子過程解 決漢諾塔的經(jīng)典問題。教學(xué)方法采用講解、探究、任務(wù)驅(qū)動(dòng)和學(xué)生自主學(xué)習(xí)相結(jié)合2、預(yù)備知識(shí)學(xué)生已掌握了用計(jì)算機(jī)解決問題的過程，掌握了程序設(shè)計(jì)基礎(chǔ)，掌握了解析法、窮舉法、查找法、排序法設(shè)計(jì) 程序的技巧。四、教學(xué)過程導(dǎo)入：大家玩漢諾塔游戲：這個(gè)游戲盤子在A、B C三根柱子上不停運(yùn)動(dòng)，有沒有規(guī)律，和你在照過鏡子時(shí)遇到的情況相同嗎當(dāng)你往鏡子前面一站，鏡子里面就有一個(gè)你的像。但你試過兩面鏡子一起 照嗎如果甲、乙兩面鏡子相互面對(duì)面放著，你往中間一站，嘿，兩面鏡子里都有 你的千百個(gè)“化身” ！為什么會(huì)有這么奇妙的現(xiàn)象呢原來，甲鏡子里有乙鏡子的 像，乙鏡子里也有甲鏡子的像，而且這樣反

5、反復(fù)復(fù)，就會(huì)產(chǎn)生一連串的“像中像”。 這是一種遞歸現(xiàn)象。由同學(xué)們總結(jié)出遞歸算法的概念遞歸算法：是一種直接或者間接地調(diào)用自身的 算法。在計(jì)算機(jī)編寫程序中, 遞歸算法對(duì)解決一大類問題是十分有效的，它往往使算法的描述簡(jiǎn)潔而且易于理 解。問題4-16 :著名的意大利數(shù)學(xué)家斐波那契(Fibonacci)在他的著作算盤書中 提出了一個(gè)“兔子問題”：假定小兔子一個(gè)月就可以長(zhǎng)成大兔子，而大兔子每個(gè) 月都會(huì)生出一對(duì)小兔子。如果年初養(yǎng)了一對(duì)小兔子，問到年底時(shí)將有多少對(duì)兔 子(當(dāng)然得假設(shè)兔子沒有死亡而且嚴(yán)格按照上述規(guī)律長(zhǎng)大與繁殖)我們不難用以前學(xué)過的知識(shí)設(shè)計(jì)出如下算法： 輸入計(jì)算兔子的月份數(shù)：n If n 3 Th

6、e n c = 1 Else a = 1: b = 1 i = 3 c = a + b : a = b : b = c i=i+1,如果i n則返回 結(jié)束參考程序如下：Private Sub Comma nd1_Click()n = VaiIf n 3 The n c = 1 Else a = 1: b = 1For i = 3 To nc = a + ba = bb = cNext i=第&n& 月的兔子數(shù)目是：& cEnd Sub開動(dòng)腦筋：我們有沒有更簡(jiǎn)單的方法解決該問題呢從斐波那契的兔子問題看遞歸算法1 斐波那契的兔子問題子分析冋題。我們可以根據(jù)題意列出表4-3來解決這個(gè)問題: 表43兔

7、子冋題分析表1月2月3月4月5月6月7月8月9月10月11月12月小 兔111235813213455大 兔1123581321345589合計(jì)1123581321345589144這個(gè)表格雖然解決了斐波那契的兔子問題(年底時(shí)兔子的總數(shù)是144只), 但仔細(xì)觀察一下這個(gè)表格，你會(huì)發(fā)現(xiàn)兔子的數(shù)目增長(zhǎng)得越來越快，如果時(shí)間再長(zhǎng)， 只用列表的方法就會(huì)有困難。(例如，你愿意用列表的方法求出5年后兔子的數(shù) 目嗎)我們需要研究表中的規(guī)律，找出一般的方法，去解決這個(gè)問題。 交流仔細(xì)研究表4-8，你有些什么發(fā)現(xiàn)每一個(gè)月份的大兔數(shù)、小兔數(shù)與上一個(gè)月 的數(shù)字有什么聯(lián)系，能肯定這個(gè)規(guī)律嗎恭喜你，你快成功了設(shè)計(jì)算法。“

8、兔子問題”很容易列出一條 遞推式而得到解決。假設(shè)第N個(gè)月的兔子數(shù)目是 F(N)，我們有：這是因?yàn)槊吭碌拇笸米訑?shù)目一定等于上月的兔子總數(shù)，而每個(gè)月的小兔子數(shù)目一定等于上月的大兔子數(shù)目(即前一個(gè)月的兔子的數(shù)目)。由上述的遞推式我們可以設(shè)計(jì)出遞歸程序。遞歸程序的特點(diǎn)是獨(dú)立寫出一個(gè) 函數(shù)(或子過程)，而這個(gè)函數(shù)只對(duì)極簡(jiǎn)單的幾種情況直接給出解答， 而在其余情 況下通過反復(fù)的調(diào)用自身而把問題歸結(jié)到最簡(jiǎn)單的情況而得到解答。刖面學(xué)過： 自定義函數(shù)的定義格式：Function 函數(shù)名(參數(shù)表 )As type過程中的代碼End Fun cti on調(diào)用函數(shù)的格式：函數(shù)名(參數(shù)表)(3) 編寫程序。窗體中開設(shè)一個(gè)

9、文本框Textl用于填人月數(shù)N,設(shè)置命令框Commandl點(diǎn)擊 它即執(zhí)行程序求出第N月的兔子數(shù)。然后用文本框Text2輸出答案。根據(jù)遞推式可以寫出遞歸程序如下：Function Fib(ByVal N As Integer) As LongIf N 3 Then Fib = 1 Else Fib = Fib(N - 1) + Fib(N - 2) End Fun cti onPrivate Sub Comma nd1_Click()N = Val=第& N & 月的兔子數(shù)目是：& Fib(N)End Sub調(diào)試程序 因?yàn)檫@個(gè)算法的效率不高，建議在調(diào)試 程序時(shí)月份數(shù)不要大于40。一個(gè)應(yīng)用遞歸算法

10、解決的問題經(jīng)典例子問題4-17 :傳說在古代印度的貝拿勒斯神廟，有一塊黃銅板上插了3根寶石柱，在其中一根寶石柱自上而下由小到大地疊放著64個(gè)大小不等的金盤。一名僧人把這些金盤從一根寶石柱移到另外一根上。僧人在移動(dòng)金盤時(shí)遵守下面3條規(guī)則：第一，一次只能移動(dòng)一個(gè)金盤。第二，每個(gè)金盤只能由一根寶石柱移到另外一根寶石柱。第三，任何時(shí)候都不能把大的金盤放在小的金盤上。神話說，如果僧人把64個(gè)金盤完全地從一根寶石移到了另外一根上，世界 的末日就要到了。當(dāng)然，神話只能當(dāng)故事來聽，世界不可以因?yàn)閭€(gè)別人的活動(dòng)而 導(dǎo)致末日。不過，從僧人搬完64個(gè)金盤所需時(shí)間的角度來說，即使僧人每秒都 能移動(dòng)一個(gè)金盤，那也得要幾千

11、億年！(1) 分析問題。我們把3根寶石柱分別命名為A、B、C。最初有N個(gè)金盤放在A,需要把它 們?nèi)堪匆?guī)則移動(dòng)到Bo當(dāng)N=1時(shí)，直接把金盤從A搬到B就可以了，1次成功。 當(dāng)NA2,那么需要利用C柱來過渡。我們假設(shè)已經(jīng)找到一種把 N1個(gè)金盤從一 根柱搬到另外一根柱的方法，那么，我們只要把N-1個(gè)金盤從A搬到C,然后把最大的金盤從A搬到B,最后把C上的N一一 1個(gè)金盤搬到B就可以了?？窟f歸 的思想，我們輕而易舉地完成了整個(gè)搬動(dòng)。設(shè)計(jì)算法。我們定義一個(gè)過程Hanoi(N，A，B，C)，表示有N個(gè)金盤需要從A柱搬到B 柱(以C柱為過渡)。那么完成它只需3步： Hanoi(N 1, A，C, B)它的意

12、思是把A柱上的N 1個(gè)金盤搬到C柱; A-B它的意思是把一個(gè)(最大的)金盤從A柱搬到B柱； Hanoi(N 1, C, B, A)它的意思是把c柱上的N 1個(gè)金盤搬到B柱。前面已經(jīng)學(xué)過：過程定義的格式：Private Sub 過程名(參數(shù)表)代碼End Sub調(diào)用過程的格式：Call過程名(參數(shù)表)(3)編寫程序(引導(dǎo)學(xué)生編寫程序)。Private Sub Hanoi(n As Integer, ByVai A As String, ByVai B As String, ByVai C As Stri ng, t As Long)If n = 1 The n = + A + + B + vbC

13、rLft = t + 1增加變量t用來統(tǒng)計(jì)移動(dòng)次數(shù)。ElseCall Hanoi(n - 1, A, C, B, t)=+ A + + B + vbCrLft = t + 1Call Hanoi(n - 1, C, B, A, t) End IfEnd SubPrivate Sub Comma nd1_Click() Dim t As Long, n As In teger t = 0n = VaiA = A B = B C = C Call Hanoi(n, A, B, C, t)=tEnd Sub測(cè)試程序 在文本框中輸入4算法然后遞歸調(diào)小結(jié)： 遞歸算法的特點(diǎn) 遞歸過程一般通過函數(shù)或子過程來實(shí)現(xiàn)。 遞歸算法：在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的 遞歸算法的實(shí)質(zhì)：是把問題轉(zhuǎn)化為規(guī)模縮小了的同類問題的子問題 用函數(shù)(或過程)來表示問題的解。 遞歸算法解決問題的特點(diǎn)：(1) 遞歸就是在過程或函數(shù)里調(diào)用自身(2) 在使用遞增歸策略時(shí)，必須有一個(gè)明確的 遞歸結(jié)束條件，稱為遞歸出口(3) 遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低。所以一般 不提倡用遞歸算法設(shè)計(jì)(4) 在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)。遞歸次數(shù)過多容易造成棧