用遞歸法解決問題

用遞歸法解決問題

教學(xué)重點（1）了解遞歸現(xiàn)象和遞歸算法的特點。（2）自定義函數(shù)及遞歸算法的自定義函數(shù)實現(xiàn)。（3）培養(yǎng)“自頂向下”、“逐步求精”的意識。

教學(xué)難點(1)遞歸過程思路的建立。(2)判斷問題是否適于遞歸解法。(3)正確寫出遞歸程序。

遞歸算法遞歸算法作為計算機程序設(shè)計中的一種重要的算法，是較難理解的算法之一。簡單地說，遞歸就是編寫這樣的一個特殊的過程，該過程體中有一個語句用于調(diào)用過程自身（稱為遞歸調(diào)用）。遞歸過程由于實現(xiàn)了自我的嵌套執(zhí)行，使這種過程的執(zhí)行變得復(fù)雜起來，其執(zhí)行的流程可以用圖1所示。遞歸算法調(diào)用子程序的含義

在過程和函數(shù)的學(xué)習(xí)中，我們知道調(diào)用子程序的一般形式是：主程序調(diào)用子程序A，子程序A調(diào)用子程序B，如圖如示，這個過程實際上是遞歸的定義：

一個函數(shù)在定義時，地調(diào)用了自己，這種算法在程序設(shè)計中統(tǒng)稱為遞歸法。函數(shù)A函數(shù)B類型二函數(shù)A類型一直接或者間接遞歸算法遞歸是一種直接或者間接地調(diào)用自身的算法。在計算機編寫程序中，遞歸算法對解決一大類問題是十分有效的，它往往使算法的描述簡潔而且易于理解。

例(1)利用遞歸方法編寫一求N的階乘程序。分析：根據(jù)N!=N*(N-1)*(N-2)*(N-3)*……*3*2*1

可以推出下列式子：

這是一個典型的遞歸算法，參考程序如下：FunctionFa(ByValnAsInteger)AsLongIfn=1ThenFa=1ElseFa=n*Fa(n-1)EndIfEndFunctionPrivateSubForm_Click()DimnAsIntegern=Val(InputBox("輸入正整數(shù)N：","N！"))Print"輸入的正整數(shù)是";n;Print"，階乘是";Fa(n)EndSub程序代碼自定義函數(shù)的定義格式:Functionprocedurename(arguments)[Astype]StatementsEndFunction其中：procedurename是函數(shù)名，

arguments是函數(shù)中的參數(shù)表，

type是函數(shù)返回值的數(shù)據(jù)類型，

statements是過程中的代碼調(diào)用函數(shù)的格式：Procedurename(arguments)分析：可以推出下列式子：

1月2月3月4月5月6月7月8月9月10月11月12月小兔1

11235813213455大兔

1123581321345589合計1123581321345589144例(2)斐波那契(Fibonacci)數(shù)列

“兔子問題”：假定小兔子一個月就可以長成大兔子，而大兔子每個月都會生出一對小兔子。如果年初養(yǎng)了一對小兔子，問到年底時將有多少對兔子?FunctionFb(ByValNAsInteger)AsLong

IfN<3ThenFb=1ElseFb=Fb(N-1)+Fb(N-2)EndIfEndFunctionPrivateSubCommand1_Click()

N=Val(Text1.Text)

