2015年计算机学院算法分析课件第三章递归

1、第第 三三 章章 递递 归归2一个递归问题一个递归问题p从前有座山，山上有座庙，庙里有个老和尚讲故从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是事，讲的是p从前有座山，山上有座庙，庙里有个老和尚讲故从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是事，讲的是p从前有座山，山上有座庙，庙里有个老和尚讲故从前有座山，山上有座庙，庙里有个老和尚讲故事，讲的是事，讲的是p 调用自己调用自己33.1 递归算法实现机制递归算法实现机制3.2 递归转非递归递归转非递归(略略)3.3 递归算法设计递归算法设计3.4 递归关系式的计算递归关系式的计算目录目录4递归递归 定义定义一个过程直接地或间接地调用

2、自己，则称这个过一个过程直接地或间接地调用自己，则称这个过程是递归的过程。程是递归的过程。 递归算法在计算机理论和实际应用中都具有重递归算法在计算机理论和实际应用中都具有重要意义。要意义。设计和分析思路清晰，实现容易，但效率较低。设计和分析思路清晰，实现容易，但效率较低。53.1 递归算法实现机制递归算法实现机制n子程序调用的一般形式子程序调用的一般形式n值回传方式值回传方式(参数传递方式参数传递方式)n子程序调用的内部操作子程序调用的内部操作n递归程序实现原理递归程序实现原理6(b) n次调用次调用(a) 1次调用次调用子程序调用形式子程序调用形式7子程序调用形式子程序调用形式(c)嵌套调用

3、嵌套调用(d)平行调用平行调用8参数传递、值回传方式参数传递、值回传方式p有两种方法：有两种方法：p两次值传送方式两次值传送方式p按指定类型为变参设置相应的存储空间。执按指定类型为变参设置相应的存储空间。执行调用时，实参值传送给变参，返回时变参值传行调用时，实参值传送给变参，返回时变参值传送给实参。送给实参。p地址传送方式地址传送方式p在内部将变参设置成一个地址，调用时将实在内部将变参设置成一个地址，调用时将实参的地址传送给变参。参的地址传送给变参。p本章讨论的递归问题对变参采用两次值传送方式。本章讨论的递归问题对变参采用两次值传送方式。9子程序调用的内部操作子程序调用的内部操作p执行调用时：

4、执行调用时：p返回地址进栈，开辟子程序的局部变量空间返回地址进栈，开辟子程序的局部变量空间p为子程序准备数据，即将实参值赋值给形参为子程序准备数据，即将实参值赋值给形参p指令流转入子程序入口指令流转入子程序入口p执行返回操作时：执行返回操作时：p将变参或函数的值保存到回传变量中将变参或函数的值保存到回传变量中p从栈顶取出返回地址从栈顶取出返回地址p按地址返回按地址返回p将回传变量中的值传送给相应的变量或位置上将回传变量中的值传送给相应的变量或位置上10递归程序实现原理递归程序实现原理p原理：一个递归过程的执行类似于多个子程序原理：一个递归过程的执行类似于多个子程序的嵌套调用。的嵌套调用。p定义

5、：递归过程直接地或间接地调用自己本身定义：递归过程直接地或间接地调用自己本身代码。代码。p特征：有递归调用、有递归出口。特征：有递归调用、有递归出口。p特点：设计和分析思路清晰，实现容易，效率特点：设计和分析思路清晰，实现容易，效率较低。较低。11procedure f(integer n)integer y; if (n=0) return 1 y f(n1); return(ny)；end f递归求阶乘的算法递归求阶乘的算法主程序：主程序：integer fn；fn f(4)；12为了保证递归调用的正确性，需要保存调用点的现场（返为了保证递归调用的正确性，需要保存调用点的现场（返回地址、局

6、部变量、被调用函数的参数等），以便正确地回地址、局部变量、被调用函数的参数等），以便正确地返回，并且按先进后出的原则来管理这些信息。返回，并且按先进后出的原则来管理这些信息。高级语言编译程序是利用栈来实现的。高级语言编译程序是利用栈来实现的。 f(n) f(n-1) f(n-2) f(1) f(0)调用调用返回返回调用点调用点 PnPn-1Pn-2P11调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场.13计算计算 4 ! 递归过程图示：递归过程图示：下图中下图中 Pi 代表现场信息，栈元素由现场信息和参数构成代表现场信息，栈元素由现

7、场信息和参数构成f(4)=4*f(3) f(3)=3*f(2) f(2)=2*f(1) f(1)=1*f(0) f(0)=1 Push(e4) Push(e3) Push(e2) Push(e1) f(4)= 4 * f(3) f(3) = 3 *f(2) f(2)= 2 *f(1) f(1)= 1 * f(0) =24 = 6 = 2 =1P4 4P3 3P4 4P2 2P3 3P4 4P1 1P2 2P3 3P4 4Pop(e1)Pop(e2)Pop(e3)Pop(e4)143.1 递归算法实现机制递归算法实现机制3.2 递归转非递归（略）递归转非递归（略）3.3 递归算法设计递归算法设计

