数据结构课件：05 第六章 递归

1、第六章 递 归第一节 递归的定义第二节 基本递归过程第三节 递归过程实现与堆栈第四节 递归法求解问题第五节 递归的效率第 1 页线性表第 2 页栈和递归在程序设计中的应用是非常广泛的，如对于迷宫的求解、表达式的求解等都可以用栈来解决。典型的hanoi塔问题，树和图的遍历等都可以用递归来解决。递归算法的设计实际上就是对问题的抽象的过程，如果抽象到每个小问题都有相同特征时，那就形成了递归，递归算法简明易懂。第 3 页 递归不仅是数学中的一个重要概念，也是计算技术中重要的概念之一。20世纪30年代，正是可计算的递归函数理论与图灵机演算和POST规范系统等理论一起为计算理论的建立奠定了基础。第 4 页

2、从方法论意义上说，递归方法是一种从简单到复杂、从低级到高级的可连续操作的解决问题的方法。 在人们的思维过程中，普遍存在着递归现象和递归机制。 对于某些问题，只能用递归方法来处理；对于某些问题，用递归方法处理比其他方法更有效。 第 5 页6.1 什么是递归 xn=x*x*x*x （n个x连乘） xn+1=xn * x S(n)=1+2+3+(n-1)+n S(n+1)=S(n)+(n+1)优点：直观、有效 第 6 页定义：如果一个对象部分地包含它自己，或者利用自己定义自己的方式来定义或描述，则称这个对象是递归的；如果一个过程直接或间接地调用自己，则称这个过程是一个递归过程。组成：递归调用、递归终

3、止条件第 7 页以下三种情况适于用递归求解问题：问题的定义是递归的问题所涉及的数据结构是递归的；问题的解法满足递归的性质。第 8 页1、问题的定义是递归的阶乘函数、幂函数和斐波那契数列。例阶乘函数的定义第 9 页求解阶乘函数的递归过程long Factorial(long n)if (n=0) return 1; /递归终止条件else return n * Factorial(n-1); /递归调用过程第 10 页求解 4! 的过程第 11 页计算斐波那契数列的函数Fib(n)的定义求解斐波那契数列的递归算法long Fib ( long n ) if ( n = 1 ) return n;

4、 else return Fib (n-1) + Fib (n-2);第 12 页递归求解的过程： 对于一个比较复杂的问题，如果能够把它分解为若干个相对简单的、而且解法相同或类似的子问题，那么当这些子问题获得解决时，原问题就获得解决分治策略。 子问题无需分解就可以直接解决时，停止分解，直接求解该子问题递归结束条件。第 13 页2、问题所涉及的数据结构是递归的例单链表 head=NULL7245head36第 14 页在头指针为p的单链表中搜索data值为item的结点template void Search（Node *p，T item）if（p = = NULL）cerr data = =

5、item）Dealwith（p）；/ 通过Dealwith函数对该节点进行一定的处理elseSearch（p-next，item）；第 15 页搜索链表最后一个结点并打印其数值template void Find (Node *f ) if ( f next = NULL ) cout f data endl; else Find ( f next );第 16 页二叉树：二叉树是数据元素的有穷集合，它或者为空集（空二叉 树），或者由一个根元素和其下的两棵互不相交的二叉树（左子树和右子树）构成。第 17 页3、问题的解法满足递归的性质例如，汉诺塔(Tower of Hanoi)问题 问题的提出

6、：在19世纪末，布拉玛神庙(Temple of Bramah)里的传教士玩着一种游戏，据说他们的游戏装置是由一块铜板上有三根金刚石针，针上放有64个直径大小不等的金盘组成的。游戏的目标是把左面针上的金盘移动到右面的针上，移动过程中一次只能移动一个盘子，不允许大盘放在小盘上面，只能借助于中间的针。他们认为这种游戏的结束就意味着世界末日的到来。欧洲人把这种游戏叫做汉诺塔(Tower of Hanoi)游戏。第 18 页第 19 页对于n阶汉诺塔进行一下分析：1.把n个盘子从上到下编号1n,要把n个盘子从a塔移动到c塔,首先借用b塔作为存放盘子的临时塔，把上面的n-1个盘子移动到b;2.把第n个盘子

