子程序的递归与嵌套

子程序的递归与嵌套第1页，课件共27页，创作于2023年2月1、复习函数与过程——子程序子程序的定义定义位置如何定义？子程序的调用在何处调用？如何调用？参数的传递值传递，地址传递变量的作用域全局，局部子程序如何返回值到调用处函数通过函数名带回值子程序可通过变量参数和全局变量的方式带回值到调用处第2页，课件共27页，创作于2023年2月【例1】：输入一个正整数，如果是回文素数则输出“Yes”，否则输出“No”【分析】定义两个并列关系的函数，分别判断一个数是否为素数和是否为回文数教材P93例5-11第3页，课件共27页，创作于2023年2月注意：1）内、外层子程序不得相互交叉，内层必须完全嵌套在外层之中；2）一般情况下，在子程序内部需要使用的变量应在子程序的内部进行定义。外层子程序不能访问内层子程序所定义的变量。【例2】：求组合数的和。vars:real;functioncnm(n,m:integer):real;functionfac(k:integer):longint;vari:integer;t:real;begint:=1;fori:=2tokdot:=t*i;fac:=t;end;begincnm:=fac(n)/(fac(m)*fac(n-m));end;begins:=cnm(6,3)+cnm(9,5);writeln(‘s=’,s:8:2);end.2、子程序的嵌套：第4页，课件共27页，创作于2023年2月functionfac(k:integer):longint;vari:integer;t:real;begint:=1;fori:=2tokdot:=t*i;fac:=t;end;functioncnm(n,m:integer):real;begincnm:=fac(n)/(fac(m)*fac(n-m));end;functionfac(k:integer):longint;Forward；functioncnm(n,m:integer):real;begincnm:=fac(n)/(fac(m)*fac(n-m));end;functionfac(k:integer):real;vari:integer;t:real;begint:=1;fori:=2tokdot:=t*i;fac:=t;end;超前引用第5页，课件共27页，创作于2023年2月【例3】：求组合数（）/7！的和。vars:real;functionfac(k:integer):longint;vari:integer;t:longint;begint:=1;fori:=2tokdot:=t*i;fac:=t;end;functioncnm(n,m:integer):real;begincnm:=fac(n)/(fac(m)*fac(n-m));end;begins:=cnm(6,3)+cnm(9,5);writeln(‘s=’,(s/fac(7)):8:2);end.学校举行晚会，要从M个学生中选N个学生到舞台上表演一个游戏，问有多少种选择方法。这是数学中的组合运算，可用下列公式计算：第6页，课件共27页，创作于2023年2月3.递归调用：①递归的定义：

Pascal语言中，如果在一个函数、过程等的定义或说明内部又直接或间接地出现有对自身的引用，则称它们是递归的或者是递归定义的。例如：在数学上，所有偶数的集合可递归地定义为：0是一个偶数；一个偶数和2的和是一个偶数。可见，仅需两句话就能定义一个由无穷多个元素组成的集合。②递归的实现：通过函数或过程的调用来实现。函数或过程直接调用其自身，称为直接递归；函数或过程间接调用其自身，称为间接递归。直接递归间接递归第7页，课件共27页，创作于2023年2月递归应用

【例5】、植树节那天，有五位同学参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；…如此，都说比另一位同学多植两棵，最后问到第五位同学时，他说自己植了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)的答案。第8页，课件共27页，创作于2023年2月程序如下：Programex5; Functionnum(x:integer):integer;//采用函数编写beginifx=5thennum:=10 //递归边界

elsenum:=num(x+1)+2;//递归式end;BEGINwriteln('TheNumis',num(1));END.程序执行过程？【例6】、猴子吃枣问题：猴子摘了一堆枣，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天，又吃了剩下的一半零一个；以后每天如此。到第十天，猴子一看只剩下一个了。问最初有多少个枣子？要求：写出递推表达式，尝试用递推函数编写程序第9页，课件共27页，创作于2023年2月课堂练习1、programlx1(input,output);vars,n:integer;functionf(n:integer):integer;

begin

ifn=1thenf:=1elsef:=n*n+f(n-1)

end;begin

write(‘inputn:’);readln(n);s:=f(n);writeln(‘f(’,n,‘)=’,s)end.该程序的功能是：

。当n的值为６时，程序的运行结果是：

