计算机算法设计与分析：3第三章递归

1、第 三 章 递 归1一个递归问题从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是 调用自己23.1 递归算法实现机制3.2 递归转非递归(略)3.3 递归算法设计3.4 递归关系式的计算(略)目录3递归 定义一个过程直接地或间接地调用自己，则称这个过程是递归的过程。 递归算法在计算机理论和实际应用中都具有重要意义。设计和分析思路清晰，实现容易，但效率较低。43.1 递归算法实现机制子程序实现原理子程序调用的一般形式值回传方式子程序调用的内部操作递归程序实现原理5主程序Call A1：子程

2、序 A主程序Call A2：子程序 ACall A1：(b) n次调用(a) 1次调用子程序调用的一般形式6子程序调用的一般形式Call B2：子程序 ACall A1：主程序子程序 BCall A2：子程序 ACall B1：主程序子程序 B(c)嵌套调用(d)平行调用子程序调用时，用栈方式管理调用子程序时的返回地址（包括局部变量）。7值回传方式实参与形参的两种数据传送方式：值参与变参变参回传值，有两种方法：两次值传送方式按指定类型为变参设置相应的存储空间。执行调用时，实参值传送给变参，返回时变参值传送给实参。地址传送方式在内部将变参设置成一个地址，调用时将实参的地址传送给变参。本章讨论的递

3、归问题对变参采用两次值传送方式。8子程序调用的内部操作执行调用时：返回地址进栈，开辟子程序的局部变量空间为子程序准备数据，即将实参值赋值给形参指令流转入子程序入口执行返回操作时：将变参或函数的值保存到回传变量中从栈顶取出返回地址按地址返回将回传变量中的值传送给相应的变量或位置上9递归程序实现原理原理：一个递归过程的执行类似于多个子程序的嵌套调用。定义：递归过程直接地或间接地调用自己本身代码。特征：有递归调用、有递归出口。特点：设计和分析思路清晰，实现容易，效率较低。10procedure f(integer n)integer y; if (n0) return 1 y f(n1); retu

4、rn(ny);end f递归求阶乘的算法主程序：integer fn;fn f(4);11为了保证递归调用的正确性，需要保存调用点的现场（返回地址、局部变量、被调用函数的参数等），以便正确地返回，并且按先进后出的原则来管理这些信息。高级语言编译程序是利用栈来实现的。 f(n) f(n1) f(n2) f(1) f(0)调用返回调用点 PnPn-1Pn-2P11调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场.12计算 4 ! 递归过程图示：下图中 Pi 代表现场信息，栈元素由现场信息和参数构成f(4)4f(3) f(3)3f(2) f(2)2f(1) f(1)1f(0) f(0)1 Pu

5、sh(e4) Push(e3) Push(e2) Push(e1) f(4)4f(3) f(3) 3f(2) f(2) 2f(1) f(1) 1f(0) 24 6 2 1P4 4P3 3P4 4P2 2P3 3P4 4P1 1P2 2P3 3P4 4Pop(e1)Pop(e2)Pop(e3)Pop(e4)133.1 递归算法实现机制3.2 递归转非递归3.3 递归算法设计3.4 递归关系式的计算目录143.3 递归算法设计递归设计需满足的要求递归求解的通用表现形式递归的几个典型例子15递归设计需满足的要求可以用递归求解的问题应满足：问题P的描述涉及规模，即P(size)；规模发生变化后，问题的

6、性质不变；问题的解决有出口。 16递归求解的通用表现形式 Procedure P(参数表) if 递归出口 then 简单操作 else 简单操作 call P 简单操作 endif end P规模或与规模相关的参数降低规模的处理对递归结果的处理17几个典型例子简单的0/1背包问题n阶Hanoi塔问题棋子移动问题n个元素的全排列自然数拆分（正整数拆分）18例3.3 简单的0/1背包问题 背包可容纳物品的最大质量为m，现有n件物品，质量分别为m1, m2, mn，mi均为正整数，要从n件物品中挑选若干件，使放入背包的质量之和正好为m.19简单的0/1背包问题例：m20, n5, (m1, m2,

7、 m3, m4, m5)(3,5,8,9,10) (x1,x2,x3,x4,x5)(1,0,1,1,0) m18? m28?注：对于第i件物品要么取，要么舍，不能取一部分，因此这个问题可能有解，也可能无解。布尔函数20问题分析 knap(m, n)m初始：.m1 m2 mn1 mnm.m1 m2 mn1mnmtruemnmm.m1 m2 mn1n1,即还有可选物品knap(mmn, n1)knap(m,n) knap(m,n1)knap(m,n) knap(mmn,n1)有解无解mn mm.m1 m2 mn1n1knap(m,n1)否则 false21function knap(m, n) c

8、ase :mmn0: knap true :mmn0: if n1 then if knap(mmn,n1) true then knap true else knap knap(m,n1) endif else knap false endif :mmn0:if n1 then knap knap(m,n1) else knap false ; endif endcaseEnd knap22例3.4 一个印度的古老传说_ 汉诺塔在贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔

