介绍递归

大榕树 \ Pascal语言 \ 算法与技巧

介绍递归

原文链接：http://www.mydrs.org/program/list.asp?id=37
递归
将复杂的处理归纳为较简单的处理，直到最简单的处理。
基础为归纳，即通过观察，得到3个内容： 1、递归的形式；
　　　　　　　　　　　　　　　　　　　2、最基本式是否有解决的方案；
　　　　　　　　　　　　　　　　　　　3、递归终止的条件例子
1 某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封共有多少种不同情况。归纳法例子 1.有n个硬币（n为偶数）正面朝上排成一排，每次将n-1个硬币翻成朝上为止。编程让计算机把翻硬币的最简过程及翻币次数打印出来（用*代表正面，用0代表反面）。
基本形式：D[1]=0;d[2]=1
递归式：d[n]= (n-1)*( d[n-1] + d[n-2])
program lettter;
　var n:integer;
　function d(n:integer):longint;
　　begin
　　　case n of
　　　　1:d:=0;
　　　　2:d:=1;
　　　else d:=(n-1)*(d(n-1)+d(n-2));
　　　end;
　　end;
　begin
　　repeat
　　　write('n=');
　　　readln(n);
　　　if n<=0 then writeln('Once more!')
　　until n>0;
　　　writeln('d=',d(n));
　　　readln;
　end.
2 有一对雌雄兔子，假定两个月便可以繁殖雌雄各一对兔子。问n各月后共有多少对兔子？
递归的三要素：
递归的形式：T[n]= T[n-1]+ T[n-2]
基本：T[1]=1，T[2]=1
结束条件：n个月
program rabbit;
　var n:integer;
　function fa(n:integer):integer;
　　begin
　　　if n<3 then fa:=1
　　　　else fa:=fa(n-1)+fa(n-2);
　　　end;
　　begin
　　　write('n=');readln(n);
　　　writeln('The number of the rabbits:',fa(n));
　　end.
3 梯有N阶，上楼可以一步上一价，也可以一次上二阶。编一个程序，计算共有多少种不同的走法。
递归的形式：s[n]=s[n-1]+s[n-2]
基本式子：s[1]=1;s[2]=2
program upstairs;
　var n:integer;
　function s(n:integer):longint;
　　begin
　　　if (n=1)or(n=2) then s:=n
　　　　　else s:=s(n-1)+s(n-2);
　　end;
　　begin
　　　repeat
　　　write('N=');readln(n);
　　　until n>0;
　　　writeln('s=',s(n));
　　　readln;
　　end.
4 设有2^n个运动员要进行网球比赛。现要设计一个满足以下要求的比赛日程表：
（1）、每个选手必须与其他n-1个选手各赛一次；
（2）、每个选手每天只能参赛一次；
（3）、循环赛在n-1天内结束。program match;
　const k=3;n=8;
　var
　　s:array[1..n,1..n] of integer;
　　i,j,p:integer;
　　ju:boolean;
　procedure copy1(be,en:integer;jug:boolean;q:integer);
　　var m,t,ban:integer;
　　begin
　　　if jug then
　　　　begin
　　　　　if be=1 then
　　　　　　begin if s[en,en]=0 then
　　　　　　　　　begin copy1(be,en div 2,true,q div 2);
　　　　　　　　　　copy1((en div 2)+1,en,false,q div 2);
　　　　　　　　　end;
　　　　　　　for m:=1 to en do
　　　　　　　　for t:=1 to en do
　　　　　　　　　s[m+q,t+q]:=s[m,t]
　　　　　　end
　　　　　else begin if s[be+q-1,q]=0 then
　　　　　　　　　　begin copy1(be,be+(q div 2)-1,true,q div 2);
　　　　　　　　　　　copy1(be+(q div 2),en,false,q div 2)
　　　　　　　　　　end;
　　　　　　　　　for m:=be to en do
　　　　　　　　　　for t:=1 to q do
　　　　　　　　　　　s[m+q,t+q]:=s[m,t]
　　　　　　　end
　　　　　end
　　　else begin
　　　　　　if s[be,q]=0 then
　　　　　　begin copy1(be,be+(q div 2)-1,true,q div 2);
　　　　　　　copy1(be+(q div 2),en,false,q div 2)
　　　　　　end;
　　　　　　for m:=be to en do
　　　　　　　for t:=1 to q do
　　　　　　　　s[m-q,t+q]:=s[m,t]
　　　　　end
　　end;
begin
　p:=8;
　for i:=1 to n do
　　for j:=1 to n do
　　　s[i,j]:=0;
　　for i:=1 to n do
　　　begin
　　　　s[i,1]:=i;
　　　　if odd(i) then s[i+1,2]:=s[i,1]
　　　　　else s[i-1,2]:=s[i,1];
　　　end;
　　copy1(1,n div 2,true,p div 2);
　　copy1((n div 2)+1,n,false,p div 2);
　　for i:=1 to n do
　　　begin
　　　　for j:=1 to n do
　　　　　write(s[i,j],' ');
　　　　writeln;
　　　end;
end.
思考题 1、数学宝塔，从最顶上走到最底层，每次只能走到下一层的左边或右边的数字，求出使所走到的所有数字之和为60的途径。
　　　　　　　　7
　　　　　　　4　　6
　　　　　　6　　9　　3
　　　　　6　　3　　7　　1
　　　　2　　5　　3　　2　　8
　　　5　　9　　4　　7　　 3　　2
　　6　　4　　1　　8　　5　　6　　3
　3　　9　　7　　6　　8　　4　　1　　5
2　　5　　7　　3　　5　　7　　8　　4　　2
2、汉诺塔问题：设有三个塔座，依次命名为x,y,z。有z个直径不同的圆盘，由小到大依次编号为1、2、……，n。开始时，它们全部按递减的次序插在塔座上。现要求按下列规则把n个圆盘按次序插放在z塔座上。
（1）、每次只能移动一个圆盘；
（2）、圆盘可以从任一个塔座上移到另一个塔座上；
（3）、任何时刻都不能把一个较大的圆盘压在较小的圆盘上。

作者：周飞
来源：
时间：2001-06-06

上一篇：二级PASCAL考试大纲
下一篇：介绍回溯