4.5.1從裴波那契的兔子問(wèn)題看遞歸算法

1、游戲：猜猜是什么禮物游戲規(guī)則：邀請(qǐng)幾個(gè)學(xué)生拆禮物，如果你拆開(kāi)看到的是禮物盒子，請(qǐng)你將里邊的禮物盒子轉(zhuǎn)交給下一個(gè)同學(xué)，下一個(gè)同學(xué)拆禮物盒子，如果拆開(kāi)看到的依然禮物盒子，依舊將禮物轉(zhuǎn)交給盒子給下一個(gè)學(xué)生，以此類(lèi)推，直到幸運(yùn)的學(xué)生打開(kāi)盒子后看到的是禮物。請(qǐng)幸運(yùn)的學(xué)生將禮物交給你前一個(gè)學(xué)生，依次傳遞回到第一個(gè)人，直到第一個(gè)學(xué)生拿到禮物，并將是什么禮物告知所有的學(xué)生。第四章 第五節(jié)從斐波那契的兔子問(wèn)題看遞歸算法遞歸法的概念這種將問(wèn)題從未知“遞”到已知，再?gòu)囊阎鸩交亍皻w”，將原問(wèn)題求解的過(guò)程就是遞歸法求解問(wèn)題的過(guò)程。任務(wù)一：兔子問(wèn)題。開(kāi) 始問(wèn)題描述難度系數(shù) *分 析問(wèn) 題問(wèn)題：有一對(duì)兔子，從出生后第3個(gè)

2、月起每個(gè)月都生”一對(duì)”兔子，小兔子長(zhǎng)到第三個(gè)月后每個(gè)月又生一對(duì)兔子，假如兔子都不死，問(wèn)每個(gè)月的兔子總數(shù)為多少？1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合計(jì)1123581321345589144當(dāng)月兔子數(shù)=當(dāng)月小兔（上上月的兔子數(shù)）+當(dāng)月大兔（上月的兔子數(shù)）任務(wù)一：兔子問(wèn)題。設(shè) 計(jì)算 法難度系數(shù) *任務(wù)一：兔子問(wèn)題。難度系數(shù) *調(diào) 試運(yùn) 行編 寫(xiě)代 碼問(wèn)題解決嘗試體驗(yàn)：求和問(wèn)題問(wèn)題描述：s=1+2+3+4+5+6+7+.+n (n1遞推與遞歸遞推實(shí)現(xiàn)（循環(huán)實(shí)現(xiàn)）遞歸實(shí)現(xiàn)（自定義函數(shù)）Private Sub Com

3、mand1_Click()Dim n As Long, i As Long, s As Longn = Val(Text1.Text)For i = To s = Next iText2.Text = sEnd SubFunction sum(ByVal n As Long) As LongIf ( ) Then sum = 1 Else sum =End FunctionPrivate Sub Command1_Click()n = Val(Text1.Text)Text2.Text = sum(n)End Sub1ns + in=1sum(n-1)+n遞推與遞歸對(duì)比遞推實(shí)現(xiàn)遞歸實(shí)現(xiàn)循環(huán)實(shí)現(xiàn)

4、自定義函數(shù)實(shí)現(xiàn)從已知求到未知從大問(wèn)題“遞”到已知的小問(wèn)題，從已知的小問(wèn)題逐步回“歸”求解大問(wèn)題優(yōu)點(diǎn)是效率高。運(yùn)行時(shí)間只因循環(huán)次數(shù)增加而增加，沒(méi)什么額外開(kāi)銷(xiāo)?？臻g上沒(méi)有什么增加。優(yōu)點(diǎn)就是易理解，容易編程。缺點(diǎn)就是不容易理解，編寫(xiě)復(fù)雜問(wèn)題時(shí)困難。缺點(diǎn)是遞歸是用棧機(jī)制實(shí)現(xiàn)的，每深入一層，都要占去一塊棧數(shù)據(jù)區(qū)域，對(duì)嵌套層數(shù)深的算法，遞歸會(huì)力不從心，空間上會(huì)以?xún)?nèi)存崩潰而告終，而且遞歸也帶來(lái)了大量的函數(shù)調(diào)用，這也有許多額外的時(shí)間開(kāi)銷(xiāo)。所以在深度大時(shí)，它的時(shí)空性就不好了。遞歸算法基本模式：Function fib(ByVal n As Long) As LongIf (n 3) /遞歸結(jié)束條件、出口Then

5、 fib = 1 /直接求解Else fib = fib(n - 1) + fib(n - 2) /遞歸求解End Function小結(jié)：(1)遞歸法通過(guò)自定義函數(shù)來(lái)實(shí)現(xiàn)；(2）函數(shù)體內(nèi)通過(guò)分支來(lái)判斷是否滿(mǎn)足遞歸結(jié)束條件，不滿(mǎn)足則進(jìn)一步縮小規(guī)模，遞歸處理。遞歸算法總結(jié)：遞歸算法1遞歸法規(guī)律2遞歸法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)缺點(diǎn)概 念遞歸算法結(jié)構(gòu) 遞歸算法基本模式 自己調(diào)用自己自定義函數(shù)（函數(shù)調(diào)用本身）遞歸法的基本模式Function sum( ) As LongIf ( ) Then /遞歸出口Else /遞歸調(diào)用函數(shù)自己End Function歡迎交流完！課后作業(yè)課后習(xí)題：難度系數(shù) *按照遞歸算法解決問(wèn)題的一般步驟：分析問(wèn)題，設(shè)計(jì)算法，編寫(xiě)程序，調(diào)試運(yùn)行，完成以下習(xí)題。1.某同學(xué)在上樓梯時(shí)，有時(shí)一步一級(jí)樓梯，有時(shí)一步兩級(jí)。如果樓梯有n級(jí)，他上完這n級(jí)樓梯有多少種不同