基础7月22日pascal语言递归

递归递归概念

当过程或函数的定义中，其内部操作又直接或间接地出现对自身的调用，则称这样的程序嵌套定义为递归定义。递归是一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。例如，在数学上，所有偶数的集合可递归地定义为：①0是一个偶数；②一个偶数与2的和是一个偶数。可见，仅需两句话就能定义一个由无穷多个元素组成的集合。在程序中，递归是通过函数或过程的调用来实现的。函数或过程直接调用其自身，称为直接递归；函数或过程间接调用其自身，称为间接递归。递归应用

例1

植树节那天，有五位同学参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；…如此，都说比另一位同学多植两棵，最后问到第五位同学时，他说自己植了10棵。问第一位同学到底植了多少棵树？【分析】把原问题求第一位同学的植树棵数a1转化为a1=a2+2，即求a2；而求a2又转化为a2=a3+2;a3=a4+2;a4=a5+2逐层转化为求a2,a3,a4,a5且都采用与求a1相同的方法，最后的a5为已知值，用a5=10返回到上一层并代入计算出a4；又用a4的值代入上一层去求a3;…,如此,直到求出a1。因此：

10(x=5)Ax=Ax+1+2(x<5)其中求Ax+1

又采用求Ax

的方法。所以:①定义一个处理问题的子程序Num(x)，如果X<5就递归调用子程序Num(x+1);②当递归调用到达一定条件(X=5)，就直接执行num:=10，再执行后继语句，遇End返回到调用子程序的地方。③最后返回到开头的原问题，此时所得到的运算结果就是原问题Num(1)的答案。程序如下：Programex6_24_1; //采用函数编写Functionnum(x:integer):integer;beginifx=5thennum:=10 //递归边界

elsenum:=num(x+1)+2;//递归式end;BEGINwriteln('TheNumis',num(1));END.

利用全局变量或变参的形式，也可以传递数据，下面采用过程编写。程序如下：Programex1; //采用过程编写Vara:integer; //定义一个全局变量a，通过全局变量传递数值ProcedureNum(x:integer);//过程Num(x)求第x位同学的棵数beginifx=5thena:=10 elsebeginNum(x+1);//递归调用过程Num(x+1)a:=a+2;//求(x+1)的棵数

end;end;BEGINNum(1);//主程序调用Num(1)求第1个人的棵数

writeln(’TheNumis’,a);END.Ex6_24_2程序中的递归过程图解如下：递归方法说明如下：①调用原问题的处理子程序（过程或函数）时，调用程序应给出具体的子程序形参值（与形参结合的实参）;②在处理子问题中，如果又调用原问题的处理子程序，但形参值应是不断改变的量(表达式);③每递归调用一次自身，系统就打开一“层”与自身相同的程序系列;④由于调用参数不断改变，将使条件满足，此时就是最后一“层”，不需再调用自身，而是在本层往下执行后继语句，遇到end，就返回到上“层”调用此子程序的地方并继续往下执行，如此直到返回主程序。⑤整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。

递归算法表现出处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。例2

用递归函数求x!

1(x=0)x!=x(x-1)!(x>0)【分析】

根据数学中的定义把求x!定义为求x*(x-1)!,其中求(x-1)!仍采用求x!的方法，需要定义一个求x！的过程或函数，逐级调用此过程或函数，即：当x=0时，x!=1；当x>0时，x!=x*(x-1)！。假设用函数Fac(x)表示x的阶乘，当x=3时，Fac(3)的求解方法可表示为：

Fac(3)=3*fac(2)=3*2*Fac(1)=3*2*1*Fac(0)=3*2*1*1=6①定义函数：fac(n:integer):integer;

如果n=0，则fac:=1;如果n>0，则继续调用函数fac:=n*fac(n-1);②返回主程序，打印fac(x)的结果。它的执行流程如下图所示：Fac(3)Fac(2)Fac(1)Fac(0)3*Fac(2)2*Fac(1)1*Fac(0)Fac(0)=1Fac(3)采用函数编写程序如下：Programex2_1;Varx:integer;Functionfac(n:integer):integer; //函数fac(n)求n!beginifn=0thenfac:=1elsefac:=n*fac(n-1) //调用函数fac(n-1)递归求(n-1)!end;BEGINreadln(x);writeln(x,’!=’,fac(x));//主程序调用fac(x)求x!END.采用过程编写程序如下：Programex2_2;varx:integer;t:longint;Procedurefac(x:longint);beginifx=1thent:=1elsebeginfac(x-1);t:=t*x;end;end;BEGINread(x);fac(x);writeln(t);END.例3

用递归算法求Xn

。【分析】把Xn

分解成：

X0=1

(n=0)X1=X*X0(n=1)X2=X*X1(n>1)X3=X*X2(n>1)……(n>1)

因此将Xn

转化为：X*Xn-1，，其中求Xn-1又用求Xn

