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

第二章遞歸

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

遞歸的概念

概念

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

procedurea;begin

.

.

.

a;

.

.

.

end;

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

procedure b; procedurec;begin begin

. .

. .

. .

c; b;

. .

. .

. .

end; end;

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

例1計(jì)算n!可用遞歸如下:

1 當(dāng)n=0時(shí)

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

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階臺(tái)階,上樓可以一步上1階,也可以一步上2階,編一程序計(jì)算共有多少種不同的走法.

設(shè)n階臺(tái)階的走法數(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è)計(jì)遞歸算法

確定遞歸

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

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

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

+2+3+...+n

求n個(gè)整數(shù)的積

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

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

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

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

典型例題

例3梵塔問題

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

不能出現(xiàn)大盤壓小盤.找出移動(dòng)次數(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ù)序列中選一個(gè)元素,并將序列中所有比該元素小的元素都放到它的右邊或左邊,再對(duì)左右兩邊分別用同樣的方法處之直到每一個(gè)待處理的序列的長度為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