数据结构与程序设计-递归

第5章递归5.1 递归简介(Introduction to Recursion)5.2 递归的原理(Principles of Recursion)5.3 回溯: 将工作延迟(Backtracking: Postponing the Work)5.4 树形结构编程: 在游戏中提前考虑走法(Tree-Structured Programs: Look-Ahead in Games)n掌握：1.递归的概念：什么是递归、种类、及递归求解方法。

2.递归过程的机制与利用递归工作栈实现递归的方法。

3.利用递归解决问题的分治法和回溯法。

n了解：n迷宫问题和n皇后问题的递归思路及利用栈实现的非递归解法。

n目的：n通过实例分析递归执行的过程和实现的方式，从而使读者掌握递归适用的场合。

5.1 递归简介递归与递归程序的概念n递归(recursion)是一种描述和解决问题的基本方法，用来解决可归纳描述的问题，或说可分解为结构自相似的问题。

所谓结构自相似，是指构成问题的部分与问题本身在结构上相似。

n递归的定义n1)定义一个对象，又用到这个对象的本身；n2)定义一个结构，它的每一个部分又是这种结构；n3)定义一个过程，在执行中又直接或间接地调用过程自己；n递归程序n在计算机中，递归问题可使用递归程序解决。

5.1 递归简介n5.1.1 用于函数调用的堆栈n5.1.2 表示函数调用的树n5.1.3 用递归计算数的阶乘n5.1.4 用分治算法解决汉诺塔问题5.1.1 用于函数调用的堆栈n调用记录(invocation record)——为每个调用函数分配的临时存储区域，包括返回地址、调用参数、局部变量等n函数嵌套调用——函数按“后进先出”次序；执行函数所使用的临时存储区域也具有“后进先出”的特性；于是调用记录必须用“堆栈”保存n堆栈的变化状态(stack frame)P.158图5.1图5.1 stack frames for function callsn递归调用的stack frame与一般的函数调用类似。

5.1.2 表示函数调用的树n可以用“树”表示函数调用的次序(根节点代表主程序；其它节点代表所调用的某个函数)n与树有关的术语(孩子、双亲、分支、兄弟、叶子/外部节点、路径、树/节点的高度/层数、树的遍历)n递归树:P.159图5.2n用于存储“调用记录”的堆栈(stack frame)的空间需求——与递归树的高度成正比——于是可以利用递归树分析递归算法的性能。

图5.2 递归树5.1.4 递归应用:用分治法解决汉诺塔问题分治法n对于一个较为复杂的问题，如果能够分解成几个相对简单的且解法相同或类似的子问题来求解，这种方法叫分治法。

n Tower of Hanoi问题是一个典型的适合用递归的方法来解决的问题。

n问题描述：如图5.3所示，有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3……n。

要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：n每次只能移一个圆盘n圆盘可在三个塔座上任意移动n任何时刻，每个塔座上不能将大盘压到小盘上图5.3 Hanoi塔解决方法：n 1. n=1时，直接把圆盘从A移到Cn 2. n>1时，将n个圆盘从A塔座上移到C塔座上可以分为以下三个步骤进行：⑴将A塔座上的n-1个圆盘借助C塔座先移到B塔座上。

⑵把A塔座上剩下的一个圆盘移到C塔座上。

⑶将n-1个圆盘从B塔座借助A塔座移到C塔座上。

n这样就将求解n个圆盘的Hanoi问题转化为求解n-个圆盘的Hanoi问题,依次类推,直至转化成只有一个圆盘的Hanoi问题。