的方法进行求解。①定义子程序cf(n:integer)求Xn;如果n>1则递归调用cf(n-1)求Xn-1;②当递归调用到达n=0时终止调用,然后执行本“层”的后继语句;③遇到子程序中的END就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后继语句;④继续执行步骤③，从调用中逐“层”返回，最后返回到主程序。采用函数编写程序如下：Programex3_1; //采用函数编写varx,n:integer;Functioncf(n:integer):integer;beginifn=0thencf:=1 //递归边界

elsecf:=x*cf(n-1); //递归式end;BEGINreadln(x,n);write(x,'^',n,'is:',cf(n));END.采用过程编写程序如下：Programex3_2; //采用过程编写Vartt,x,n:integer;//利用全局变量tt传递结果Procedurecf(n:integer);//过程cf(n)求xnbeginifn=0thentt:=1elsebegincf(n-1);//递归调用过程cf(n-1)求xn-1tt:=tt*xend;end;BEGINreadln(x,n);//输入x,ncf(n);//主程序调用过程cf(n)求xnwriteln(x,’^’,n,’=‘,tt);END.例4

用递归方法求两个数m和n的最大公约数。(m>0，n>0)【分析】求两个数的最大公约数，可以用枚举因子的方法，从两者中较小的数到1枚举能被两个数同时整除且是最大的约数的方法；也可以用辗转相除法，这里采用递归实现辗转相除算法：①求X除以Y的余数;②如果余数不为0，则让X=Y，Y=余数，重复步骤①，即调用子程序;③如果余数为0，则终止调用子程序;④输出此时的Y值。采用函数编写程序如下：Programex4_1;varm,n,g:integer;Functiongcd(m,n：integer)：integer;varr:integer;beginr:=mmodn;ifr=0thengcd:=nelsegcd:=gcd(n,r);end;BEGIN //主程序

read(m,n);g:=gcd(m,n);writeln(‘m=’,m,’n=’,n,’gcd=’,g);END.采用过程编写程序如下：Programex4_2;Vara,b,d:integer;Proceduregcd(x,y:nteger);//过程beginifxmody=0thend:=y //d是用于传递结果的全局变量

elsegcd(y,xmody)//递归调用过程end;BEGINreadln(a,b);gcd(a,b);writeln(‘m=’,a,’n=’,b,’gcd=’,d);END.运行：输入12848输出m=128n=48gcd=16输入6794输出m=67n=94gcd=1例5

已知一个一维数组A[1..N](N<50)，又已知一整数M。如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。【分析】对于一个已确定的数组a[1]至a[n]和一个确定的数m，判断能否使数组a中任意几个元素之和等于m，等价于判断能否从数组a中取任意数使其和为m。此时若a[n]=m，则可以输出“YES”，否则若n=1，则可以输出“NO”。否则可以按以下规则进行判断：对于a中任意元素a[n]只有取与不取两种情况：

(１)取a[n]：则此时问题转化为：对于一个已确定的数组a[1]至a[n-1]和一个确定的数m-a[n]，判断能否使数组a中任意几个元素之和等于m-a[n]。