Text2.Text="第"&N&"月的兔子數(shù)目是："&Fb(N)EndSub程序代碼分析：第一階第二階第三階例(3)爬樓梯樓梯一共有N個臺階，小明爬樓梯的方法是一步跨一個臺階或者一步跨兩個臺階，于是小明開始爬樓，爬上樓以后小明提了一個問題：按剛才那樣，爬完臺階一共有多少種可能的爬法？第一階只有一種爬法：跨一步1種第二階有兩種爬法：每次只跨1步或者跨2步2種第三階有三種爬法：有可能來自第一階，也有可能來自第二階3種思考：那第四階，第五階有多少種爬法呢那第n階有多少種爬法呢？假設(shè)g（n）表示第n個臺階的爬法由數(shù)學(xué)知識可得遞歸關(guān)系式：ng(n-1)+g(n-2)n>2n≤2g(n)=遞歸程序如下：Privatefunctiong(byvalnasinteger)Ifn=1orn=2theng=nElseg=g(n-1)+g(n-2)EndifEndfunction思考g(n)與g(n-1)、g(n-2)關(guān)系任務(wù)：1、寫出遞歸公式2、完成程序代碼小結(jié)：遞歸算法的特點：

遞歸過程：

一般通過函數(shù)或子過程來實現(xiàn)。

遞歸算法：

在函數(shù)或子過程的內(nèi)部，直接或者間接地調(diào)用自己的算法。遞歸算法的實質(zhì)：

是把問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題。

然后遞歸調(diào)用函數(shù)(或過程)來表示問題的解。

小結(jié)：一個應(yīng)用遞歸算法解決的問題經(jīng)典例子傳說在古代印度的貝拿勒斯神廟，有一塊黃銅板上插了3根寶石柱，在其中一根寶石柱自上而下由小到大地疊放著64個大小不等的金盤。一名僧人把這些金盤從一根寶石柱移到另外一根上。僧人在移動金盤時遵守下面3條規(guī)則：第一，一次只能移動一個金盤。第二，每個金盤只能由一根寶石柱移到另外一根寶石柱。第三，任何時候都不能把大的金盤放在小的金盤上。神話說，如果僧人把64個金盤完全地從一根寶石移到了另外一根上，世界的末日就要到了。當(dāng)然，神話只能當(dāng)故事來聽，世界不可以因為個別人的活動而導(dǎo)致末日。不過，從僧人搬完64個金盤所需時間的角度來說，即使僧人每秒都能移動一個金盤，那也得要幾千億年！分析問題我們把3根寶石柱分別命名為A、B、C。最初有N個金盤放在A，需要把它們?nèi)堪匆?guī)則移動到B。當(dāng)N=1時，直接把金盤從A搬到B就可以了，1次成功。當(dāng)N≥2，那么需要利用C柱來過渡。我們假設(shè)已經(jīng)找到一種把N－1個金盤從一根柱搬到另外一根柱的方法，那么，我們只要把N－1個金盤從A搬到C，然后把最大的金盤從A搬到B，最后把C上的N－1個金盤搬到B就可以了。靠遞歸的思想，我們輕而易舉地完成了整個搬動。設(shè)計算法

我們定義一個過程Hanoi(N，A，B，C)，表示有N個金盤需要從A柱搬到B柱(以C柱為過渡)。那么完成它只需3步：①Hanoi(N－1，A，C，B)它的意思是把A柱上的N－1個金盤搬到C柱；②

A→B

它的意思是把一個(最大的)金盤從A柱搬到B柱；③

Hanoi(N－1，C，B，A)它的意思是把c柱上的N－1個金盤搬到B柱。子程序PrivateSubHanoi(nAsInteger,ByValAAsString,ByValBAsString,ByValCAsString,tAsLong)Ifn=1ThenText3.Text=Text3.Text+A+"→"+B+“"t=t+1增加變量t用來統(tǒng)計移動次數(shù)。Else

CallHanoi(n-1,A,C,B,t)

Text3.Text=Text3.Text+A+"→"+B+“"

t=t+1

CallHanoi(n-1,C,B,A,t)EndIfEndSub主程序PrivateSubCommand1_Click()

DimtAsLong,nAsInteger

t=0

n=Val(Text1.Text)

A="A":

B="B":

C="C"

CallHanoi(n,A,B,C,t)

Text2.Text=tEndSub小結(jié)遞歸算法所體現(xiàn)的“重復(fù)”一般有三個要求