遞歸一個函數或過程直接或間接調用它本身。例：用遞歸計算n!.1n=0n!=n*(n-1)!n>0Functionfac(n:integer):real;Beginifn=0thenfac:=1elsefac:=n*fac(n-1)End;定義函數fac:Programfacn(input,output);Varn:integer;y:real;functionfac(n:integer):real;beginifn=0thenfac:=1elsefac:=n*fac(n-1)end;Beginread(n);y:=fac(n);writeln(n,’!=‘,y)End.執行過程：（以fac(3)為例）Fac(3)第四次調用n=01*fac(0)返回值6返回值2返回值1返回值1第一次調用N=33*fac(2)第二次調用第三次調用n=2n=12*fac(1)Fac(3)=3*fac(2)=3*2*fac(1)=3*2*1*fac(0)=3*2*1*1求m與n的最大公約數。

（用輾轉相除法）

數學知識已知：m,n的最大公約數等價于求n與（mmodn）的最大公約數。mn=0gcd(m,n)=gcd(n,mmodn)n>0Functiongcd(m,n:integer):integer;beginifn=0thengcd:=melsegcd:=gcd(n,mmodn)end;Programgmn(input,output);Varm,n,g:integer;Beginread(m,n);g:=gcd(m,n);writeln(‘m=‘,m,’n=‘,n,’gcd=‘,g)End.漢諾塔游戲：n=64源中間目標ABC漢諾塔游戲：n=1源中間目標ABC漢諾塔游戲：n=2源中間目標ABC漢諾塔游戲：n=3源中間目標ABC思路:1.先把上面63個盤子從A柱子移到B柱子（借助C柱子）2.把第64個盤子從A柱子移到C號柱子.3.把63個盤子從B柱子移到C號柱子（借助A柱子）4.當只乘下一個盤子時,直接移到3號柱子.

把將n個盤子從a經b移到c這一動作定義成一個過程move:Move(64,a,b,c),整個處理過程可描述為:Move(63,a,c,b)ACMove(63,b,a,c)N=1falsetrueMove(n-1,a,c,b);Writeln(a,’’,c);Move(n-1,b,a,c)Writeln(a,’’,c)輸入盤子總數total;Move(total,1,2,3)主程序：子程序move:例：求total=3Move(3,1,2,3)Move(n,a,b,c)n=3a=1b=2c=3Move(2,1,3,2)Writeln(1,’

’,3)Move(2,2,1,3)n=2a=1b=3c=2Move(1,1,2,3)Writeln(1,’

’,2)Move(1,3,1,2)n=1a=1b=2c=3Writeln(1,’

’,3)n=1a=3b=1c=2Writeln(3,’

’,2)n=2a=2b=1c=3Writeln(2,’

’,3)Move(1,2,3,1)Move(1,1,2,3)n=1a=2b=3c=1Writeln(2,’

’,1)n=1a=1b=2c=3Writeln(1,’

’,3)1

31

23

21

32

12

31

3Programhanoi(input,output);Vartotal:integer;

proceduremove(n,a,b,c:integer);beginifn=1thenwriteln(a,’->’,c)elsebeginmove(n-1,a,c,b);writeln(a,’-->’,c);move(n-1,b,a,c)end;end;Beginread(total);move(total,1,2,3)End.練習：1、順序讀入字符，以‘？’結束，然后以和輸入相反的次序輸出讀入的字符，用遞歸過程作。2、求菲波拉契數列的第10項和第20項的值。已知：

a0=0a1=1A2=a0+a1A3=a1+a2A4=a2+a3programas;varch:char;procedures;varch1:char;beginread(ch1);ifch1<>'?'thens;ifch1<>'?'thenwrite(ch1)end;begins;writeln;end.programas;functiond(x:integer):longint;beginifx=0thend:=0elseifx=1thend:=1elsed:=d(x-2)+d(x-1)end;beginwriteln(d(10),d(20):10);end.二.遞推遞推是迭代算法中一種用若干步可重復的簡單運算來描述復雜數學問題的方法。例如求階乘的算法；在求階乘的算法中，存在如下的遞推公式：f(0)=0!=1f(1)=1*0!=1f(2)=2*1!=2f(3)=3*2!=6……f(n)=n*(n-1)!=n*f(n-1)

遞推的特點：可以從初始條件出發，應用遞推公式逐個求出其它的值。建立遞推公式的關鍵在于找到第n項與第n+1項的關系以及初始項的值。

a1=aan+1=f(an)兔子繁殖問題

有一對小兔，過一個月后長成大兔，到第三個月就可以生下一對小兔，并且以后每個月都生下一對小兔，而所生的小兔也同樣到一個月之后長成大兔，到第三個月就可以生下一對小兔，并且以后也每個月都生下一對小兔。假設所有的兔子一年內均不死亡，問一年后共有多少對兔子？分析：每個月的兔子都可分成二類：1001112

3

21小兔大兔ababbb+aaaaaa

1;b

0;Month1whilemonth<12doaaa;ab;bb+aamonthmonth+1to