算法與程序設(shè)計(jì) 4.5.1 從裴波那契的兔子問題看遞歸算法

遞歸算法與遞歸程序歙縣二中胡星

有4個(gè)人排成一隊(duì)，問最后一個(gè)人的身高時(shí)，他說比第3個(gè)人高2厘米；問第3個(gè)人的身高時(shí)，他說比第2個(gè)人高2厘米；問第2個(gè)人的身高時(shí)，他說比第1個(gè)人高2厘米；最后問第1個(gè)人的身高，他說是170厘米，請(qǐng)問：第4個(gè)人的身高是多少？Hn=H(n-1)+2H1=170H4=H3+2H3=H2+2H2=H1+2H1=170176172174遞歸遞歸在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法。遞歸是指一種（或多種）簡單的基本情況定義的一類對(duì)象或方法，并規(guī)定其他所有情況都能被還原為其基本情況。上臺(tái)階:10級(jí)臺(tái)階每次可上1級(jí)或2級(jí)，有多少種上法?1級(jí)臺(tái)階1 1種2級(jí)臺(tái)階 1+1，2 2種3級(jí)臺(tái)階 1+1+1，1+2，2+13種4級(jí)臺(tái)階1+1+1+1，1+1+2，1+2+1，2+1+1，2+25種……

……

……10級(jí)臺(tái)階

？枚舉法若對(duì)第一步進(jìn)行分析，則有兩種情況：假設(shè)第一步上1級(jí)，則余n-1級(jí)。假設(shè)第一步上2級(jí)，則余n-2級(jí)。12345678910123581321345589設(shè)Sn為n級(jí)的上法，則有：Sn=S(n-1)+S(n-2)

(n≥3)S1=1S2=2分析問題設(shè)計(jì)算法開始輸入臺(tái)階數(shù)nn≤2S(n)=nS(n)=S(n-1)+S(n-2)輸出方法數(shù)S(n)結(jié)束否是S(n)編寫程序FunctionS(ByValnAsInteger)AsLongIfn<=2ThenS=nElseS=S(n-1)+S(n-2)EndFunctionPrivateSubForm_Click()DimnAsIntegern=Val(InputBox(“請(qǐng)輸入樓梯級(jí)數(shù)n：","輸入樓梯級(jí)數(shù)"))Print"當(dāng)樓梯級(jí)數(shù)";n;"時(shí)，"Print"可以有";S(n);"種不同的上樓梯方法。"EndSub調(diào)試運(yùn)行上臺(tái)階方法檢測結(jié)果遞歸算法是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題，然后遞歸調(diào)用函數(shù)（或過程）來表示問題的解。因此，設(shè)計(jì)遞歸算法的關(guān)鍵在于，確定遞歸公式（過程的描述中包含他本身）和確定邊界（終了）條件。遞歸作為一種算法被應(yīng)用在程序設(shè)計(jì)語言中，是指函數(shù)/過程/子程序在運(yùn)行過程中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)象。小結(jié)遞歸算法與遞歸程序遞歸現(xiàn)象遞歸特點(diǎn)使算法的描述簡單而易于表達(dá)遞歸算法往往不是高效的算法遞歸三要素每次遞歸調(diào)用都要縮小問題規(guī)模前次遞歸調(diào)用為后次做準(zhǔn)備遞歸調(diào)用必須有條件進(jìn)行拓展若10級(jí)臺(tái)階每次可上1級(jí)或2級(jí)或3級(jí)，又有多少種上法?1級(jí)臺(tái)階1 1種2級(jí)臺(tái)階 1+1，2 2種3級(jí)臺(tái)階 1+1+1，1+2，2+1，34種……

……