預(yù)備知識遞歸介紹及應(yīng)用

第二章遞歸

遞歸是計算機科學(xué)的一個重要概念,遞歸的方法是程序設(shè)計中有效的方法,采用遞歸編寫程序能是程序變得簡潔和清晰.

遞歸的概念

概念

一個過程(或函數(shù))直接或間接調(diào)用自己本身,這種過程(或函數(shù))叫遞歸過程(或函數(shù)).如:

procedurea;begin

.

.

.

a;

.

.

.

end;

這種方式是直接調(diào)用.又如:

procedure b; procedurec;begin begin

. .

. .

. .

c; b;

. .

. .

. .

end; end;

這種方式是間接調(diào)用.

例1計算n!可用遞歸如下:

1 當(dāng)n=0時

fac(n)={n*fac(n-1)當(dāng)n>0時可編寫程序如下:

programfac2;varn:integer;

functionfac(n:integer):real;begin

ifn=0thenfac:=1elsefac:=n*fac(n-1)

end;begin

write('n=');readln(n);wrin('fac(',n,')=',fac(n):6:0);end.

例2樓梯有n階臺階,上樓可以一步上1階,也可以一步上2階,編一程序計算共有多少種不同的走法.

設(shè)n階臺階的走法數(shù)為f(n)

顯然有

f(n)={2 n=2

可編程序如下：programlouti;varn:integer;

1 n=1

f(n-1)+f(n-2) n>2

functionf(x:integer):integer;begin

ifx=1thenf:=1else

ifx=2thenf:=2elsef:=f(x-1)+f(x-2);end;

beginwrite('n=');read(n);wrin('f(',n,')=',f(n))end.

如何設(shè)計遞歸算法

確定遞歸

確定邊界(終了)條件練習(xí):

用遞歸的方法完成下列問題

1.求數(shù)組中的最大數(shù)

+2+3+...+n

求n個整數(shù)的積

求n個整數(shù)的平均值

求n個自然數(shù)的最大公約數(shù)與最小公倍數(shù)

有一對雌雄兔,每兩個月就繁殖雌雄各一對兔子.問n個月后共有多少對兔子?

已知:數(shù)列1,1,2,4,7,13,24,44,...求數(shù)列的第n項.

典型例題

例3梵塔問題

如圖:已知有三根針分別用1,2,3表示,在一號針中從小放n個盤子,現(xiàn)要求把所有的盤子從1針全部移到3針,移動規(guī)則是:使用2針作為過度針,每次只移動一塊盤子,且每根針上

不能出現(xiàn)大盤壓小盤.找出移動次數(shù)最小的方案.

程序如下:

programfanta;var

n:integer;

proceduremove(n,a,b,c:integer);begin

ifn=1thenwrin(a,'--->',c)elsebegin

move(n-1,a,c,b);wrin(a,'--->',c);move(n-1,b,a,c);end;

end;begin

write('Entern=');read(n);move(n,1,2,3);end.

例4快速排序

快速排序的思想是:先從數(shù)據(jù)序列中選一個元素,并將序列中所有比該元素小的元素都放到它的右邊或左邊,再對左右兩邊分別用同樣的方法處之直到每一個待處理的序列的長度為1,處理結(jié)束.

程序如下:

programkspv;constn=7;type

arr=array[1..n]ofinteger;var

a:arr;i:integer;

procedurequicksort(varb:arr;s,t:integer);vari,j,x,t1:integer;

begini:=s;j:=t;x:=b[i];repeat

while(b[j]>=x)and(j>i)doj:=j-1;

ifj>ithenbegint1:=b[i];b[i]:=b[j];b[j]:=t1;end;while(b[i]<=x)and(i<j)doi:=i+1;

ifi<jthenbegint1:=b[j];b[j]:=b[i];b[i]:=t1;enduntili=j;

b[i]:=x;

i:=i+1;j:=j-1;

ifs<jthenquicksort(b,s,j);ifi<tthenquicksort(b,i,t);

end;begin

write('inputdata:');

fori:=1tondoread(a[i]);wrin;

quicksort(a,1,n);write('outputdata:');

fori:=1tondowrite(a[i]:6);wrin;

e