noip講義5-遞歸法(小學(xué)程度)

遞歸

如果函數(shù)體或過程體中出現(xiàn)調(diào)用其自身的語句，稱為遞歸。

遞歸過程的執(zhí)行流程

從下圖可知，遞歸過程的執(zhí)行總是一個過程體未執(zhí)行完，

就帶著本次執(zhí)行的結(jié)果又進入另一輪過程體的執(zhí)行，……，如此反復(fù)，不斷深入，直到某次過程的執(zhí)行遇到終止遞歸的邊界條件時，則不再深入，而執(zhí)行本次的過程體余下的部分，然后又返回到上一次調(diào)用的過程體中，執(zhí)行其余下的部分，……，如此反復(fù)，直到回到起始位置上，才最終結(jié)束整個遞歸過程的執(zhí)行，得到相應(yīng)的執(zhí)行結(jié)果。寫出運行結(jié)果。var

n:integer;procedurep(n:integer);

var

i:integer;beginifn>0thenbegin

p(n-1);

fori:=1tondowrite(n);

writeln;endend;beginn:=5;

p(n);end.P(5)->P(4)->P(3)->P(2)->P(1)->P(0)122333444455555遞歸函數(shù)或過程通常帶有一些局部變量(如本例中的n)，只有當整個函數(shù)體或過程體執(zhí)行完畢時，這些局部變量才失去意義。每遞歸調(diào)用一次，就必須生成一組‘新’的局部變量，雖然這些新的局部變量與原來的局部變量分別具有相同的名字，但其分配的存儲空間不同，其值也完全無關(guān)。遞歸在計算機中的實現(xiàn)

計算機執(zhí)行遞歸算法時，是通過棧來實現(xiàn)的。在遞歸過程（或函數(shù)）開始運行時，系統(tǒng)首先為遞歸建立一個棧，在每次執(zhí)行遞歸調(diào)用語句之前，自動把本算法中所使用的值參和局部變量的當前值以及調(diào)用后的返回地址壓棧（稱為“保存現(xiàn)場”，以便需要時“恢復(fù)現(xiàn)場”返回到某一狀態(tài)），在每次遞歸調(diào)用結(jié)束后，又自動把棧頂元素的值分別賦給相應(yīng)的值參和局部變量（出棧），以便使它們恢復(fù)到調(diào)用前的值，接著無條件轉(zhuǎn)向由返回地址所指定的位置繼續(xù)執(zhí)行算法。例1

階乘函數(shù)

階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程

邊界條件與遞歸方程是遞歸函數(shù)的二個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。

程序：

programp1(input，output)；

var

n：integer；s：

longint；

functionfac(a：integer)：longint；

beginifa=0thenfac:=1elsefac:=a*fac(a-1)；

end；

begin

readln(n)；

s:=fac(n)；

writeln(n，‘!=’，s)end．

遞歸過程分析-階乘函數(shù)

階乘函數(shù)可遞歸地定義為：邊界條件遞歸方程例2:

用遞歸方法求兩個數(shù)x和y的最大公約數(shù)。(x>0，y>0)

解1求兩個數(shù)的最大公約數(shù)可以用輾轉(zhuǎn)相除法，即求m與n的最大公約數(shù)等價于求（xmody）的值與y的最大公約數(shù)，此時的y可以當作新的x，而（xmody）的值當作新的y，所以原問題的求解又變成求新的m與n的最大公約數(shù)問題，繼續(xù)下去，直至(xmody)為0，最大公約數(shù)就是最終存放在y中的值。遞歸公式：functiongcd(x,y：longint)：longint；

varr：integer；beginr:=mmodn；

ifr=0thengcd:=nelsegcd:=gcd(n,r)；｛遞歸調(diào)用｝

end；varr：integer；beginr:=xmody；

ifr=0thengcd:=yelsegcd:=gcd(y,r)；｛遞歸調(diào)用｝

end；思考：0，1，1，2，3，5，8，13，21，34，55……從第三項起，每一項都是緊挨著的前兩項的和。寫出計算斐波那切數(shù)列的任意一個數(shù)據(jù)項遞歸函數(shù)形式。

functionfic(m：integer)：longint；

