子程序的递归与嵌套.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,子程序的嵌套与递归,1,、复习函数与过程,子程序,子程序的定义,定义位置,如何定义？,子程序的调用,在何处调用？,如何调用？,参数的传递,值传递，地址传递,变量的作用域,全局，局部,子程序如何返回值到调用处,函数通过函数名带回值,子程序可通过变量参数和全局变量的方式带回值到调用处,【,例,1】,：输入一个正整数，如果是回文素数则输出“,Yes”,，否则输出“,No”,【,分析,】,定义两个并列关系的函数，分别判断一个数是否为素数和是否为回文数,教材,P93,例,5-11,注意：,1,）内、外层子程序不得相互交叉，内层必须完全嵌套在外层之中；,2,）一般情况下，在子程序内部需要使用的变量应在子程序的内部进行定义。外层子程序不能访问内层子程序所定义的变量。,【,例,2】,：求组合数 的和。,var,s:real,;,function,cnm(n,m:integer):real,;,function,fac(k:integer):longint,;,var,i:integer,;,t:real,;,begin,t:=1;,for i:=2 to k do t:=t*i;,fac,:=t;,end;,begin,cnm,:=fac(n)/(fac(m)*fac(n-m);,end;,begin,s:=cnm(6,3)+cnm(9,5);,writeln(,s,=,s:8:2);,end.,2,、子程序的嵌套：,function,fac(k:integer):longint,;,var,i:integer,;,t:real,;,begin,t:=1;,for i:=2 to k do t:=t*i;,fac,:=t;,end;,function,cnm(n,m:integer):real,;,begin,cnm,:=,fac(n)/(fac(m,)*,fac(n-m,);,end;,function,fac(k:integer):longint,;,Forward,；,function,cnm(n,m:integer):real,;,begin,cnm,:=,fac(n)/(fac(m,)*,fac(n-m,);,end;,function,fac(k:integer):real,;,var,i:integer,;,t:real,;,begin,t:=1;,for i:=2 to k do t:=t*i;,fac,:=t;,end;,超前引用,【,例,3】,：求组合数（）,/7,！的和。,var,s:real;,function,fac(k:integer):longint,;,var,i:integer;,t:longint,;,begin,t:=1;,for i:=2 to k do t:=t*i;,fac:=t;,end;,function,cnm(n,m:integer):real,;,begin,cnm,:=fac(n)/(fac(m)*fac(n-m);,end;,begin,s:=cnm(6,3)+cnm(9,5);,writeln(,s,=,(s/fac(7):8:2);,end.,学校举行晚会，要从,M,个学生中选,N,个学生到舞台上表演一个游戏，问有多少种选择方法。这是数学中的组合运算，可用下列公式计算：,3.,递归调用：,递归的定义：,Pascal,语言中，如果在一个函数、过程等的定义或说明内部又直接或间接地出现有对自身的引用，则称它们是递归的或者是递归定义的。,例如：在数学上，所有偶数的集合可递归地定义为：,0,是一个偶数；,一个偶数和,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),A,x,=,A,x+1,+2 (x5),其中求,Ax+1,又采用求,Ax,的方法。所以,:,定义一个处理问题的子程序,Num(x,),，如果,X 0,【,例,7】,用递归计算,n!,n!,可以由下面公式表示：,var,n,s:integer,;,function fac(a:integer):integer;,begin,if a=0 then fac:=1 else fac:=a*fac(a-1);,end;,begin,readln(n,);s:=fac(n);,writeln(n,!=,s),end.,使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的、规模较小的问题进行求解，最终达到对原问题的求解。,栈,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)=1,fac(1)=1,*,递归过程,【,例,8】,：把一个十进制整数转换成,K,进制数,(k,c),else,begin,move(n-1,a,c,b);,writeln(a,-,c);,move(n-1,b,a,c),end;,end;,begin,write(the,number of dish:);,readln(number,);,move(number,A,B,C,);,end.,【,例,10】,求找出具有下列性质的数的个数,(,包含输入的自然数,n),：,先输入一个自然数,n(n,=500),然后对此自然数按照如下方法进行处理,:,.,不作任何处理,;,.,在它的左边加上一个自然数,但该自然数不能超过原数的一半,;,.,加上数后,继续按此规则进行处理,直到不能再加自然数为止,.,样例,:,输入,:6,满足条件的数为,6,16,26,126,36,136,输出,:6,var,n,i:integer,;,s:real,;,procedure,qiu(x:integer,);,var,k:integer,;,begin,if x0 then,begin,s:=s+1;,for k:=1 to x div 2 do,qiu(k,),end,end;,begin,readln(n,);s:=0;,qiu(n,);,writeln(s:2:0),end.,【,例,11】,、求,m,与,n,的最大公约数,分析：从数学上可以知道求,m,与,n,的最大公约数等价于求,n,与,(m mod n),的最大公约数。这时可以把,n,当作新的,m,(m mod n),当作新的,n,，这样问题又变成了求新的,m,与,n,的最大公约数,这种方法我们称为辗转相除法。,设两个整数分别为m,和,n,，将,m,整除,n,得到一个余数,r,，若,r=0,，则除数,n,就是最大公约数，否则，将除数作为被除数，余数作为除数继续相除，直到余数,=0,为止。,Var,m,n:integer,;function,gys(a,b:integer):integer,;,var,r:integer,;begin r:=a mod b;if r=0 then,gys:b,else,gys,:=,gys(b,r,);end;begin,readln(m,n,);,writeln(gys,is:,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,),为真，否则为假。因此，可以用递归来解此题。,递归终止条件为：,if,an,=m then sum:=true else if n=1 then sum:=false;,【,例,12】,已知一个一维数组,A1.N(N50),，又已知一整数,M,。如能使数组,A,中任意几个元素之和等于,M,，则输出,YES,，反之则为,NO,。,Program,digui,(,input,output,);,Const n=8;,Type mat=array1.n of char;,Var,i:integer;a:mat,;,Procedure,print(i:integer,);,begin,If i=n then,write(ai,),else begin print(i+1);write(ai);end;,end;,Begin,for i:=1 to n do,readln(ai,);,i:=1;,print(i,);,readln,;,End.,例,13,、输入,N,个字符，然后以倒序输出（用递归实现）。,课后练习：,1,、楼梯共有,N,阶台阶，上楼可以以一步上一个台阶，也可以一步上二个台阶。编一个程序计算上,N,阶台阶，共有多少种走法？,2,、递归的方法求,12+22+32+n2,。,3,、用辗转相除法求两个正整数的最大公约数，用递归和非递归的形式编程。,4,、输入一个非负整数，输出这个数的倒序数。例如输入,123,，输出,321,。,5,、用递归算法将数组,A,中的,N,个数倒序输出。,6,、用递归方法求,N,个数中的最大数及其位置。,7,、用递归算法将一个十进制数,X,转换成任意进制数,M,（,M=16,）。,