遞推與遞歸算法

遞推與遞歸算法遞推和遞歸是編程中常用的基本算法。在前面的解題中已經(jīng)用到了這兩種方法，下面對這兩種算法基本應(yīng)用進行詳細研究討論。一、遞推遞推算法是一種用若干步可重復(fù)的簡單運算（規(guī)律）來描述復(fù)雜問題的方法。［例1］植樹節(jié)那天，有五位參加了植樹活動，他們完成植樹的棵數(shù)都不相同。問第一位同學(xué)植了多少棵時，他指著旁邊的第二位同學(xué)說比他多植了兩棵；追問第二位同學(xué)，他又說比第三位同學(xué)多植了兩棵；…如此，都說比另一位同學(xué)多植兩棵。最后問到第五位同學(xué)時，他說自己植了10棵。到底第一位同學(xué)植了多少棵樹？解：設(shè)第一位同學(xué)植樹的棵數(shù)為al，欲求al，需從第五位同學(xué)植樹的棵數(shù)a5入手，根據(jù)“多兩棵”這個規(guī)律，按照一定順序逐步進行推算：a5=10;a4=a5+2=12;a3=a4+2=14;a2=a3+2=16;a1=a2+2=18;Pascal程序：ProgramExam1;Vari,a:byte;begina:=10;｛以第五位同學(xué)的棵數(shù)為遞推的起始值｝fori:=1to4do｛還有4人，遞推計算4次｝a:=a+2;｛遞推運算規(guī)律｝writeln（’TheNumis’，a）;readlnend.本程序的遞推運算可用如下圖示描述:初始值i=l■a=a+2i=2,a=a+2i=3-a=a+2i=4a=a+2a：-10(12)(14)(16)a?遞推算法以初始｛起點｝值為基礎(chǔ)，用相同的運算規(guī)律，逐次重復(fù)運算，直至運算結(jié)束。這種從“起點”重復(fù)相同的方法直至到達一定“邊界”，猶如單向運動，用循環(huán)可以實現(xiàn)。遞推的本質(zhì)是按規(guī)律逐次推出（計算）下一步的結(jié)果。二、遞歸遞歸算法是把處理問題的方法定義成與原問題處理方法相同的過程，在處理問題的過程中又調(diào)用自身定義的函數(shù)或過程。仍用上例的計算植樹棵數(shù)問題來說明遞歸算法：解：把原問題求第一位同學(xué)在植樹棵數(shù)al,轉(zhuǎn)化為a1=a2+2;即求a2；而求a2又轉(zhuǎn)化為a2=a3+2;a3=a4+2;a4=a5+2;逐層轉(zhuǎn)化為求a2,a3,a4,a5且都采用與求al相同的方法；最后的a5為已知，則用a5=10返回到上一層并代入計算出a4；又用a4的值代入上一層去求a3;...,如此，直到求出al。因此：(10ts=5)a^i+2fe<5)其中求ax+i又采用求氣的方法。所以：定義一個處理問題的過程Num(x)：如果X<5就遞歸調(diào)用過程Num(x+1);當(dāng)遞歸調(diào)用到達一定條件(X=5)，就直接執(zhí)行a:=10，再執(zhí)行后繼語句，遇End返回到調(diào)用本過程的地方，將帶回的計算結(jié)果(值)參與此處的后繼語句進行運算(a:=a+2);最后返回到開頭的原問題，此時所得到的運算結(jié)果就是原問題Num(1)的答案。Pascal程序：ProgramExam1_1;Vara:byte;ProcedureNum(x:integer);｛過程Num(x)求x的棵數(shù)｝beginifx=5thena:=10elsebeginNum(x+1);｛遞歸調(diào)用過程Num(x+1)｝a:=a+2｛求(x+1)的棵數(shù)｝endend;beginNum⑴；｛主程序調(diào)用Num⑴求第1個人的棵數(shù)｝writeln(’TheNumis’，a);readlnend.程序中的遞歸過程圖解如下:參照圖示，遞歸方法說明如下：調(diào)用原問題的處理過程時，調(diào)用程序應(yīng)給出具體的過程形參值(數(shù)據(jù))；在處理子問題中，如果又調(diào)用原問題的處理過程，但形參值應(yīng)是不斷改變的量(表達式)；每遞歸調(diào)用一次自身過程，系統(tǒng)就打開一“層”與自身相同的程序系列；由于調(diào)用參數(shù)不斷改變，將使條件滿足(達到一定邊界)，此時就是最后一“層”，不需再調(diào)用(打開新層)，而是往下執(zhí)行后繼語句，給出邊界值，遇到本過程的END，就返回到上“層”調(diào)用此過程的地方并繼續(xù)往下執(zhí)行；整個遞歸過程可視為由往返雙向“運動”組成，先是逐層遞進，逐層打開新的“篇章”，(有可能無具體計算值)當(dāng)最終遞進達到邊界，執(zhí)行完本“層”的語句，才由最末一“層”逐次返回到上“層”，每次返回均帶回新的計算值，直至回到第一次由主程序調(diào)用的地方，完成對原問題的處理。［例2］用遞歸算法求Xn。解：把Xn分解成：X0=1(n=0)Xi=X*X0(n=1)X2=X*X1(n>1)X3=X*X2(n>1)(n>1)Xn=X*Xn-1(n>1)因此將Xn轉(zhuǎn)化為：其中求Xn-1又用求Xn的方法進行求解。定義過程xn(x,n:integer)求Xn；如果n>1則遞歸調(diào)用xn(x,n-1)求Xn—1；當(dāng)遞歸調(diào)用到達n=0，就執(zhí)行tt:=1,然后執(zhí)行本“層”的后繼語句；遇到過程的END就結(jié)束本次的調(diào)用，返回到上一“層”調(diào)用語句的地方，并執(zhí)行其后續(xù)語句tt:=tt*x;繼續(xù)執(zhí)行步驟③，從調(diào)用中逐“層”返回，最后返回到主程序，輸出tt的值。Pascal程序：ProgramExam2;Vartt,a,b:integer;Procedurexn(x,n:integer);{過程xn(x,n)求xn}beginifn=0thentt:=1elsebeginxn(x,n-1);{遞歸調(diào)用過xn(x,n-1)求xn-1}tt:=tt*xend;end;beginwrite(’inputx,n:’)；readln(a,b);{輸入a,b}xn(a,b);{主程序調(diào)用過程xn(a,b)求ab}writeln(a,’、，b,’=‘，tt);readlnend.遞歸算法，常常是把解決原問題按順序逐次調(diào)用同一“子程序”(過程)去處理，最后一次調(diào)用得到已知數(shù)據(jù)，執(zhí)行完該次調(diào)用過程的處理，將結(jié)果帶回，按“先進后出”原則，依次計算返回。如果處理問題的結(jié)果只需返回一個確定的計算值，可定義成遞歸函數(shù)。f1(X=l4—X(Z-1)\(z>［例3］用遞歸函數(shù)求x!解：根據(jù)數(shù)學(xué)中的定義把求x!定義為求x*(x-1)!,其中求(x-1)!仍采用求x!的方法，需要定義一個求a!的過程或函數(shù)，逐級調(diào)用此過程或函數(shù)，即：(x-1)!=(x-1)*(x-2)!;(x-2)!=(x-2)*(x-3)!;直到x=0時給出0!=1，才開始逐級返回并計算各值。定義遞歸函數(shù)：fac(a:integer):integer;如果a=0，則fac:=1;如果a>0，則調(diào)用函數(shù)fac:=fac(a-1)*a;返回主程序，打印fac(x)的結(jié)果。Pascal程序：ProgramExam3;Varx:integer;functionfac(a:integer):integer;｛函數(shù)fac(a)求a!｝beginifa=0thenfac:=1elsefac:=fac(a-1)*a｛函數(shù)fac(a-1)遞歸求(a-1)!｝end;beginwrite(’inputx’)；readln(x);writeln(x,’！=’，fac(x));｛主程序調(diào)用fac(x)求x!｝readlnend.遞歸算法表現(xiàn)在處理問題的強大能力。然而，如同循環(huán)一樣，遞歸也會帶來無終止調(diào)用的可能性，因此，在設(shè)計遞歸過程(函數(shù))時，必須考慮遞歸調(diào)用的終止問題，就是遞歸調(diào)用要受限于某一條件，而且要保證這個條件在一定情況下肯定能得到滿足。［例4］用遞歸算求自然數(shù)A，B的最大公約數(shù)。解：求最大公約數(shù)的方法有許多種，若用歐幾里德發(fā)明的輾轉(zhuǎn)相除方法如下：定義求X除以Y的余數(shù)的過程；如果余數(shù)不為0，則讓X=Y，Y=余數(shù)，重復(fù)步驟①，即調(diào)用過程；如果余數(shù)為0，則終止調(diào)用過程；輸出此時的Y值。Pascal程序：ProgramExam4;Vara,b,d:integer;ProcedureGdd(x,y:nteger);｛過程｝beginifxmody=0thend:=yelseGdd(y,xmody)｛遞歸調(diào)用過程｝end;beginwrite(’inputa,b=’);readln(a,b);Gdd(a,b);writeln(’(’，a,’，’，b,’)=’，d);readlnend.簡單地說，遞歸算法的本質(zhì)就是自己調(diào)用自己，用調(diào)用自己的方法去處理問題，可使解決問題變得簡潔明了。按正常情況有幾次調(diào)用，就有幾次返回。但有些程序可以只進行遞歸處理，不一定要返回時才進行所需要的處理。［例5］移梵塔。有三根柱A，B，C在柱A上有N塊盤片，所有盤片都是大的在下面，小片能放在大片上面?，F(xiàn)要將A上的N塊片移到C柱上，每次只能移動一片，而且在同一根柱子上必須保持上面的盤片比下面的盤片小，請輸出移動方法。解：先考慮簡單情形。如果N=3，則具體移動步驟為：

,假設(shè)把第3步視為一片)：第4步，第6步抽出來就相當(dāng)于N=2的情況(把上面2片捆在一起，記為（A,C,BJ2抄蔑將A柱上的(NT)片移到B上,3.將B上的(N-1)片移到C上,結(jié)束.[B,假設(shè)把第3步視為一片)：第4步，第6步抽出來就相當(dāng)于N=2的情況(把上面2片捆在一起，記為（A,C,BJ2抄蔑將A柱上的(NT)片移到B上,所以可按“N=2”的移動步驟設(shè)計：如果N=0，則退出，即結(jié)束程序；否則繼續(xù)往下執(zhí)行；用C柱作為協(xié)助過渡，將A柱上的(N-1)片移到B柱上，調(diào)用過程sub(n-1,a,b,c);將A柱上剩下的一片直接移到C柱上；用A柱作為協(xié)助過渡，將B柱上的(N-1)移到C柱上，調(diào)用過程sub(n-1,b,c,a)。Pascal程序：ProgramExam65;Varx,y,z:char;N,k:integer;Proceduresub(n:integer;a,c,b:char);beginifn=0thenexit;sub(n-1,a,b,c);inc(k);writeln(k,’：from’，a,’一>’，c);sub(n-1,b,c,a);end;beginwrite(’n=’;readln(n);k:=0;x:=’A’；y:=’B’；Z:=’C’；sub(n,x,z,y);readlnend.程序定義了把n片從A柱移到C柱的過程sub(n,a,c,b)，這個過程把移動分為以下三步來進行：先調(diào)用過程sub(n-1,a,b,c)，把(n-1)片從A