算法设计与分析--递归

《算法设计与分析--递归》由会员分享，可在线阅读，更多相关《算法设计与分析--递归（58页珍藏版）》请在金锄头文库上搜索。

1、递 归,第3章 递 归,递归调用的内部实现原理 递归程序的阅读 递归转非递归 递归算法的设计 解递归方程,递归的定义在定义一个过程或函数时出现调用本过程或本函数的成分,称之为递归。若调用自身,称之为直接递归。若过程或函数p调用过程或函数q,而q又调用p,称之为间接递归。,3.1 递归调用的内部实现原理,图3.1 子程序调用的几种形式,(1)两次值传送方式 按指定类型为变参设置相应的存储空间，在执行调用时，将实参值传送给变参，在返回时将变参的值回传实参。 (2)地址传送方式 在内部将变参设置成一个地址，调用时首先执行地址传送，将实参的地址传送给变参，在子程序执行过程中，对变参的操作实际上变成所对

2、应的实参的操作。,值的回传,在执行调用时，系统至少执行如下操作： a.返回地址进栈，同时在栈顶为被调子程序的局部变量开辟空间； b.为被调子程序准备数据：计算实参值，并赋给对应的栈顶的形参； c.将指令流转入被调子程序的入口处； 在执行返回操作时，系统至少执行如下操作： a.若有变参或是函数，将其值保存到回传变量中； b.从栈顶取出返回地址； c.按返回地址返回； d.若有变参或是函数，从回传变量中取出保存的值传送给相应的变量或位置上。,子程序调用的内部实现,3.2.1 模拟系统栈方式 例3.1 求m，n(mn)的最大公因子的递归过程。 procedure GCD(m，nint；var hin

3、t)begin 1if n=0 2 then begin hm； write(h)； end 3else call GCD(n，m mod n，h)； 4endp；,3.2 递归程序的阅读,call GCD(28，6，X)执行过程,指令流方式 GCD(100，18，x)执行write(x)的运行过程，,指令流方式,指令流方式 例3.3 对下面的递归过程， 写出调用P(3)的运行结果。 procedure P(wint)； beginif w0 thenbegincall P(w-1)；write(w)；call P(w-1)；end； endp；,递归算法的程序设计存在两个问题： 并不是所有语

4、言都支持递归； 递归程序比非递归程序要花费更多的时间，当递归层数太多时，会出现栈溢出。,3.3 递归转非递归,系统自动地为递归设置了一个栈，因此，在等价的非递归程序中，需要设置栈S，初始为空 调用的c操作是将程序的执行流程转入到子程序的入口处，所以等价程序中，用无条件的转移语句实现，并在入口处设置一个标号L0。 对程序中的每个递归调用，用以下几个等价操作替换： a.保留现场：开辟栈顶存储空间，用于保存返回地址(不妨用Li，i=1，2，)和调用层的形参和局部变量的值(最外层调用不必考虑)；,递归转非递归方法,b.准备数据：为被调子程序准备数据，计算实参值，并赋给对应的形参； c.执行goto L

5、0； d.在返回处设一个标号Li(i=1，2，3，)，并根据需要设置以下语句：若有变参或是函数，从回传变量中取出所保存的值，并传送到相应的实参或位置。 对返回语句，如果栈不空，则依次执行如下操作，否则结束本子程序，返回。 a.回传数据：若有变参或是函数，将其值保存到回传变量中； b.恢复现场：从栈顶取出返址(不妨设保存到X中)及各变量、形参的值，并退栈； c.返回，执行goto X； d.对其中的非递归调用和返回操作可照搬。,例3.4 将下面的递归程序转化成等价的非递归程序。 procedure P(wint)； beginif w0 thenbegincall P(w-1)；write(w)

6、；end； endp；,解 按转化规则可得procedure P1(wint)；begininit(S)； l0 if w0 thenbeginpush(S，w，l1)；ww-1goto l0； l1 write(w)；end；if not empty(S) thenbeginpop(S，w，X)；goto X；end；endp；,简化规则1 如果递归程序中只有一次递归调用，则在转换时，返回地址不入栈。,图3.4 例3.4的流程图,procedure P1(wint)； begininit(S)；while w0 dobeginpush(S，w)；ww-1；end； while not emp

7、ty(S) dobeginpop(S，w)；write(w)；end； endp；,修改后的程序,例3.5 将下面递归程序改为等价的非递归程序。 procedure P(wint)； beginif w0 thenbeginwrite(w)；call P(w-1)；end； endp；,procedure P1(wint)； begininit(S)； l0 if w0 thenbeginwrite(w)；push(S，w)；ww-1；goto l0； l1 end；if not empty(s) thenbeginpop(S，w)；goto l1；end； endp；,简化规则2 在尾递归调