beginifm=1thenfic:=0elseifm=2thenfic:=1elsefic:=fic(m-1)+fic(m-2）

｛遞歸調(diào)用｝

end；遞歸過程當一個問題可以不斷的通過一種有規(guī)律的增加或遞減轉(zhuǎn)化為一個新問題，而解決新問題的方法和原問題相同時，可以考慮過程的遞歸調(diào)用，注意這種“不斷的增加或遞減”是有盡頭的。programp4(input，output)；procedurerever；

varc：char；

beginread(c)；

ifc<>'!'thenrever;write(c)；

end；begin{主程序}

rever；end．運行：輸入hey!輸出!yeh。程序中，c是過程rever的局部變量。每一次遞歸調(diào)用，都要為局部變量重新分配單元，因此各層的變量c實際上是不同的量，它們分別用于保存執(zhí)行本層調(diào)用時的輸入值。

例3：輸入一串以‘!’結(jié)束的字符，按逆序輸出。elseProcedrue

begin

輸出n的最右邊的一個數(shù)字；

if還有數(shù)字then將余下的“數(shù)字倒序”

end輸入一個非負數(shù)，輸出這個數(shù)的倒序數(shù)。elseProcedruereverse(n:integer);

var

nr,nl:integer;beginnr:=nmod10;write(nr);

nl:=ndiv10;ifnl<>0thenreverse(nl)end;遞歸過程分析—數(shù)字倒序例4:

用遞歸算法把任一給定的十進制正整數(shù)（<=32000）轉(zhuǎn)換成八進制數(shù)輸出。分析：利用短除法不斷除以8取余數(shù)這個重復(fù)過程，將原數(shù)據(jù)不斷縮小，形成遞歸關(guān)系，當數(shù)據(jù)規(guī)?？s小至0時，遞歸結(jié)束。proceduretran(n:longint);{遞歸過程}

var

k:longint;begink:=nmod8;{取除以8以后的余數(shù)}n:=ndiv8;{取除以8以后的商}ifn<>0thentran(n);{直到商為0，結(jié)束遞歸過程}write(k:1)end;在調(diào)用過程或函數(shù)之前，系統(tǒng)需完成三件事：⑴為被調(diào)用過程的局部變量分配存儲區(qū)；⑵將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用過程保存；⑶將控制轉(zhuǎn)移到被調(diào)過程的入口。從被調(diào)用過程返回調(diào)用過程之前，系統(tǒng)也應(yīng)完成三件工作：⑴保存被調(diào)過程的計算結(jié)果；⑵釋放被調(diào)過程的數(shù)據(jù)區(qū)；⑶依照被調(diào)過程保存的返回地址將控制轉(zhuǎn)移到調(diào)用過程。例5、由m個A，n個B組成若干個排列。從某個排列的位置1開始數(shù)，數(shù)到任意位置時都能保證A的個數(shù)不少于B的個數(shù)，則稱該排列為合理排列。例如：當m=2，n=2時排列有AABB(合理)ABAB(合理)ABBA(不合理)BBAA(不合理)合理排列數(shù)有2種輸入：只有一行兩個整數(shù)m,n（1≤n≤m≤12）（用空格分隔）輸出：一個整數(shù)（所有的合理排列數(shù)）【樣例】輸入輸出325分析：模擬排隊的情況，從第1個人開始，第1人只能是A，第2個可以是A也可以是B，再其后的人要保證任意位置時都能保證A的個數(shù)不少于B的個數(shù)，遞歸求有多少個排列。Var

m,n,t:LongInt;Procedurepd(i,j:LongInt);BeginIf(i=m)And(j=nThent:=t+1{已生成一種排列}ElseBeginIfi<mThenpd(i+1,j);{增加1個A}If(j<n)And(j<i)Thenpd(i,j+1);End;{增加1個B}End;Begint:=0;Read(m,n);pd(1,0);Writeln(t);End.(i=m)And(j=n)pd(i+1,j);(j<n)And(j<i)例7、漢諾塔（towerofHanoi）問題。有n個大小不等的中空圓盤，按照從小到大的順序迭套在立柱A上，另有兩根立柱B和C?，F(xiàn)要求把全部圓盤從A柱（源柱）移到C柱（目標柱），移動過程中可借助B柱（中間柱）。移動時有如下的要求：①一次只移動一個盤；②不允許把大盤放在小盤上邊；③可使用任意一根立柱暫存圓盤。先以三個盤的移動為例，看一下移動過程。

分析：首先將A柱上方的n-1個盤子從A柱移到B柱，此過程中C柱為中間柱；接著將A柱剩下的一個盤子移到C柱；最后再將B柱上的n-1個盤子移到C柱，此過程中A柱為中間柱，這就變成了移動n-1個盤子的問題了。定義過程hanoi，實現(xiàn)這一遞歸算法：若n=1，則A→C

若n>=2，則hanoi(n-1，A，C，B)

A→C

hanoi(n-1，B，A，C)運行結(jié)果：EnterthenumberofdisksinHanoitower：3A→CA→BC→BA→CB→AB→CA→Cvarn：integer；procedurehanoi(n:integer;x,y,z：char)；begin

ifn=1thenwriteln(x,‘->’,n,‘->’,z)

elsebegin

hanoi(n-1,x,z,y)；

writeln(x,‘->’,n,‘->’,z)；

hanoi(n-1,y,x,z)endend；begin

{主程序）

readln(n)；

hanoi(n,‘A’,‘B’,‘C’)end．解2求兩個數(shù)的最大公約數(shù)可以用輾轉(zhuǎn)相減法

f(x,y)=f(y,x-y)

避免了大整數(shù)的取模運算。但迭代次數(shù)太多。f(48,28)=f(28,20)=f(20,8)=f(12,8)=f(8,4)=f(4,0)分析：

1.如果y=k*y1，x=k*x1，有f(y,x)=k*f(y1,x1)。2.如果x=p*x1，假設(shè)p是素數(shù)，并且y不能被p整除，那么f(x,y)=f(p*x1,y)=f(x1,y)。例8再探1:

用遞歸方法求兩個數(shù)x和y的最大公約數(shù)。(x>0，y>0)

functionfic(m：integer)：longint；

beginifm=1thenfic:=0elseifm=2thenfic:=1elsefic:=fic(m-1)+fic(m-2）

｛遞歸調(diào)用｝

end；例9

再探Fibonacci數(shù)列

優(yōu)化？遞歸要素：完成遞歸必須考慮的因素有兩個。

（1）邊界條件。也就是所描述問題的最簡單情況，它本身不再使用遞歸的定義。如階乘，當n=0時，f(n)=1，不使用f(n-1)來定義。（2）遞歸關(guān)系。使問題向邊界條件轉(zhuǎn)化的規(guī)則。遞歸定義必須能使問題的規(guī)模越來越簡單。遞歸的優(yōu)點：長處是，它能使一個蘊含遞歸關(guān)系且結(jié)構(gòu)復(fù)雜的程序簡介精煉，增加可讀性。特別是在難于找到從邊界到解的全過程的情況下，如果把問題推進一步,其結(jié)果仍維持原問題的關(guān)系，則采用遞歸算法編程比較合適。遞歸的缺點：遞歸算法的效率往往很低，費時和費內(nèi)存空間。FreePascal理論上可以使用4GB（2^32byte）的內(nèi)存，因此實際上幾乎可以使用系統(tǒng)中的所有剩余內(nèi)存（但有時賽題中有內(nèi)存限制），這是因為FreePascal使用的是32位的編譯器。但大量數(shù)據(jù)的處理過程將會耗時,有時將出現(xiàn)超時。解決方法：在遞歸算法中消除遞歸調(diào)用，使其轉(zhuǎn)化為非遞歸算法。1、采用一個用戶定義的棧來模擬系統(tǒng)的遞歸調(diào)用工作棧。該方法通用性強，但本質(zhì)上還是遞歸，只不過人工做了本來由編譯器做的事情，優(yōu)化效果不明顯。2、用遞推來實現(xiàn)遞歸函數(shù)。3、通過變換能將一些遞歸轉(zhuǎn)化為尾遞歸，從而迭代求出結(jié)果。后兩種方法在時空復(fù)雜度上均有較大改善，但其適用范圍有限。如何設(shè)計遞歸算法

一個問題要用遞歸方法來解決必須符合兩個條件：1、可以把一個問題轉(zhuǎn)化成一個新的問題，而新問題的解法和原問題的解法完全相同，只是處理對象的規(guī)模不同。2、必順要有一個明確的遞歸結(jié)束條件。例1、翻硬幣(03年初賽題)

題目描述：一摞硬幣共有m枚，每一枚都是正面朝上。取下最上面的一枚硬幣，將它翻面后放回原處。然后取下最上面的2枚硬幣，將他們一起翻面后再放回原處。再取3枚，取4枚……直至m枚。然后再從這摞硬幣最上面的一枚開始，重復(fù)剛才的做法。這樣一直做下去，直到這摞硬幣中的每一枚又都是正面朝上為止。輸入：僅有的一個數(shù)字是這摞硬幣的枚數(shù)m，0<m<50。輸出：為了使這摞硬幣中的每一枚又都是正面朝上所必需翻的次數(shù)。輸入樣例：

30輸出樣例：

899constmax=100;var

a,b:array[1..max]ofboolean;

m,n:integer;procedureprint;

var

i:integer;

p:boolean;begin

（）；

p:=true;fori:=1tomdoifa[i]thenp:=false;ifpthenbegin

writeln('total=',n);

（）;end;end;procedureturn(k:integer);

var

i:integer;beginifk>mthen（）;b:=a;fori:=1tokdo

b[i]:=not(

);a:=b;print;

（）；

end;begin

readln(m);

fillchar(a,sizeof(a),false);n:=0;｛翻面次數(shù)｝

turn(1);｛翻一個硬幣｝end.k:=1halta[k+1-i]turn(k+1)inc(n)例2、求全排列(06年初賽題)

下面程序的功能是利用遞歸方法生成從1到n(n<10)的n個數(shù)的全部可能的排列（不一定按升序輸出）。例如，輸入3，則應(yīng)該輸出（每行輸出5個排列）：123132213231321312

var

i,n,k:integer;a:array[1..10]ofinteger;

count:longint;procedureperm(k:integer);

var

j,p,t:integer;begin

if()thenbegin();forp:=1tokdowrite(a[p]:1);write('');if()then

writeln;exit;end;

forj:=ktondobegint:=a[k];

a[k]:=a[j];

a[j]:=t;perm(k+1);t:=a[k];()

endend;begin

writeln('Entryn:');

read(n);count:=0;fori:=1tondoa[i]:=i;()end.perm(1)K=ninc(count)countmod5=0a[k]:=a[j];a[j]:=t;123123123132123132213213213231231321321321312312例3、2的冪次方表示(98年復(fù)賽)

任何一個正整數(shù)都可以用2的冪次方表示。例如：137=27+23+20同時約定次方用括號來表示，即ab可表示為a(b)。由此可知，137可表示為：2(7)+2(3)+2(0)

進一步：7=22+2+20(21用2表示)3=2+20所以最后137可表示為：2(2(2)+2+2(0))+2(2+2(0))+2(0)又如：1315=210+28+25+2+20所以1315最后可表示為：2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)輸入：一個正整數(shù)(n<=20000)輸出：符合約定的n的0,2表示(在表示中不能有空格)var

n:longint;proceduretry(n:longint);

vara:array[1..1000]ofinteger;

k,p,i,t:longint;beginfillchar(a,sizeof(a),0);

k:=n;p:=0;t:=0;while()dobegin

inc(p);

a[p]:=kmod2;if(a[p]<>0)and(t=0)thent:=p;

{t記錄二進制數(shù)中從最低位開始第一個'1'的位置}k:=kdiv2;end;fori:=pdowntot+1doifa[i]=1thenif()thenwrite('2+')elsebegin

write('2(');();write(')+');end;{情況一}if()thenwrite('2(0)')elsebeginift=2thenwrite('2')elsebeginwrite('2(');();write(')');end;end;{情況二}end;begin

readln(n);

try(n);end.由于最后一項后面沒有加號，其它項之后有加號，因此程序中進行了區(qū)別對待．k>0i=2try(i-1)t=1try(t-1)給出一棵二叉樹的中序與后序排列。求出它的先序排列。（約定樹結(jié)點用不同的大寫字母表示，長度≤8）。[樣例]輸入：BADCBDCA輸出：ABCD

分析:

通過對比二叉樹的中序與后序排列，我們可以找出根節(jié)點及左右子樹。同樣的，也可以通過對比左子樹的中序與后序排列，找出左子樹的根節(jié)點……可見，該問題能夠被遞歸描述。當找到最后一個根節(jié)點時，遞歸無法再進行下去，這就是遞歸結(jié)束的邊界條件。