7、移动到c3.那么如何把第n-1个盘子移动到c？ 可以把a作为临时塔，把第n-1盘子上面的n-2个盘子从b移动到a，把第n-2个盘子移动到c。这样n-2个盘子又回到了a上了。4.以此类推，下面n-2个盘子的移动仿佛是在重复第1、2步操作，这个问题变成了典型的递归问题。第 20 页void Hanoi (int n, String A, String B, String C ) /解决汉诺塔问题的算法 if ( n = 1 ) cout move A to C endl; else Hanoi ( n-1, A, C, B ); cout move A to C endl; Hanoi ( n-1

8、, B, A, C ); 第 21 页6.2基本递归过程 递归过程在实现时，发生递归调用：分为内部调用和外部调用。 调用方式不同，返回的方式也不相同。递归调用正确进行：调用时参数传递正确过程结束正确返回：返回地址正确第 22 页在高级语言（编译程序）中，是利用“递归工作栈”来实现递归调用的。 f(n) f(n-1) f(n-2) f(1) f(0)调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场调用返回调用点 PnPn-1Pn-2P11第 23 页层层向下递归，退出时的次序正好相反：递归次序n! (n-1)! (n-2)! 1! 0!=1 返回次序工作记录：返回地址参数 （函数名、引用参

9、数与数组参数等）局部变量第 24 页函数递归时的活动记录第 25 页 long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1); RetLoc2 void main ( ) int Result; Result = Factorial (4);RetLoc1 第 26 页计算Factorial时活动记录的内容第 27 页堆栈:递归算法转化为非递归算法CREATS ( S )：建立一个堆栈 S;S x : 元素 x 进栈； x S : 元素 x 出栈；StackEmpty(S): 若 S 为空