9、(Tower of Hanoi）。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 假如每秒钟一次，移完这些金片需要5845亿年以上。 23n阶Hanoi塔问题有n个圆盘依半径从小到大自上而下地套在柱子A上，柱子B和C没有圆盘。要求将A上的盘子换到C上，每次只移动一个，且不允许将大圆盘压在小圆盘的上面。24XYZHanoi(n,X,Y,Z)圆盘数量源柱辅助柱目标柱寻找递归出口(1) n1, X1Z(2) n2,

10、 X1Y X2Z Y1Z25n阶Hanoi问题Hanoi(n,X,Y,Z)n3, Hanoi(2,X,Z,Y) XZ Hanoi(2,Y,X,Z)3XYZ26CABCABABC(1) Hanoi(n1,X,Z,Y)(2) X nZ(3) Hanoi(n1,Y,X,Z)XYZHanoi(n,X,Y,Z)圆盘数量源柱辅助柱目标柱27n阶Hanoi问题procedure Hanoi(n, X, Y, Z) if (n1) then move(X, Z) else Hanoi(n1, X, Z, Y) move(X, Z) Hanoi(n1, Y, X, Z) endifEnd Hanoi28例3.5

11、 棋子移动问题 有2n个棋子(n4)排成一行，白子用0表示，黑子用1表示，例如n5时初始状态为右边至少有两个空位）0 0 0 0 0 1 1 1 1 1 _ _，（要求通过棋子移动最终成为 0 1 0 1 0 1 0 1 0 1.29棋子移动问题移动规则每次必须同时移动相邻两个棋子颜色不限，移动方向不限每次移动必须跳过若干棋子不能调换这两个棋子的位置30n4 00001111_ _ step1 000_ _11101 (4,5)(9,10) step2 0001011_ _1 (8,9)(4,5) step3 0_ _1011001 (2,3)(8,9) step4 010101_ _01 (

12、7,8)(2,3) step5 _ _01010101 (1,2)(7,8)寻找递归出口31n5 0000011111_ _ step1 0000_ _111101 (5,6)(11,12) step2 00001111_ _01 (9,10)(5,6)n6 000000111111_ _ step1 00000_ _1111101 (6,7)(13,14) step2 0000011111_ _01 (11,12)(6,7)chess(n)递归出口：n4;递归过程：n4时；move (n,n1)(2n1,2n2)；move (2n1,2n)(n,n1);call chess(n1); 32棋

13、子的移动问题Procedure Chess(n) if n=4 then 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) else move (n, n+1) (2n+1, 2n+2) move (2n1, 2n) (n, n+1) call Chess(n-1) endifEnd Chess递归出口递归调用A(9)A(4)A(10)A(5)33例3.6 求n个元素的全排列设A=a1,a2,an是要进行排列的n个元素的集合， n1 输出a1 n2 输出a1a2 a2a1

14、n3 输出a1a2a3 a1a3a2 a2a1a3 a2a3a1 a3a2a1 a3a1a2 分析n3，排列按如下步骤进行： a1之后跟a2, a3的所有全排列；在上述全排列里，a1和a2位置互换；在上述全排列里， a1和a3位置互换。34求n个元素的全排列range(A) = a1range(A1), a2range(A2), anrange(An)集合A用数组实现range(A,1,n)：递归出口：range(A, n, n)递归调用：使得集合所有元素都可以作为前缀出现A-a1A-a2A-an35求n个元素的全排列procedure range(A, k, n) if kn then pr

15、int(A) else for i k to n do A(k) A(i) call range(A,k1,n) A(k) A(i) repeat endifend range递归出口，打印整个数组A。A(i)与A(k)值互换缺省时，认为形参是in型，其值变化时不回传。call range(A,1,n)36range(A,1,3)If 13 then print(A) else for i 1 to 3 do A(1)A(i); call range(A,2,3) 略A=a, b, cabc1) i1, aa Aa,b,c2) i2, bb Aa,b,cacb3) i3, bc Aa,c,bb

16、ac4) i2, a b Ab,a,c5) i2, aa Ab,a,cbca6) i3, ac Ab,c,arange(A,2,3)for i2 to 3 do A(2)A(i); call range(A,3,3) 略range(A,3,3)If 33 print(A) 略7) i3, ac Ac,b,acba8) i2, bb Ac,b,acab9) i3, ba Ac,a,b37例3.7 自然数拆分任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和，试求n的所有拆分。n2 211n3 312 111n4 413 112 1111 2238自然数拆分（正整数拆分）n6 6 15

17、 114 1113 11112 111111 1122 123 24 222 3339自然数拆分（正整数拆分）拆分的结果用一维数组A保存；对任意自然数的所有拆分方式，依据A(1)的值，可以分为n/2类；第i类第一行元素是A1i， A2ni；为保证拆分不重复，A中元素是非降的；下一次的拆分，用A的下标来控制，而不是A中的元素值；发生下一次拆分（递归调用）的判断条件。40自然数拆分（正整数拆分）算法procedure split(t) for k 1 to t do write(A(k) ; repeat j t; L A(j) for i A(j1) to L/2 do A(j) i; A(j1

18、) Li ; call split(t1) repeat end split procedure main(n) for i 1 to n2 do A(1) i; A(2) ni; call split(2) repeatend main输出已产生的一种拆分本次拆分的起始位置本次拆分的数值41split(2)Print:1,3j2; L3i在13/2之间i1: A2 1; A3 2;main(4)i在14/2之间i1: A11; A23;i2: A12; A22;1split(3)Print:1,1,2j3; L2i在12/2之间i1: A3 1; A4 12split(4)Print:1,1

19、,1,1j4; L1i在11/2之间3split(2)Print:2,2j2; L3i在22/2之间4423.4 递归关系式的计算递归算法的时间复杂度分析K阶线性齐次递归关系式的解法 43递归算法的时间复杂度分析求n个元素的最大元问题 二分法 Max(A,1,n) A(1)A(2) A(n/2) A(n/21) A(n)Max(A,1, n/2)Max(A,n/21,n)max44求n个元素的最大元问题Procedure MAX (A,i, j) if ij then return A(i) endif if ji1 then if A(i)A(j) then return A(i) else return A(j) ; endif else k (ij)/2 m1 MAX(