子程序的递归与嵌套.ppt

子程序的嵌套与递归,1、复习函数与过程子程序,子程序的定义定义位置如何定义？子程序的调用在何处调用？如何调用？参数的传递值传递，地址传递变量的作用域全局，局部子程序如何返回值到调用处函数通过函数名带回值子程序可通过变量参数和全局变量的方式带回值到调用处,【例1】：输入一个正整数，如果是回文素数则输出“Yes”，否则输出“No”,【分析】定义两个并列关系的函数，分别判断一个数是否为素数和是否为回文数教材P93例5-11,注意：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、子程序的嵌套：,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;,超前引用,【例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个学生到舞台上表演一个游戏，问有多少种选择方法。这是数学中的组合运算，可用下列公式计算：,3.递归调用：递归的定义：Pascal语言中，如果在一个函数、过程等的定义或说明内部又直接或间接地出现有对自身的引用，则称它们是递归的或者是递归定义的。例如：在数学上，所有偶数的集合可递归地定义为：0是一个偶数；一个偶数和2的和是一个偶数。可见，仅需两句话就能定义一个由无穷多个元素组成的集合。递归的实现：通过函数或过程的调用来实现。函数或过程直接调用其自身，称为直接递归；函数或过程间接调用其自身，称为间接递归。,直接递归,间接递归,递归应用,程序如下：Programex5;Functionnum(x:integer):integer;/采用函数编写beginifx=5thennum:=10/递归边界elsenum:=num(x+1)+2;/递归式end;BEGINwriteln(TheNumis,num(1);END.,程序执行过程？,【例6】、猴子吃枣问题：猴子摘了一堆枣，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天，又吃了剩下的一半零一个；以后每天如此。到第十天，猴子一看只剩下一个了。问最初有多少个枣子？,要求：写出递推表达式，尝试用递推函数编写程序,课堂练习1、programlx1(input,output);vars,n:integer;functionf(n:integer):integer;beginifn=1thenf:=1elsef:=n*n+f(n-1)end;beginwrite(inputn:);readln(n);s:=f(n);writeln(f(,n,)=,s)end.该程序的功能是：。当n的值为时，程序的运行结果是：,在处理子问题时，如果又调用原问题的处理子程序，但形参值应是不断改变的量(表达式);,递归方法说明如下：,调用原问题的子程序（过程或函数）时，调用程序应给出具体的子程序形参值（与形参结合的实参）;,递归算法表现出处理问题的强大能力。然而，如同循环一样，递归也会带来无终止调用的可能性，因此，在设计递归过程（函数）时，必须考虑递归调用的终止问题，就是递归调用要受限于某一条件，而且要保证这个条件在一定情况下肯定能得到满足。,整个递归过程可视为由往返双向“运动”组成，先是逐层递进，逐层打开新的“篇章”，（有可能无具体计算值）当最终递进达到边界，执行完本“层”的语句，才由最末一“层”逐次返回到上“层”，每次返回均带回新的计算值，直至回到第一次由主程序调用的地方，完成对原问题的处理。,由于调用参数不断改变，将使条件满足，此时就是最后一“层”，不需再调用自身，而是在本层往下执行后继语句，遇到end，就返回到上“层”调用此子程序的地方并继续往下执行，如此直到返回主程序,每递归调用一次自身，系统就打开一“层”与自身相同的程序系列;,如何设计递归算法？,1.确定递归公式2.确定边界(终了)条件,课堂练习2：求：1+2+3+.+n的值。n从键盘上输入。有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?用递归的方法求Xn（X和n由键盘输入）已知:数列1,1,2,4,7,13,24,44,.求数列的第n项.,【例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.,使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的、规模较小的问题进行求解，最终达到对原问题的求解。,栈,递归过程,【例8】：把一个十进制整数转换成K进制数(k,c)elsebeginmove(n-1,a,c,b);writeln(a,-,c);move(n-1,b,a,c)end;end;beginwrite(thenumberofdish:);readln(number);move(number,A,B,C);end.,【例10】求找出具有下列性质的数的个数(包含输入的自然数n)：先输入一个自然数n(n=500),然后对此自然数按照如下方法进行处理:.不作任何处理;.在它的左边加上一个自然数,但该自然数不能超过原数的一半;.加上数后,继续按此规则进行处理,直到不能再加自然数为止.样例:输入:6满足条件的数为6162612636136输出:6,varn,i:integer;s:real;procedureqiu(x:integer);vark:integer;beginifx0thenbegins:=s+1;fork:=1toxdiv2doqiu(k)endend;beginreadln(n);s:=0;qiu(n);writeln(s:2:0)end.,【例11】、求m与n的最大公约数,分析：从数学上可以知道求m与n的最大公约数等价于求n与(mmodn)的最大公约数。这时可以把n当作新的m,(mmodn)当作新的n，这样问题又变成了求新的m与n的最大公约数这种方法我们称为辗转相除法。设两个整数分别为m和n，将m整除n得到一个余数r，若r=0，则除数n就是最大公约数，否则，将除数作为被除数，余数作为除数继续相除，直到余数=0为止。,Varm,n:integer;functiongys(a,b:integer):integer;varr:integer;beginr:=amodb;ifr=0thengys:belsegys:=gys(b,r);end;beginreadln(m,n);writeln(gysis:,gys(m,n);end.,【分析】对于一个已确定的数组a1至an和一个确定的数m，判断能否使数组a中任意几个元素之和等于m，等价于判断能否从数组a中取任意数使其和为m。此时若an=m，则可以输出“YES”，否则若n=1，则可以输出“NO”。否则可以按以下规则进行判断：对于a中任意元素an只有取与不取两种情况：()取an：则此时问题转化为：对于一个已确定的数组a1至an-1和一个确定的数m-an，判断能否使数组a中任意几个元素之和等于m-an。()不取an：则此时问题转化为：对于一个已确定的数组a1至an-1和一个确定的数m，判断能否使数组a中任意几个元素之和等于m。若用函数sum(n,m)表示能否从数组a1至an中取任意数使其和为m，只要sum(n-1,m-an)和sum(n-1,m)当中有一个值为真，则sum(n,m)为真，否则为假。因此，可以用递归来解此题。递归终止条件为：ifan=mthensum:=trueelseifn=1thensum:=false;,【例12】已知一个一维数组A1.N(N50)，又已知一整数M。如能使数组A中任意几个元素之和等于M，则输出YES，反之则为NO。,Programdigui(input,output);Constn=8;Typemat=array1.nofchar;Vari:integer;a:mat;Procedureprint(i:integer);beginIfi=nthenwrite(ai)elsebeginprint(i+1);write(ai);end;end;Beginfori:=1tondoreadln(ai);i:=1;print(i);readln;End.,例13、输入N个字符，然后以倒序输出（用递归实现）。