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

遞歸

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

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

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

就帶著本次執(zhí)行的結(jié)果又進(jìn)入另一輪過(guò)程體的執(zhí)行，……，如此反復(fù)，不斷深入，直到某次過(guò)程的執(zhí)行遇到終止遞歸的邊界條件時(shí)，則不再深入，而執(zhí)行本次的過(guò)程體余下的部分，然后又返回到上一次調(diào)用的過(guò)程體中，執(zhí)行其余下的部分，……，如此反復(fù)，直到回到起始位置上，才最終結(jié)束整個(gè)遞歸過(guò)程的執(zhí)行，得到相應(yīng)的執(zhí)行結(jié)果。寫出運(yùn)行結(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ù)或過(guò)程通常帶有一些局部變量(如本例中的n)，只有當(dāng)整個(gè)函數(shù)體或過(guò)程體執(zhí)行完畢時(shí)，這些局部變量才失去意義。每遞歸調(diào)用一次，就必須生成一組‘新’的局部變量，雖然這些新的局部變量與原來(lái)的局部變量分別具有相同的名字，但其分配的存儲(chǔ)空間不同，其值也完全無(wú)關(guān)。遞歸在計(jì)算機(jī)中的實(shí)現(xiàn)

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

階乘函數(shù)

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

邊界條件與遞歸方程是遞歸函數(shù)的二個(gè)要素，遞歸函數(shù)只有具備了這兩個(gè)要素，才能在有限次計(jì)算后得出結(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．

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

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

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

解1求兩個(gè)數(shù)的最大公約數(shù)可以用輾轉(zhuǎn)相除法，即求m與n的最大公約數(shù)等價(jià)于求（xmody）的值與y的最大公約數(shù)，此時(shí)的y可以當(dāng)作新的x，而（xmody）的值當(dāng)作新的y，所以原問(wèn)題的求解又變成求新的m與n的最大公約數(shù)問(wèn)題，繼續(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……從第三項(xiàng)起，每一項(xiàng)都是緊挨著的前兩項(xiàng)的和。寫出計(jì)算斐波那切數(shù)列的任意一個(gè)數(shù)據(jù)項(xiàng)遞歸函數(shù)形式。

functionfic(m：integer)：longint；

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

｛遞歸調(diào)用｝

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

varc：char；

beginread(c)；

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

end；begin{主程序}

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

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

begin

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

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

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

var

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

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

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

var

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

m,n,t:LongInt;Procedurepd(i,j:LongInt);BeginIf(i=m)And(j=nThent:=t+1{已生成一種排列}ElseBeginIfi<mThenpd(i+1,j);{增加1個(gè)A}If(j<n)And(j<i)Thenpd(i,j+1);End;{增加1個(gè)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）問(wèn)題。有n個(gè)大小不等的中空?qǐng)A盤，按照從小到大的順序迭套在立柱A上，另有兩根立柱B和C。現(xiàn)要求把全部圓盤從A柱（源柱）移到C柱（目標(biāo)柱），移動(dòng)過(guò)程中可借助B柱（中間柱）。移動(dòng)時(shí)有如下的要求：①一次只移動(dòng)一個(gè)盤；②不允許把大盤放在小盤上邊；③可使用任意一根立柱暫存圓盤。先以三個(gè)盤的移動(dòng)為例，看一下移動(dòng)過(guò)程。

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

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

A→C

hanoi(n-1，B，A，C)運(yùn)行結(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求兩個(gè)數(shù)的最大公約數(shù)可以用輾轉(zhuǎn)相減法

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

避免了大整數(shù)的取模運(yùn)算。但迭代次數(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是素?cái)?shù)，并且y不能被p整除，那么f(x,y)=f(p*x1,y)=f(x1,y)。例8再探1:

用遞歸方法求兩個(gè)數(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)化？遞歸要素：完成遞歸必須考慮的因素有兩個(gè)。

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

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

題目描述：一摞硬幣共有m枚，每一枚都是正面朝上。取下最上面的一枚硬幣，將它翻面后放回原處。然后取下最上面的2枚硬幣，將他們一起翻面后再放回原處。再取3枚，取4枚……直至m枚。然后再?gòu)倪@摞硬幣最上面的一枚開(kāi)始，重復(fù)剛才的做法。這樣一直做下去，直到這摞硬幣中的每一枚又都是正面朝上為止。輸入：僅有的一個(gè)數(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);｛翻一個(gè)硬幣｝end.k:=1halta[k+1-i]turn(k+1)inc(n)例2、求全排列(06年初賽題)

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

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

進(jìn)一步：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)輸入：一個(gè)正整數(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記錄二進(jìn)制數(shù)中從最低位開(kāi)始第一個(gè)'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.由于最后一項(xiàng)后面沒(méi)有加號(hào)，其它項(xiàng)之后有加號(hào)，因此程序中進(jìn)行了區(qū)別對(duì)待．k>0i=2try(i-1)t=1try(t-1)給出一棵二叉樹(shù)的中序與后序排列。求出它的先序排列。（約定樹(shù)結(jié)點(diǎn)用不同的大寫字母表示，長(zhǎng)度≤8）。[樣例]輸入：BADCBDCA輸出：ABCD

分析:

通過(guò)對(duì)比二叉樹(shù)的中序與后序排列，我們可以找出根節(jié)點(diǎn)及左右子樹(shù)。同樣的，也可以通過(guò)對(duì)比左子樹(shù)的中序與后序排列，找出左子樹(shù)的根節(jié)點(diǎn)……可見(jiàn)，該問(wèn)題能夠被遞歸描述。當(dāng)找到最后一個(gè)根節(jié)點(diǎn)時(shí)，遞歸無(wú)法再進(jìn)行下去，這就是遞歸結(jié)束的邊界條件。