第10页，课件共27页，创作于2023年2月②在处理子问题时，如果又调用原问题的处理子程序，但形参值应是不断改变的量(表达式);递归方法说明如下：①调用原问题的子程序（过程或函数）时，调用程序应给出具体的子程序形参值（与形参结合的实参）;递归算法表现出处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。⑤整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。④由于调用参数不断改变，将使条件满足，此时就是最后一“层”，不需再调用自身，而是在本层往下执行后继语句，遇到end，就返回到上“层”调用此子程序的地方并继续往下执行，如此直到返回主程序③每递归调用一次自身，系统就打开一“层”与自身相同的程序系列;第11页，课件共27页，创作于2023年2月如何设计递归算法？1.确定递归公式2.确定边界(终了)条件课堂练习2：求：1+2+3+...+n的值。n从键盘上输入。有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?用递归的方法求Xn（X和n由键盘输入）已知:数列1,1,2,4,7,13,24,44,...求数列的第n项.第12页，课件共27页，创作于2023年2月n!1n=0n(n-1)!n>0【例7】：用递归计算n!n!可以由下面公式表示：varn,s:integer;functionfac(a:integer):integer;beginifa=0thenfac:=1elsefac:=a*fac(a-1);end;beginreadln(n);s:=fac(n);writeln(n,‘!=’,s)end.使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的、规模较小的问题进行求解，最终达到对原问题的求解。第13页，课件共27页，创作于2023年2月栈……fac(5)=5*……fac(5)=5*fac(4)=4*fac(3)=3*……fac(5)=5*fac(4)=4*……fac(5)=5*fac(4)=4*fac(3)=3*fac(2)=2*fac(5)=5*fac(4)=4*fac(3)=3*fac(2)=2*fac(1)=1*fac(5)=5*fac(4)=4*fac(3)=3*fac(2)=2*fac(0)=1fac(1)=1*第14页，课件共27页，创作于2023年2月递归过程【例8】：把一个十进制整数转换成K进制数(k<10)。Knumber8157819820532第15页，课件共27页，创作于2023年2月分析根据数制转换规则，把一个十进制整数转换成K进制数，要用“除K取余”法。也就是用K依次去除这个数及其商，所得余数依次作为K进制数相继的低位数字，一直到商为0即可。如果我们不用数组存储每次求得的低位数字，怎么让程序按顺序输出K进制的各位数字？第16页，课件共27页，创作于2023年2月分析可以用递归的方法实现这一过程。算法过程tentok(number,k)如下：步一digitnumbermodk;步二numbernumberdivk步三如果number不为0则调用

tentok(number,k)步四输出digit第17页，课件共27页，创作于2023年2月参考程序：programconvert(input,output);varnumber,k:integer;proceduretentok(number,k:Integer);vardigit:integer;begindigit:=numbermodk;number:=numberdivk;ifnumber<>0thententok(number,k);write(digit);end;beginwrite('Enternumberandconvertedbasisk(2-9):');readln(number,k);tentok(number,k);writeln;end.第18页，课件共27页，创作于2023年2月执行过程分析第2次调用digit=3number=2tentok(2,8)第1次调用digit=5number=19tentok(19,8)Tentok(157,8)第3次调用digit=2number=0write(digit)write(digit)write(digit)Knumber8157819820532第19页，课件共27页，创作于2023年2月递归结构的优点：结构清晰、容易阅读和理解。递归结构的缺点：需要保留每次递归调用时的参数和局部变量，占用内存大，耗费机时多，程序运行的效率较低。递归算法的实用情况：1.符合递归的描述：需要解决的问题可以化为子问题求解，而子问题求解的方法与原问题相同，只是数量增大或减少。2.递归调用的次数是有限的。3.必须有递归结束的条件。第20页，课件共27页，创作于2023年2月例9、汉诺塔问题有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。在移动盘子的过程当中发现要搬动n个盘子，必须先将n-1个盘子从A柱搬到B柱去，再将A柱上的最后一个盘子搬到C柱，最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。源柱工作柱目标柱ABC第21页，课件共27页，创作于2023年2月vara,b,c,number:integer;proceduremove(n:integer;a,b,c:char);begin

ifn=1thenwriteln(a,'->',c)

else

begin

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

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

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

end;end;begin

write('thenumberofdish:');

readln(number);

move(number,’A’,’B’,’C’);end.第22页，课件共27页，创作于2023年2月【例10】求找出具有下列性质的数的个数(包含输入的自然数n)：先输入一个自然数n(n<=500),然后对此自然数按照如下方法进行处理:①.不作任何处理;②.在它的左边加上一个自然数,但该自然数不能超过原数的一半;③.加上数后,继续按此规则进行处理,直到不能再加自然数为止.样例:

输入:

6满足条件的数为

6

16

26

126

36

136输出:

6

varn,i:integer;

s:real;procedureqiu(x:integer);vark:integer;begin

ifx<>0then

begin

s:=s+1;

fork:=1toxdiv2doqiu(k)

endend;begin

readln(n);

s:=0;

qiu(n);

writeln(s:2:0)end.第23页，课件共27页，创作于2023年2月【例11】、求m与n的最大公约数分析：从数学上可以知道求m与n的最大公约数等价于求n与(mmodn)的最大公约数。这时可以把n当作新的m,(mmodn)当作新的n，这样问题又变成了求新的m与n的最大公约数……这种方法我们称为辗转相除法。设两个整数分别为m和n，将m整除n得到一个余数r，若r=0，则除数n就是最大公约数，否则，将除数作为被除数，余数作为除数继续相除，直到余数=0为止。

Var

m,n:integer;

functiongys(a,b:integer):integer;

var

r:integer;

begin

r:=amodb;

ifr=0thengys:b

elsegys:=gys(b,r);

end;

begin

readln(m,n);

writeln(‘gysis:’,gys(m,n));

end.第24页，课件共27页，创作于2023年2月【分析】对于一个已确定的数组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