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

13.1递归算法实现机制3.3递归算法设计第三章递归算法2递归

定义一个过程直接地或间接地调用自己，则称这个过程是递归的过程。递归算法在计算机理论和实际应用中都具有重要意义递归算法特征：有递归调用、有递归出口设计和分析思路清晰，实现容易，效率较低33.1递归算法实现机制

子程序实现原理 子程序调用的形式 值回传方式 调用操作递归程序实现原理4proceduref（integern）begin if(n=0)return1 y

f（n-1）

return（n*y）； end递归求阶乘的算法主程序：integerfn；fn

f(4)；5为了保证递归调用的正确性，需要保存调用点的现场（返回地址、局部变量、被调用函数的参数等），以便正确地返回，并且按先进后出的原则来管理这些信息。高级语言编译程序是利用栈来实现的。f(n)f(n-1)f(n-2)f(1)f(0)调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场…调用返回调用点

PnPn-1Pn-2P116计算4!递归过程图示：下图中Pi代表现场信息，栈元素由现场信息和参数构成f(4)=4*f(3)f(3)=3*f(2)f(2)=2*f(1)f(1)=1*f(0)f(0)=1Push(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 =1P44P33P44P22P33P44P11P22P33P44Pop(e1)Pop(e2)Pop(e3)Pop(e4)73.3递归算法设计

通用形式 实际上是分治策略一些实例8

例1.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。9Hanoi塔要求：1）每次只能移动一个盘子；2）盘子可以放到ABC任何一个塔座上；3）任何时候，都不能将较大的盘子压在较小的圆盘之上；10Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，估计工作量。算法：N=2时第一步先把最上面的一个圆盘套在B上第二步把下面的一个圆盘移到C上

最后把B上的圆盘移到C上

到此转移完毕ABC11

对于一般n个圆盘的问题，

假定n-1个盘子的转移算法已经确定。

先把上面的n-1个圆盘经过C转移到B。

第二步把A下面一个圆盘移到C上

最后再把B上的n-1个圆盘经过A转移到C上ABC12

上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，…以此类推。13

算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。14算法复杂度递归关系式为：h(1)=1h(n)=2h(n-1)+1求解后：h(n)=2n-115递归关系式的求解方法：1、迭代法（本课程需要掌握）2、母函数法（简要介绍）3、公式法求解k阶线性齐次递归关系式16母函数以幂级数函数为例：数列a0,a1,a2,…,an,…用幂级数函数表达：f(x)=a0+a1x+a2x2+…+anxn+…以母函数运算求解系数表达式汉诺塔问题举例17例2：棋子移动(00…011…1--)(--0101…01)同时移动两枚相邻棋子；跳跃若干棋子算法：出口n=4Move(n,n+1)(2n+1,2n+2)Move(2n-1,2n)(n,n+1)CallChess(n-1)18时间复杂度:移动次数M(n