子程序的递归与嵌套.ppt

《子程序的递归与嵌套.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、子程序的嵌套与递归1、复习函数与过程——子程序子程序的定义定义位置如何定义？子程序的调用在何处调用？如何调用？参数的传递值传递，地址传递变量的作用域全局，局部子程序如何返回值到调用处函数通过函数名带回值子程序可通过变量参数和全局变量的方式带回值到调用处【例1】：输入一个正整数，如果是回文素数则输出“Yes”，否则输出“No”【分析】定义两个并列关系的函数，分别判断一个数是否为素数和是否为回文数教材P93例5-11注意：1）内、外层子程序不得相互交叉，内层必须完全嵌套在外层之中；2）一般情况下，在子程序内部需要

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

3、=’,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;begin

4、cnm:=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;functioncn

5、m(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语言中，如果在一个函数、过程等的定义或说明内部又直接或间接地出现有对自身的引用，则称它们是递归的或者是递归定义的。例如

6、：在数学上，所有偶数的集合可递归地定义为：0是一个偶数；一个偶数和2的和是一个偶数。可见，仅需两句话就能定义一个由无穷多个元素组成的集合。②递归的实现：通过函数或过程的调用来实现。函数或过程直接调用其自身，称为直接递归；函数或过程间接调用其自身，称为间接递归。直接递归间接递归递归应用【例5】、植树节那天，有五位同学参加了植树活动，他们完成植树的棵数都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；…如此，都说比另一位同学多植两棵，最后问到

7、第五位同学时，他说自己植了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

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