8、用时，不必执行入栈操作。,注意：如果有变参或是函数，则在返回后还要执行赋值操作，所以不能算尾递归。,图3.5 例3.5流程图,procedure P1(wint)； begin l0if w0 thenbeginwrite(w);ww-1;goto l0end; endp;,修改后的程序,例3.6 将例3.1转换成等价的非递归程序。procedure GCD(m,nint;var hint);var temp,backvarint;begin,init(S); l0if n=0 thenbeginhm;write(h);endelsebeginpush(S,m,n,h);temp m; m n

9、; n temp mod n;goto l0;,l1h backvar;end;if not empty(S) thenbeginbackvar h;pop(S,m,n,h);goto l1;end; endp;,图3.6 例3.6的流程图,procedure GCD(m,nint;var hint);var temp,backvar int;begininit(S);while n0 dobeginpush(S,m,n,h);temp m; m n; n temp mod n;end;,h m;write(h); while not empty(S) dobeginbackvar h;pop

10、(S,m,n,h);h backvar;end; endp;,修改后的程序,适宜于用递归算法求解的问题的充分必要条件是： 问题 P 的描述涉及规模，即 P(size)； 规模发生变化后，问题的性质不发生变 问题的解决有出口。表现形式 procedure P(参数表)； beginif 递归出口then 简单操作elsebegin 简单操作；call P; 简单操作 end; endp;,3.4 递归算法的设计,例3.7 简单的0/1背包问题。 设一背包可容物品的最大质量为m，现有n个物品，质量为(w1,w2,wn)，wi均为正整数，从n件物品中挑选若干件，使放入背包的质量之和正好为m。,例3.

11、9 棋子移动。有 2n 个棋子(n4)排成一行，白子用0代表，黑子用1代表，n =5的初始状态为： 0 0 0 0 0 1 1 1 1 1 _ _(右边至少有两个空位) 移动规则是每次必须同时移动相邻两个棋子，颜色不限，移动方向不限，每次移动必须跳过若干棋子，不能调换两个棋子的位置，最后成为： 0 1 0 1 0 1 0 1 0 1,下面用不完全归纳法找出口和递推关系。 n=4 0 0 0 0 1 1 1 1_ _ 第一步 0 0 0 _ _ 1 1 1 0 1 (4,5)(9,10) 第二步 0 0 0 1 0 1 1 _ _ 1 (8,9) (4,5) 第三步 0 _ _ 1 0 1 1

12、0 0 1 (2,3) (8,9) 第四步 0 1 0 1 0 1 _ _ 0 1 (7,8) (2,3) 第五步 _ _ 0 1 0 1 0 1 0 1 (1,2) (7,8),n=5 0 0 0 0 0 1 1 1 1 1 _ _ 第一步 0 0 0 0 _ _ 1 1 1 1 0 1 (5,6) (11,12) 第二步 0 0 0 0 1 1 1 1 _ _ 0 1 (9,10)(5,6) 这时前 8 枚棋子是 n =4的情况，移法如 n =4的第一步到第五步即可完成 n =5时的移子。 n=6 0 0 0 0 0 0 1 1 1 1 1 1 _ _ 第一步 0 0 0 0 0 _ _

13、1 1 1 1 1 0 1 (6,7)(13,14) 第二步 0 0 0 0 0 1 1 1 1 1 _ _ 0 1 (11,12)(6,7) 前 10 枚棋子为 n =5的情况。,由此归纳出： n =4时是递归的出口，在退出时作5个移动操作： move (4,5) (9,10) move (8,9) (4,5) move (2,3) (8,9) move (7,8) (2,3) move (1,2) (7,8) 如果 2n 个棋子的移动用 chess( n )表示，则递推关系是： Move (n,n+1) (2n+1,2n+2); move (2n-1,2n) (n,n+1); call c

14、hess(n-1);,例3.10 求 n 个元素的全排列。 分析： n =1输出：a1; n =2输出：a1 a2a2 a1; n =3输出：a1 a2 a3 a1 a3 a2a2 a1 a3a2 a3 a1 a3 a1 a2a3 a1 a2,分析 n =3，全部排列分成三类： a1 类： a1 之后跟a2 ， a3 的所有全排列。 a2 类： a2 之后跟a1 ， a3 的所有全排列。 a3 类： a3 之后跟a2 ， a1 的所有全排列。 将中a1 ， a2 的互换位置，得到；将中a1 ， a3 的互换位置，得到。它说明可以用循环的方式重复执行交换位置，后面跟随剩余序列的所有排列，对剩余序列再使用这个方法，这就是递归调用，当后跟的元素没有时就得到递归的边界。,例3.11 自然数拆分。 任何一个大于1的自然数 n，总可以拆分成若干个小于 n 的自然数之和，试求 n 的所有拆分。,n =2 可拆分成 2=1+1 n =3 可拆分成 3=1+2=1+1+1 n =4 可拆分成 4=1+3=1+1+2=1+1+1+1=2+2,n =7 可拆分成 7=1+6=1+1+5=1+1+1+4=1+1+1+1+3=1+1+1+1+1+2=1+1+1+1+1+1+1=1+1+1+2+2=1+1+2+3=1+2+4=1+2+2+2=1+3+3=2+5=2+2+3=3+4,