子程序的递归与嵌套.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的和是一个偶数。 可见，仅需两句话就能定义一个由无穷多个元素组成的集合。 递归的实现： 通过函数或过程的调用来实现。 函数或过程直接调用其自身，称为直接递归；函数或过程间接调用其自身，称为间接递归。,直接递归,间接递归,递归应用,程序如下： Program ex5; Function num(x:integer):integer; /采用函数编写 begin if x=5 then num:=10 /递归边界 else num:=num(x+1) +2; /递归式 end; BEGIN writeln(The Num is ,num(1); END.,程序执行过程？,【例6】、猴子吃枣问题：猴子摘了一堆枣，第一天吃了一半，还嫌不过瘾，又吃了一个；第二天，又吃了剩下的一半零一个；以后每天如此。到第十天，猴子一看只剩下一个了。问最初有多少个枣子？,要求：写出递推表达式，尝试用递推函数编写程序,课堂练习1、program lx1(input,output); var s,n:integer; function f(n:integer):integer; begin if n=1 then f:=1 else f:=n*n+f(n-1) end; begin write(input n:);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!可以由下面公式表示：,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.,使用递归求解问题，通常可以将一个比较大的问题层层转化为一个与原问题相类似的、规模较小的问题进行求解，最终达到对原问题的求解。,栈,递归过程,【例8】：把一个十进制整数转换成K进制数(k10)。,K number,8,157,8,19,8,2,0,5,3,2,分析,根据数制转换规则，把一个十进制整数转换成K进制数，要用“除K取余”法。也就是用K依次去除这个数及其商，所得余数依次作为K进制数相继的低位数字，一直到商为0即可。 如果我们不用数组存储每次求得的低位数字，怎么让程序按顺序输出K进制的各位数字？,分析,可以用递归的方法实现这一过程。算法过程tentok(number,k)如下： 步一 digitnumber mod k; 步二 numbernumber div k 步三 如果number不为0则调用 tentok(number,k) 步四 输出digit,参考程序：,program convert(input,output); var number ,k:integer; procedure tentok(number,k:Integer); var digit:integer; begin digit:=number mod k; number:=number div k; if number0 then tentok(number,k); write(digit); end; begin write(Enter number and converted basis k(2-9):); readln(number,k); tentok(number,k); writeln; end.,执行过程分析,第2次调用 digit=3 number=2 tentok(2,8),第1次调用 digit=5 number=19 tentok(19,8),Tentok(157,8),第3次调用 digit=2 number=0,write(digit),write(digit),write(digit),K number,8,157,8,19,8,2,0,5,3,2,递归结构的优点：结构清晰、容易阅读和理解。 递归结构的缺点：需要保留每次递归调用时的参数和局部变 量，占用内存大，耗费机时多，程序运行 的效率较低 。 递归算法的实用情况： 1.符合递归的描述：需要解决的问题可以化为子问题求解， 而子问题求解的方法与原问题相同，只 是数量增大或减少。 2.递归调用的次数是有限的。 3.必须有递归结束的条件。,例9、汉诺塔问题,有n个半径各不相同的圆盘，按半径从大到小，自下而上依次套在A柱上，另外还有B、C两根空柱。要求将A柱上的n个圆盘全部搬到C柱上去，每次只能搬动一个盘子，且必须始终保持每根柱子上是小盘在上，大盘在下。,在移动盘子的过程当中发现要搬动n个盘子，必须先将n-1个盘子从A柱搬到B柱去，再将A柱上的最后一个盘子搬到C柱，最后从B柱上将n-1个盘子搬到C柱去。搬动n个盘子和搬动n-1个盘子时的方法是一样的，当盘子搬到只剩一个时，递归结束。,源柱 工作柱 目标柱,A B C,var a,b,c,number:integer; procedure move(n: integer;a,b,c:char); begin if n=1 then writeln(a,-,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 the