遞歸算法和遞歸程序doc資料

遞歸算法和遞歸程序當(dāng)你站在甲、乙兩面相互面對(duì)面的鏡子中間時(shí)，你會(huì)發(fā)現(xiàn)什么奇妙的現(xiàn)象嗎？

你會(huì)發(fā)現(xiàn)甲鏡子里有乙鏡子的像，乙鏡子里有甲鏡子的像，而且反反復(fù)復(fù)，就會(huì)產(chǎn)生一連串的“像中像”。照鏡子問(wèn)題蘊(yùn)含了遞歸思想遞歸法包括2種情況：函數(shù)自己調(diào)用自己兩個(gè)函數(shù)之間相互調(diào)用

遞歸算法：就是一種函數(shù)直接或者間接地調(diào)用自身的算法。4.5.1

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

一、斐波那契的兔子問(wèn)題

1．斐波那契的兔子問(wèn)題——取自意大利數(shù)學(xué)家斐波那契的《算盤(pán)書(shū)》（1202年）

(L.Fibonacci,1170-1250）

問(wèn)題假定小兔子一個(gè)月就可以長(zhǎng)成大兔子，而大兔子每個(gè)月就會(huì)生出一對(duì)小兔子。如果年初養(yǎng)了一對(duì)小兔子，問(wèn)到年底時(shí)將有多少對(duì)兔子？（假設(shè)兔子沒(méi)有死亡而且嚴(yán)格按照上述規(guī)律長(zhǎng)大與繁殖）分析

1月

1對(duì)分析

1月 1對(duì)

2月 1對(duì)分析

1月 1對(duì)

2月 1對(duì)

3月 2對(duì)分析

1月 1對(duì)

2月 1對(duì)

3月 2對(duì)

4月 3對(duì)分析

1月 1對(duì)

2月 1對(duì)

3月 2對(duì)

4月 3對(duì)

5月 5對(duì)分析

1月 1對(duì)

2月 1對(duì)

3月 2對(duì)

4月 3對(duì)

5月 5對(duì)

6月 8對(duì)兔子問(wèn)題分析表1月2月3月4月5月6月7月8月9月10月11月12月小兔111235813213455大兔1123581321345589合計(jì)1123581321345589144你會(huì)發(fā)現(xiàn)時(shí)間越長(zhǎng)，用列表法解決會(huì)很困難。我們需要研究表中的規(guī)律，找出一般的方法去解決這個(gè)問(wèn)題。仔細(xì)觀察表內(nèi)的數(shù)據(jù)你會(huì)發(fā)現(xiàn)第N個(gè)月的兔子總數(shù)是第N-1個(gè)月和第N-2個(gè)月兔子總數(shù)之和。設(shè)計(jì)算法假設(shè)第N個(gè)月的兔子數(shù)目是F（N），我們可以得到這樣一個(gè)遞推式：F（N）=F（N-1）+F（N-2）當(dāng)N>=3F（1）=F（2）=1編寫(xiě)程序同學(xué)們自己設(shè)計(jì)下面的窗體并寫(xiě)出遞歸程序：調(diào)試程序運(yùn)行程序，在文本框Text1.text中輸入月數(shù)，得出運(yùn)行結(jié)果。單擊此按鈕運(yùn)行程序遞歸算法基本思想:

把規(guī)模大的、較難解決的問(wèn)題變成規(guī)模較小的、易解決的同一問(wèn)題。規(guī)模較小的問(wèn)題又變成規(guī)模更小的問(wèn)題，并且小到一定的程度直到可以直接得出它的解，從而得到原來(lái)問(wèn)題的解。注意：必須要有一個(gè)結(jié)束遞歸的條件，不得無(wú)限遞歸。遞歸法的歸納1：遞歸算法的實(shí)質(zhì)：是把問(wèn)題轉(zhuǎn)化為規(guī)模縮小了的同類(lèi)問(wèn)題的子問(wèn)題。然后遞歸調(diào)用函數(shù)(或過(guò)程)來(lái)表示問(wèn)題的解。遞歸算法解決問(wèn)題的特點(diǎn)：(1)

遞歸就是在過(guò)程或函數(shù)里調(diào)用自身。(2)

在使用遞增歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱(chēng)為遞歸出口。(3)

遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序遞歸法的歸納2：遞歸算法所體現(xiàn)的“重復(fù)”一般有三個(gè)要求：一是每次調(diào)用在規(guī)模上都有所縮小(通常是減半)；二是相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備(通常前一次的輸出就作為后一次的輸入)；三是在問(wèn)題的規(guī)模極小時(shí)必須用直接給出解答而不再進(jìn)行遞歸調(diào)用，因而每次遞歸