10、，返回1.最后一次发生的递归过程必须最先完成。6.3递归过程的实现：堆栈与递归第 28 页例2.3 计算数组 A 中最大最小元素的算法BS 。算法BS（A ，i ，j . fmax ，fmin）/ 在数组A的第i个元素到第j个元素之间寻找最大和最小元素，已知i j 。BS1 递归出口 IF i = j THEN （ fmaxfminAi. RETURN. ） IF i = j 1 THEN（ IF Ai n THEN RETURN(0). ELSE IF(n = k OR k = 0) THEN RETURN(1).COMM2递归调用RETURN (COMM(n-1, k) + COMM(n-

11、1, k-1) 第 42 页递归的应用回溯(backtracking)寻找特定问题解的一种比较可靠的方法是首先列出所有候选解，然后依次检查每一个候选解，在检查完所有或部分候选解后，即可找到所需要的解。 理论上，当候选解的数量有限并且通过检查所有或部分候选解能够得到所需要的解的时候，上述方法是可行的。 对候选解进行系统检查的方法有多种，其中回溯和分枝限界法是比较常用的两种。6.4.2 回 溯第 43 页 回溯法试图通过建立部分的解决方法来得到整个问题的解决方案。该算法可将一个局部的解决方法扩展到整个问题。 如果从局部的解决方法肯定不能得到整个问题的解决方案，也就是说局部的解将导致走进死胡同，这时

12、就要通过移除最近加入的部分将算法回退，并且尝试其他的方法。第 44 页回溯的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。 回溯法解决的问题：货船装箱、背包、最大完备子图、旅行商和电路板排列第 45 页迷宫老鼠问题2,12,22,31,11,21,33,13,23,3第 46 页 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0 0 0(1,1)(1,2) (1,3)失败，回溯到(1,2)(1,1) (2,1) (3,1) (3,2) (3,3)第 47

13、页迷宫问题小型迷宫 路口 动作 结果 1(入口) 正向走 进到 2 2 左拐弯 进到 3 3 右拐弯 进到 4 4(堵死) 回溯 退到 3 3(堵死) 回溯 退到 2 2 正向走 进到 5 5(堵死) 回溯 退到 2 2 右拐弯 进到 6 6 左拐弯 进到 7 (出口)7643521第 48 页例： n-皇后问题在国际象棋中，最强大的棋子是皇后，因为她能攻击她所在行、所在列内或沿对角方向的任何一个棋子。n-皇后问题要求在棋盘上放置n个皇后，使得没有哪个皇后能攻击其他的皇后。 第 49 页在回溯中，由于每个皇后都必须放置在不同的行中，所以n-皇后问题的解决方案可以表示为一个n元组(x1, , x

14、n)，这里的xi 是把第i个皇后放在第i行的列数且1 xi n. 由于任何两个皇后都不能出现在同一列中，因此n元组(x1, , xn)中没有两个元素是相同的。那么，应该如何判断两个皇后是否在同一斜角线上呢？第 50 页 如果设想棋盘的方格像二维数组A(1: n, 1: n)的下标那样标记，对于在同一条斜角线上的由左上方到右下方的每一个元素都有相同的“行列”值，同样，在同一条上的由右上方到左下方的每一个元素则有相同的“行+列”值。假设有两个皇后被放置在(i, j)和(k, l)位置上，那么根据以上所述，仅当 ij kl 或 i+j k+l时，它们才在同一条斜角线上。将这两个等式分别变换成 jl

15、ik 或 jl ki因此，当且仅当 | jl | | ik | 时，两个皇后在同一条斜角线上，这里的| jl |为jl的绝对值。第 51 页n-皇后问题的解为一个n元组，使用一个大小为n的数组queenInRow来存储。其中queenInRow k表示第k行的第k个皇后所在列的位置。例如queenInRow 1=7表示第一个皇后被放在第一行、第7列。假设已经将第k-1个皇后放入第k-1行中，接下来尝试将第k个皇后放入第k行的某一列。编写算法PLACE(k, i . result)，当第k个皇后能放置于第k行第i列则返回true；否则返回false。第 52 页算法PLACE要测试两种情况，即q

16、ueenInRow k是否不同于前面queenInRow 1，queenInRowk1的值以及在同一条斜角线上是否有别的皇后。 第 53 页算法PLACE( k, i . result)/*如果一个皇后能放在第k行第i列则返回true；否则返回false，结果保存在result中 */PLACE1 初始化 j1.PLACE2 判定能否放置 第 54 页WHILE j 0) do X(k)X(k)+1; while ( X(k)n and Not PLACE(k) ) do X(k)X(k)+1; repeat if (X(k)n) then if (k=n) then print (X); e

17、lse kk+1; X(k)0; endif else kk-1; endifrepeatend NQUEENS/若是一个完整的解则打印数组X/ k是当前行; X(k)是当前列 / 对所有的行执行循环语句/移到下一列当该位置不能放皇后时转到下一列/找到一个位置/否则转到下一行/ 没有合适的位置, 回溯第 57 页递归方法虽然在解决某些问题时是最直观、最方便的方法，但却不是一种高效的方法，主要原因在于递归方法过于频繁的函数调用和参数传递。在这种情况下，若采用循环或递归算法的非递归实现，将会大大提高算法的执行效率。6.5 递归的效率 第 58 页调用次数 SumCall(k) = SumCall(

18、k-1)+SumCall(k-2)+1斐波那契数列的递归调用树第 59 页由此可以计算出算法的复杂度为O(2k)，递归算法的运行时间是指数级的。如果我们采用简单的循环语句计算斐波那契数列的第n项，则算法的复杂度为O(n)。用循环实现计算斐波那契数列的方法：如果n为0或1则返回n值，否则用循环进行迭代计算。第 60 页计算斐波那契数列的非递归函数long CalFib（long n） if（n = 1） return n；else long f1 = 1，f2 = 0，f = 0；for（ int i = 2；i = n；i+） f = f1+f2；f2 = f1；f1 = f；return f；第 61 页当k=35时，斐波那契数迭代函数需进行33次加法，而递归函数需要进行185万次函数调用！斐波那契数的例子对于使用递归方案可能带来的问题是个很好的警示。由于函数调用产生的额外开销，一个简单的递归函数也有可能严重地损害程序的运行性能。更严重的结果是，一次递