实现算法：//Main program:const int disks = 64; // Make this constant much smaller to run program.void move(int count, int start, int finish, int temp);/* Pre: None.Post: The simulation of the Towers of Hanoi has terminated. */main( ){move(disks, 1, 3, 2);}//Recursive function:void move(int count, int start, int finish, int temp){if (count > 0){move(count-1, start, temp, finish);cout<<"Move disk "<<count<<" from "<<start<<" to "<<finish<<"."<<endl;move(count-1, temp, finish, start);}}求解汉诺塔问题的递归树(n=3)n小结：n递归算法的效率往往很低, 费时和费内存空间. 但是递归也有其长处, 它能使一个蕴含递归关系且结构复杂的程序简介精炼, 增加可读性. 特别是在难于找到从边界到解的全过程的情况下, 如果把问题推进一步没其结果仍维持原问题的关系, 则采用递归算法编程比较合适.5.2 递归的原理n5.2.1 递归算法设计的原则n5.2.2 递归算法的机器实现n5.2.3 尾递归n5.2.4 用栈实现递归过程的非递归算法n注意：区分以下的概念n算法设计n算法实现n算法分析5.2.1 递归算法设计的原则n找出关键步骤Find the key stepn首先考虑“如何对问题进行划分?”、“中间的关键步骤如何实现?”n找出终止规则Find a stopping rulen终止规则通常是不需要递归且较易解决的较小的或特殊的情形n给出算法大纲Outline your algorithmn将关键步骤和终止规则组合起来，并且通过if语句区分这两种情形5.2.1 递归算法设计的原则(续)n检查终止性Check terminationn确保递归会终止，保证算法能够处理极端的情形n画出递归树Draw a recursion treen递归算法分析的工具n树的高度与程序运行时所需要的空间紧密相关，而树的结点数反映了执行关键步骤所需的时间5.2.1 递归算法设计的原则(续)总结：递归定义的两个要素§1）递归边界条件。

也就是所描述问题的最简单情况，它本身不再使用递归的定义。

例如裴波那契数列，当n=0时,f(n)=1,不使用f(n-1)来定义。

§2）递归定义：使问题向边界条件转化的规则。

递归定义必须能使问题越来越简单。

如上例：f(n)由f(n-1)定义，越来越靠近f(0),也即边界条件。

最简单的情况是f(0)=1。

n[例5.1]求裴波那契数列的递归程序为:int fib(int n){ if(n == 0)return1; // 递归边界else if(n == 1)return2;else return(fib(n-2)+ fib(n-1)); // 递归定义}n这类递归问题可转化为递推算法, 递归边界作为递推的边界条件.5.2.2 递归算法的机器实现递归和递归工作栈n在递归调用时，必须做好参数保存，参数传递工作——利用递归工作栈来处理。

1.递归算法是一次次以新的实参自身调用的过程，并且系统要设置栈，递归调用时返回地址等参数逐次进栈。

即每进入一层递归，系统就要建立一个新的工作记录(进栈)。

2.返回地址等参数出栈，由最末级调用逐次返回到上级。

即每退出一层递归，系统就要从递归工作栈退出工作记录(退栈)。

5.2.2 递归算法的机器实现(续)n在多处理机环境下的实现n每次递归调用在单独的处理机上实现n算法的并行执行大大提高了算法的性能n单处理机的实现n每次递归调用都要分配一个局部的存储区域，以存放调用前的寄存器状态、返回地址、局部变量、调用参数等。

n算法以完全串行的方式执行5.2.2 递归算法的机器实现(续)n单机分时系统n一个递归程序可由n个用户调用，每个用户具有各自独立的数据区，但共享同一个指令区域。

n程序的并发执行要求必须使程序是可重入的。

n问题：在以上3种不同的运行环境下，执行递归算法所需的时间、空间如何?5.2.3 尾递归n尾递归的含义(P.175图5.8)n DEFINITION：Tail recursion occurs when the last-executed statement of a function is a recursive call to itself.n区分“最后执行的语句”与“最后出现的语句”n去掉尾递归的好处n可以节省堆栈空间n去掉尾递归的方法n If the last-executed statement of a function is a recursive callto the function itself, then this call can be eliminated byreassigning the calling parameters to the values specified inthe recursive call, and then repeating the whole function.n将算法转化为迭代形式n尾递归优化举例——汉诺塔算法的改进void move(int count, int start, int finish, int temp){if (count > 0){move(count−1, start, temp, finish);cout<<"Move disk "<<count<<" from "<<start<<" to "<<finish<< "." <<endl;move(count−1, temp, finish, start);}}n尾递归，要将start作为temp、temp作为start，继续递归调用，故交换start和temp，可转化为迭代的形式，从而得到算法的改进。

消除尾递归的汉诺塔算法void move(int count, int start, int finish, int temp)/* move : iterative versionPre: Disk count is a valid disk to be moved.Post: Moves count disks from start to finish using temp for temporary storage. */{int swap; // temporary storage to swap towerswhile (count > 0){ // Replace the if statement with a loop.move(count−1, start, temp, finish); // first recursive callcout<<"Move disk "<<count<<" from "<<start<<" to "<<finish<< "."<<endl;count−−; //Change parameters to mimic the second recursive call.swap = start;start = temp;temp = swap;}}5.2.4 用栈实现递归过程的非递归算法n在编程中设置栈，将递归过程用非递归算法来解。