8、3.4 递归关系式的计算递归关系式的计算目录目录153.3 递归算法设计递归算法设计p递归设计需满足的要求递归设计需满足的要求p递归求解的通用表现形式递归求解的通用表现形式p递归的几个典型例子递归的几个典型例子16递归设计需满足的要求递归设计需满足的要求可以用递归求解的问题应满足：可以用递归求解的问题应满足：问题问题P的描述涉及规模，即的描述涉及规模，即P(size)；规模发生变化后，问题的性质不变；规模发生变化后，问题的性质不变；问题的解决有出口。问题的解决有出口。 17递归求解的通用表现形式递归求解的通用表现形式 Procedure P(参数表) if 递归出口 then 简单操作 els

9、e 简单操作 call P 简单操作 endif end P规模或与规模规模或与规模相关的参数相关的参数降低规模降低规模的处理的处理对递归结对递归结果的处理果的处理18几个典型例子几个典型例子p简单的简单的0/1背包问题背包问题pn阶阶Hanoi塔问题塔问题p棋子移动问题棋子移动问题pn个元素的全排列个元素的全排列p自然数拆分（正整数拆分）自然数拆分（正整数拆分）19例例3.3 简单的简单的0/1背包问题背包问题 背包可容背包可容纳物品的最大质量为纳物品的最大质量为m，现有，现有n件物件物品，质量分别为品，质量分别为m1, m2, mn，mi均为正整均为正整数，要从数，要从n件物品中挑选若干件

10、，使放入背包件物品中挑选若干件，使放入背包的质量之和正好为的质量之和正好为m.20简单的简单的0/1背包问题背包问题例：例：m=20, n=5, (m1, m2, m3, m4, m5) =(3,5,8,9,10) (x1,x2,x3,x4,x5)=(1,0,1,1,0) m=18? m=28?注：对于第注：对于第i件物品要么取，要么舍，不能取一件物品要么取，要么舍，不能取一部分，因此这个问题可能有解，也可能无解。部分，因此这个问题可能有解，也可能无解。布尔函布尔函数数21问题分析问题分析 knap(m, n)m初始：初始：.m1 m2 mn1 mnm.m1 m2 mn1mnmtruemnmm

11、.m1 m2 mn1n1,即还有可选物品即还有可选物品knap(mmn, n1)knap(m,n) knap(m,n1)knap(m,n) true有解有解无解无解mn mm.m1 m2 mn1n1knap(m,n1)否则否则 false22function knap(m,n) case :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) el

