遞歸算法與遞歸程序這幅圖中，蘊含了一個的神奇的故事，你能講出這個故事嗎？從前有座山，山里有座廟，廟里有個老和尚給小和尚講故事：老和尚說：“從前有座山，山里有座廟，廟里有個老和尚給小和尚講故事：老和尚說：“從前有座山，山里有座廟…這個故事有什么獨特之處？故事之中嵌套了故事本身，循環往復，無休無止事例1：做個游戲，看圖講故事事例2：想像一下，當你身處一個兩面都是鏡子的空間里，你會看到什么樣的景象？鏡中有像，像中有鏡，層層疊疊，無窮無盡事例1中，“從前有座山…”中故事講述了故事本身。事例2中，A鏡中有B鏡的鏡像，B鏡的鏡像中又有A鏡的鏡像，鏡像互相映照，層層疊疊。故事

鏡子A

鏡子B在程序設計中，運用遞歸思想設計的算法，我們稱之為“遞歸算法”。那么，遞歸算法是怎樣實現的，如何運用遞歸算法來解決我們生活中的實際問題呢？今天這節課，我們就來共同探究遞歸算法與遞歸程序，揭開遞歸算法的神秘面紗。這種事物直接或者間接調用自身的現象，我們稱之為“遞歸”。

著名的意大利數學家斐波那契在他的著作《算盤書》中提到了這樣一個問題：有人年初養了一對小兔子，這對小兔子一個月后就可以長成大兔子，而大兔子每個月都會生出一對小兔子，問到年底時一共有多少對兔子?。。。？問題1：斐波那契的兔子問題兔子問題分析：1月2月3月4月5月6月7月8月9月10月11月12月小兔大兔合計每月大兔數=下月小兔數每月兔子總數=下月大兔數1月2月3月4月5月6月想一想：每月大兔數與下月小兔數是什么關系？每月兔子總數與下月大兔數又是什么關系？11235512315534144895534211388511211321345589231381

用列表的方法，我們很容易地解決了問題，但仔細觀察表格中的數據，我們會發現隨著月份的增長兔子的數目增長的越來越快，如果時間再長的話用列表的方法就會越來越困難。試想一下，你愿意用列表的方法求出5年后兔子的數目嗎？所以，我們需要尋找更簡便更一般的方法。想一想：還有什么更好的方法？編程求解1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321347589合計11235813213455891441.分析問題：仔細研究表中的數據，你有什么發現？從第3個月開始，每月兔子數等于前兩個月的兔子數之和每個月的兔子總數=小兔數+大兔數=上個月大兔數+上個月兔子總數=上上個月兔子總數+上個月兔子總數

為什么？假設第N個月的兔子數目是F(N)，那么兔子問題的求解可以描述為一個函數：F(1)=F(2)=1N<3F(N)=F(N-1)+F(N-2)N>=3觀察：這個函數有什么特點？函數自己調用了自己（遞歸）1.分析問題（用函數描述問題的求解）：F(4)=F(3)+F(2)F(5)=F(4)+F(3)F(6)=F(5)+F(4)F(3)=F(2)+F(1)F(4)=F(3)+F(2)F(3)=F(2)+F(1)F(3)=F(2)+F(1)F(1)=F(2)=1N<3F(N)=F(N-1)+F(N-2)N>=3遞推回歸

遞歸算法實質是把問題轉化為規模縮小了的同類問題的子問題，然后通過函數（或過程）重復的層層自我調用（遞歸調用）來描述問題的解答。2.設計算法（定義函數，調用函數）：問題需求：求第N個月的兔子數目是F(N)Step1:定義函數f(n)（用函數描述問題的求解）

當N<3時，f(n)=1；當N>=3時，f(n)=f(n-1)+F(N-2)Step2:輸入月份nStep3:輸出f(n)（調用定義的函數f(n)）主程序Sub流程圖：自定義函數F(N)流程圖：3.編寫程序:定義函數：FunctionF(ByValNAsInteger)AsLongIfN<3thenF=1elseF=F(N-1)+F(N-2)EndFunction自定義函數的定義格式:Function函數名稱(參數列表)[As類型]語句組EndFunction

子過程的定義格式:PrivateSub子過程名稱(參數列表)過程語句組EndSub

調用自定義函數的格式：變量=函數名稱(參數)

定義子過程：PrivateSubCommand1_Click()N=Val(Text1.Text)Label3.Caption=F(N)EndSub1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321347589合計1123581321345589144打開ep1.frm文件，輸入程序，運行并測試結果：4.運行調試，測試結果：任務1:嘗試用遞歸算法編寫程序，解決斐波那契的兔子問題。打開ep1.frm窗體文件，補充程序代碼并運行調試，測試結果。1.遞歸算法是如何實現的？遞歸算法的實質是什么？2.運用遞歸算法編程解決問題的一般過程與方法？3.遞歸算法解決問題有什么特點？交流與討論：1.遞歸算法的實質及實現方法：遞歸算法實質是把問題轉化為規模縮小了的同類問題的子問題，然后通過函數（或過程）重復的層層自我調用（遞歸調用）來描述問題的解答。課堂小結：3.遞歸算法解決問題的特點：（1）問題描述簡潔，結構清晰，易于理解；（2）必須有一個明確的遞歸結束條件，稱為遞歸出口，無結束條件（出口）的遞歸調用不能正常結束（溢出或者死循環）。（3）耗費計算機資源（占用內存空間）大，效率較低2.運用遞歸算法編程解決問題的一般過程與方法：（1）定義遞歸函數（或者過程）（用遞歸函數描述問題的求解）；（2）調用自定義函數（或者過程），求得結果問題2.數學上對正整數n的階乘的定義是1n=0n!=1×2×3×…×n,n>0

任務2:打開ep2.frm，將程序補充完整，實現求任意正整數N的階乘n!=1×2×3×…×(N-1)×n(N-1)!=1×2×3×…×(N-1)…1!=1×10!=1

用函數F(N)描述N!1n=0

F(N)=n>0問題3.在計算機內部是用加法運算來求乘法運算結果的。試編寫一個程序實現求出兩個正整數M與N相乘的結果，代碼中不能出現乘法運算。

任務3:打開ep3.frm，將程序補充完整，實現用加法運算求正整數M與N的乘積。M×N=M+M+…+M(N個M）M×(N-1)=M+M+…+M(N-1個M）

…

M×2=M+M

M×1=M

用函數F(N)描述N!mn=1

F(N)=n>1用函數F(N)描述N!mn=1

F(N)=n>1任務4:打開ep4.frm，將程序代碼補充完整，實現求從比薩斜塔落下的小球N次著地后經過的垂直距離.第1次著地，F(1)=54.5第2次著地，F(2)=54.5+54.5/2=81.75第3次著地，F(3