(２)不取a[n]：则此时问题转化为：对于一个已确定的数组a[1]至a[n-1]和一个确定的数m，判断能否使数组a中任意几个元素之和等于m。若用函数sum(n,m)表示能否从数组a[1]至a[n]中取任意数使其和为m，只要sum(n-1,m-a[n])和sum(n-1,m)当中有一个值为真，则sum(n,m)为真，否则为假。因此，可以用递归来解此题。递归终止条件为：ifa[n]=mthensum:=trueelseifn=1thensum:=false;采用函数编写程序如下：Programex5_1;Constmax=50;Vara:array[1..max]ofinteger;n,m,i:integer;Functionsum(n,m:integer):boolean;Beginifa[n]=mthensum:=trueelseifn=1thensum:=falseelsesum:=sum(n-1,m-a[n])orsum(n-1,m);End;Beginreadln(n);fori:=1tondoreadln(a[i]);readln(m);ifsum(n,m)thenwriteln('YES')elsewriteln('NO');End.采用过程编写程序如下：Programex5_2;Constmax=50;Vara:array[1..max]ofinteger;n,m,i:integer;flag:boolean;Proceduresum(n,m:integer);Beginifa[n]=mthenflag:=true ` //利用全局变量flag传递结果

elseifn=1thenexit //n=1作为递归边界，不再递归下去

elsebeginsum(n-1,m-a[n]);sum(n-1,m);end;End;Beginreadln(n);fori:=1tondoreadln(a[i]);readln(m);flag:=false;sum(n,m);ifflagthenwriteln('YES')elsewriteln('NO');End.例6：利用递归，将一个十进制整数K转化为N进制整数（N<=10）。测试数据：输入：K和N的值193输出：转化后的N进制整数201programaa;varn,k:integer;proceduretentok(k,n:integer);varr:integer;beginr:=kmodn;

k:=kdivn;ifk<>0thententok(k,n);write(r);end;beginread(k,n);tentok(k,n);writeln;end.判断运行结果1.programd1;

var

s,n:integer;

functionf(n:integer):integer;

begin

ifn=1thenf:=1

elsef:=n*n+f(n-1);

end;

begin

write('inputn:');readln(n);

s:=f(n);

writeln('f(',n,')=',s)

end.输入:inputn:3输出:练习一2．programd2;

var

a,b:integer;

functionf(n:integer):integer;

begin

ifn=1thenf:=1

elseifn=2thenf:=2

elsef:=f(n-1)+f(n-2);

end;

begin

read(a);

b:=f(a);

writeln(b);

end.输入:4输出:3．programd3;

var

a,b,c,d:integer;

procedurep(a:integer;varb:integer);

var

c:integer;

begin

a:=a+1;b:=b+1;c:=2;d:=d+1;

writeln('m',a,b,c,d);

ifa<3thenp(a,b);

writeln('n',a,b,c,d)

end;

begin

a:=1;b:=1;c:=1;d:=1;

writeln('x',a,b,c,d);

p(a,b);

writeln('y',a,b,c,d);

end.练习2:楼梯有N阶台阶，上楼可以一步上一阶，也可以一步上二阶，计算共有多少种不同走法。测试数据：输入：输入N的值6输出：走法总数13提示：N=1f(1)=1N=2f(2)=2当N>=3时f(N)=f(N-1)+f(N-2)练习1：读入一串字符倒序输出，以字符’&’为结束标志，用过程来实现。练习题递归及其应用请计算ack(m,n)的值。(m,n<=5)例1:已知:ack(m,n)函数的计算公式如下:programaa;

var

m,n:longint;

a:longint;

functionack(m,n:longint):longint;

begin

ifm=0thenack:=n+1

elseifn=0thenack:=ack(m-1,1)

elseack:=ack(m-1,ack(m,n-1))

end;

begin

read(m,n);

a:=ack(m,n);

writeln(a);

end.测试数据输入：34输出：125其Pascal程序如下：例2:用辗转相除法求两个自然数m,n的最大公约数。思路：辗转相除法规定：求两个正整数m,n（m>=n）的最大公约数，应先将m除以n；求得余数r,如果等于零，除数n就是m,n的最大公约数；如果r不等于零，就用n除以r，再看所得余数是否为零。重复上面过程，直到余数r为零时，则上一次的余数值即为m,n的最大公约数。用其数学方式描述如下:programaa;

var

m,n,t:integer;

functionf(m,n:integer):integer;

varr:integer;

begin

if(mmodn)=0thenf:=n

else

begin

r:=mmodn;

f:=f(n,r);

end;

end;begin

readln(m,n);

ifm<nthen

begin

t:=m;

m:=n;

n:=t;

end;

writeln('gd=',f(m,n));end.测试数据输入：2018输出：gd=2例3:移盘子游戏(汉诺塔问题)已知有三根针分别用1,2,3表示，在1号针中从小到大放了N个盘子，如图3.2所示，现要求把所有盘子从1针全部移到3针，移动规则是：允许使用2号针作为过渡针，每次只准移动一块盘子，且每根针上不能出现大盘子压小盘子的情况。请找出移动次数最少的移动方案。思路：假定可以通过某个过程把1针上面的N-1个盘搬到过渡针2中，然后把1针中剩下的1个盘移动到3针，然后再把过渡针2中的N-1个盘移到3针去，这样完成了移盘。思路是很明确的，我们把N个盘子移动问题转化成N-1个盘子移动问题，即如何从1针把N-1个盘子移动到2针和从2针把N-1个盘子移动到3针。同理，移N-1个盘子问题又可以进一步简化为移N-2盘子问题，这种简化过程实质就是一个递归过程。但递归过程不能永远递归下去，必须有边界条件令过程停止调用。显然，边界条件是当只有一个盘子时，仅需作最后一次移动即可。下面为移盘子游戏PASCAL程序。programaa;

var

n:integer;

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

begin

ifn=1then

writeln(a,'------>',c)

else

begin

move(n-1,a,c,b);

writeln(a,'------>',c);

move(n-1,b,a,c);

end;

end;

begin

readln(n);

move(n,1,2,3);

end.测试数据：输入:3输出:1------>31------>23------>21------>32------>12------>31------>3例4:数的计算（1）问题描述我们要求找出具有下列性质数的个数(包含输入的自然数n):先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:1、不作任何处理;2、在它的左边加上一个自然数,但该自然数不能超过原数的一半;3、加上数后,继续按此规则进行处理,直到不能再加自然数为止.样例:

输入:

6

满足条件的数为

6(此部分不必输出)