12、se knap false ; endif endcaseEnd knap23例例3.4 一个印度的古老传说一个印度的古老传说_ 汉诺塔汉诺塔p在贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着在贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的中一根针上从下到上地穿好了由大到小的64片金片，这片金片，这就是所谓的汉诺塔就是所谓的汉诺塔(Tower of Hanoi）。）。p不论白天黑夜，总有一个僧侣在按照下面的法则移动这些不论白天黑夜，总有一个僧侣在按照下面的

13、法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。而梵塔、庙宇和众生也都将同归于尽。 假如每秒钟一次，移完这些金片需要假如每秒钟一次，移完这些金片需要5845亿年以上。亿年以上。 24n阶阶Hanoi塔问题塔问题p有有n个圆盘依半径从小到大自上而下地套个圆盘依半径从小到大自上而下地套在柱子在柱子A上，柱

14、子上，柱子B和和C没有圆盘。要求将没有圆盘。要求将A上的盘子换到上的盘子换到C上，每次只移动一个，上，每次只移动一个，且不允许将大圆盘压在小圆盘的上面。且不允许将大圆盘压在小圆盘的上面。25XYZHanoi(n,X,Y,Z)圆盘圆盘数量数量源柱源柱辅助辅助柱柱目标目标柱柱寻找递归出口寻找递归出口(1) n=1, X1Z(2) n=2, X1Y X2Z Y1Z26n阶阶Hanoi问题问题pHanoi(n,X,Y,Z)pn=3, Hanoi(2,X,Z,Y)p XZp Hanoi(2,Y,X,Z)3XYZ27CABCABABC(1) Hanoi(n-1,X,Z,Y)(2) X nZ(3) Hano

15、i(n-1,Y,X,Z)XYZHanoi(n,X,Y,Z)圆盘圆盘数量数量源柱源柱辅助辅助柱柱目标目标柱柱28n阶阶Hanoi问题问题procedure Hanoi(n, X, Y, Z) if (n 1) then move(X, Z) else Hanoi(n1, X, Z, Y) move(X, Z) Hanoi(n1, Y, X, Z) endifEnd Hanoi29例例3.5 棋子移动问题棋子移动问题 有有2n个棋子个棋子(n4)排成一行，白子用排成一行，白子用0表示，黑子用表示，黑子用1表示，例如表示，例如n=5时初始状态为右边至少有两个空位）时初始状态为右边至少有两个空位）0

16、0 0 0 0 1 1 1 1 1 _ _，（要求通过棋子移动最终成，（要求通过棋子移动最终成为为 0 1 0 1 0 1 0 1 0 1.30棋子移动问题棋子移动问题移动规则移动规则每次必须同时移动相邻两个棋子每次必须同时移动相邻两个棋子颜色不限，移动方向不限颜色不限，移动方向不限每次移动必须跳过若干棋子每次移动必须跳过若干棋子不能调换这两个棋子的位置不能调换这两个棋子的位置31pn=4 00001111_ _p step1 000_ _11101 (4,5)(9,10)p step2 0001011_ _1 (8,9)(4,5)p step3 0_ _1011001 (2,3)(8,9)p

17、 step4 010101_ _01 (7,8)(2,3)p step5 _ _01010101 (1,2)(7,8)寻找递归出口寻找递归出口32pn5 _ _p step1 0000_ _111101 (5,6)(11,12)p step2 00001111_ _01 (9,10)(5,6)pn6 0 1_ _p step1 00000_ _1111101 (6,7)(13,14)p step2 _ _01 (11,12)(6,7)chess(n)递归出口：递归出口：n4;递归过程：递归过程：n4时；时；move (n,n1)(2n1,2n2)；move (2n1,2n)(n,n1);cal

18、l chess(n1); 33棋子的移动问题棋子的移动问题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 ChessA(9)A(4)A(10)A(5)34例例3.6 求求n个元素的全排列个元素的全排列p设设A=a1,a2,an是要进行排列的是要进行排列

19、的n个元素的集合，个元素的集合，p n1 输出输出a1p n2 输出输出a1a2p a2a1p n3 输出输出a3a1a2 p a3a2a1 p a1a2a3 p a1a3a2p a2a1a3 p a2a3a1p 分析分析n=3，排列按如下步骤进行：，排列按如下步骤进行： a3之后跟之后跟a1,a2的所有全排列；的所有全排列；在上述全排列里，在上述全排列里，a3和和a1位置互换；位置互换；在上述全排列里，在上述全排列里，a3和和a2位置互换。位置互换。354. 求求n个元素的全排列个元素的全排列 range(A) a1range(A1) a2range(A2) , anrange(An)A-a

20、nA-a2A-a136求求n个元素的全排列个元素的全排列prange(A)p = a1range(A1), a2range(A2), anrange(An)p集合集合A用数组实现用数组实现prange(A,1,n)：p递归出口：递归出口：range(A, n, n)p递归调用：使得集合所有元素都可以作为前缀出现递归调用：使得集合所有元素都可以作为前缀出现37求求n个元素的全排列个元素的全排列procedure range(A, k, n) if kn then print(A) else for i k to n do A(k) A(i) call range(A,k1,n) A(k) A(i

21、) repeat endifend range递归出口，打印递归出口，打印整个数组整个数组A。A(i)与与A(k)值值互换互换call range(A,1,n)38range(A,1,3)If 1=3 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,bbac4) i2, a b Ab,a,c5) i2, aa Ab,a,cbca6) i3, ac Ab,c,arange(A,2,3)for

22、i2 to 3 do A(2)A(i); call range(A,3,3) 略略range(A,3,3)If 3=3 print(A) 略略7) i3, ac Ac,b,acba8) i2, bb Ac,b,acab9) i3, ba Ac,a,b39例例3.7 自然数拆分自然数拆分p任何一个大于任何一个大于1的自然数的自然数n，总可以拆分成，总可以拆分成若干个小于若干个小于n的自然数之和，试求的自然数之和，试求n的所有的所有拆分。拆分。pn2 211pn3 312p 111pn4 413p 112p 1111p 2240自然数拆分（正整数拆分）自然数拆分（正整数拆分）pn6 6 15p 1

23、14p 1113p 11112p 111111p 1122p 123p 24p 222p 3341自然数拆分（正整数拆分）自然数拆分（正整数拆分）p拆分的结果用一维数组拆分的结果用一维数组A保存；保存；p对任意自然数的所有拆分方式，依据对任意自然数的所有拆分方式，依据A(1)的值，的值，可以分为可以分为n/2类；类；p第第i类第一个元素是类第一个元素是A1i， A2ni；p为保证拆分不重复，为保证拆分不重复，A中元素是非降的。中元素是非降的。42自然数拆分（正整数拆分）算法自然数拆分（正整数拆分）算法procedure split(t) for k 1 to t do write(A(k) ;

24、 repeat j t; L A(j) for i A(j1) to L/2 do A(j) i; A(j1) 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输出已产生的输出已产生的一种拆分一种拆分本次拆本次拆分的起分的起始位置始位置本次拆分的本次拆分的数值数值用用A的下标来控的下标来控制下一次拆分制下一次拆分43split(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,1,1j4; L1i在11/2之间3sp