数据结构课件：05、第六章 递归[新][荐]

1、数据结构数据结构 精品课程精品课程第第 1 页页第六章第六章 递递 归归第一节第一节 递归的定义递归的定义第二节第二节 基本递归过程基本递归过程第三节第三节 递归过程实现与堆栈递归过程实现与堆栈第四节第四节 递归法求解问题递归法求解问题第五节第五节 递归的效率递归的效率数据结构数据结构 精品课程精品课程第第 2 页页线性表线性表数据结构数据结构 精品课程精品课程第第 3 页页栈和递归在程序设计中的应用是非常栈和递归在程序设计中的应用是非常广泛的，如对于迷宫的求解、表达式的广泛的，如对于迷宫的求解、表达式的求解等都可以用栈来解决。典型的求解等都可以用栈来解决。典型的hanoihanoi塔问题，树

2、和图的遍历等都可以用递归塔问题，树和图的遍历等都可以用递归来解决。递归算法的设计实际上就是对来解决。递归算法的设计实际上就是对问题的抽象的过程，如果抽象到每个小问题的抽象的过程，如果抽象到每个小问题都有相同特征时，那就形成了递归，问题都有相同特征时，那就形成了递归，递归算法简明易懂。递归算法简明易懂。数据结构数据结构 精品课程精品课程第第 4 页页 递归不仅是数学中的一个重要概念，递归不仅是数学中的一个重要概念，也是计算技术中重要的概念之一。也是计算技术中重要的概念之一。20世世纪纪30年代，正是可计算的递归函数理论年代，正是可计算的递归函数理论与图灵机演算和与图灵机演算和POST规范系统等理

3、论规范系统等理论一起为计算理论的建立奠定了基础。一起为计算理论的建立奠定了基础。数据结构数据结构 精品课程精品课程第第 5 页页从方法论意义上说，递归方法是一种从从方法论意义上说，递归方法是一种从简单到复杂、从低级到高级的可连续操作的解简单到复杂、从低级到高级的可连续操作的解决问题的方法。决问题的方法。 在人们的思维过程中，普遍存在着递归在人们的思维过程中，普遍存在着递归现象和递归机制。现象和递归机制。 对于某些问题，只能用递归方法来处理；对于某些问题，只能用递归方法来处理；对于某些问题，用递归方法处理比其他方法更对于某些问题，用递归方法处理比其他方法更有效。有效。 数据结构数据结构 精品课程

4、精品课程第第 6 页页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)优点：优点：直观、有效直观、有效 数据结构数据结构 精品课程精品课程第第 7 页页定义：定义：如果一个对象部分地如果一个对象部分地包含包含它自己，它自己，或者利用自己定义自己的方式来定或者利用自己定义自己的方式来定义或描述，则称义或描述，则称这个对象这个对象是递归的；是递归的；如果一个过程如果一个过程直接或间接直接或间接地调用自地调用自己，则称这个己，则称这个过程是过程是一个递归过程。一个递归过程。组成：

5、组成：递归调用、递归终止条件递归调用、递归终止条件数据结构数据结构 精品课程精品课程第第 8 页页以下三种情况适于用递归求解问题：以下三种情况适于用递归求解问题：1.问题的定义是递归的问题的定义是递归的2.问题所涉及的数据结构是递归的；问题所涉及的数据结构是递归的；3.问题的解法满足递归的性质。问题的解法满足递归的性质。数据结构数据结构 精品课程精品课程第第 9 页页1、问题的定义是递归的、问题的定义是递归的阶乘函数、幂函数阶乘函数、幂函数和和斐波那契数列。斐波那契数列。例例阶乘函数的定义阶乘函数的定义 0n ! 10n 1!nnn数据结构数据结构 精品课程精品课程第第 10 页页求解阶乘函数

6、的递归过程求解阶乘函数的递归过程long Factorial(long n)if (n=0) return 1; /递归终止条件递归终止条件else return n * Factorial(n-1); /递归调用过程递归调用过程数据结构数据结构 精品课程精品课程第第 11 页页求解求解 4! 的过程的过程数据结构数据结构 精品课程精品课程第第 12 页页计算斐波那契数列的函数计算斐波那契数列的函数Fib(n)的定义的定义1),2() 1(0,1,)(nnFibnFibnnnFib求解斐波那契数列的递归算法求解斐波那契数列的递归算法long Fib ( long n ) if ( n = 1

7、) return n; else return Fib (n- -1) + Fib (n- -2);数据结构数据结构 精品课程精品课程第第 13 页页递归求解的过程：递归求解的过程： 对于一个比较复杂的问题，如果能够对于一个比较复杂的问题，如果能够把它把它分解分解为若干个为若干个相对简单相对简单的、而且的、而且解法解法相同相同或或类似类似的子问题，那么当这些子问题的子问题，那么当这些子问题获得解决时，原问题就获得解决分治获得解决时，原问题就获得解决分治策略。策略。 子问题无需分解就可以直接解决时，子问题无需分解就可以直接解决时，停止分解，直接求解该子问题停止分解，直接求解该子问题递归结递归结束

8、条件。束条件。数据结构数据结构 精品课程精品课程第第 14 页页2、问题所涉及的数据结构是递归的例单链表 head=NULL7245head36数据结构数据结构 精品课程精品课程第第 15 页页在头指针为在头指针为p的单链表中搜索的单链表中搜索data值为值为item的结点的结点template void Search（Node *p，T item）if（p = = NULL）cerr data = = item）Dealwith（p）；）；/ 通过通过Dealwith函数对函数对该节点进行一定的处理该节点进行一定的处理elseSearch（p-next，item）；）；数据结构数据结构 精品

9、课程精品课程第第 16 页页搜索链表最后一个结点并打印其数值搜索链表最后一个结点并打印其数值template void Find (Node *f ) if ( f next = NULL ) cout f data endl; else Find ( f next );数据结构数据结构 精品课程精品课程第第 17 页页二叉树：二叉树是数据元素的有穷二叉树：二叉树是数据元素的有穷集合，它或者为空集（空二叉集合，它或者为空集（空二叉 树），或者由一个根元素和其下的两树），或者由一个根元素和其下的两棵互不相交的二叉树（左子树和右子棵互不相交的二叉树（左子树和右子树）构成。树）构成。数据结构数据结构

10、 精品课程精品课程第第 18 页页3、问题的解法满足递归的性质例如，汉诺塔例如，汉诺塔(Tower of Hanoi)问题问题 问题的提出：问题的提出：在在19世纪末，布拉玛神庙世纪末，布拉玛神庙(Temple of Bramah)里的传教士玩着一种游戏，里的传教士玩着一种游戏，据说他们的游戏装置是由一块铜板上有三根金刚据说他们的游戏装置是由一块铜板上有三根金刚石针，针上放有石针，针上放有64个直径大小不等的金盘组成的。个直径大小不等的金盘组成的。游戏的目标是把左面针上的金盘移动到右面的针游戏的目标是把左面针上的金盘移动到右面的针上，移动过程中一次只能移动一个盘子，不允许上，移动过程中一次只能

11、移动一个盘子，不允许大盘放在小盘上面，只能借助于中间的针。他们大盘放在小盘上面，只能借助于中间的针。他们认为这种游戏的结束就意味着世界末日的到来。认为这种游戏的结束就意味着世界末日的到来。欧洲人把这种游戏叫做汉诺塔欧洲人把这种游戏叫做汉诺塔(Tower of Hanoi)游戏。游戏。数据结构数据结构 精品课程精品课程第第 19 页页数据结构数据结构 精品课程精品课程第第 20 页页对于对于n阶汉诺塔进行一下分析：阶汉诺塔进行一下分析：1.把把n个盘子从上到下编号个盘子从上到下编号1n,要把要把n个盘子从个盘子从a塔移动到塔移动到c塔塔,首先借用首先借用b塔作为存放盘子的临时塔作为存放盘子的临时

12、塔，把上面的塔，把上面的n-1个盘子移动到个盘子移动到b;2.把第把第n个盘子移动到个盘子移动到c3.那么如何把第那么如何把第n-1个盘子移动到个盘子移动到c？ 可以把可以把a作为临时塔，把第作为临时塔，把第n-1盘子上面的盘子上面的n-2个盘子从个盘子从b移动到移动到a，把第，把第n-2个盘子移动到个盘子移动到c。这。这样样n-2个盘子又回到了个盘子又回到了a上了。上了。4.以此类推，下面以此类推，下面n-2个盘子的移动仿佛是在重复个盘子的移动仿佛是在重复第第1、2步操作，这个问题变成了典型的递归问题。步操作，这个问题变成了典型的递归问题。数据结构数据结构 精品课程精品课程第第 21 页页v

13、oid 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, B, A, C ); 数据结构数据结构 精品课程精品课程第第 22 页页6.2基本递归过程基本递归过程 递归过程在实现时，发生递归调用：递归过程在实现时，发生递归调用：分为分为内部调用和外部调用内部调用和外部调用。 调用方式不同，返回的方式也不相同。调用方式不同，返回的方式也不相同。v递归调用正

14、确进行：调用时参数传递正递归调用正确进行：调用时参数传递正确确v过程结束正确返回：返回地址正确过程结束正确返回：返回地址正确数据结构数据结构 精品课程精品课程第第 23 页页在高级语言（编译程序）中，是利用在高级语言（编译程序）中，是利用“递归工作栈递归工作栈”来来实现递归调用的。实现递归调用的。 f(n) f(n-1) f(n-2) f(1) f(0)调用时执行入栈操作保存现场，返回时执行出栈调用时执行入栈操作保存现场，返回时执行出栈操作恢复现场操作恢复现场调用调用返回返回调用点调用点 PnPn-1Pn-2P11数据结构数据结构 精品课程精品课程第第 24 页页层层向下递归，退出时的次序正好

15、相反：层层向下递归，退出时的次序正好相反：递归次序递归次序n! (n-1)! (n-2)! 1! 0!=1 返回次序返回次序工作记录：工作记录：返回地址返回地址参数参数 （函数名、引用参数与数组参数等）（函数名、引用参数与数组参数等）局部变量局部变量数据结构数据结构 精品课程精品课程第第 25 页页函数递归时的活动记录函数递归时的活动记录数据结构数据结构 精品课程精品课程第第 26 页页 long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1); RetLoc2 void main ( )

16、int Result; Result = Factorial (4);RetLoc1 数据结构数据结构 精品课程精品课程第第 27 页页数据结构数据结构 精品课程精品课程第第 28 页页堆栈堆栈: :递归算法转化为非递归算法递归算法转化为非递归算法CREATS ( S )：建立一个堆栈：建立一个堆栈 S;S x : 元素元素 x 进栈；进栈； x S : 元素元素 x 出栈；出栈；StackEmpty(S): 若若 S 为空，返回为空，返回1.最后一次发生的递归过程必须最先完成。最后一次发生的递归过程必须最先完成。6.3递归过程的实现：堆栈与递归递归过程的实现：堆栈与递归数据结构数据结构 精品

17、课程精品课程第第 29 页页例例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 (C

18、OMM(n-1, k) + COMM(n-1, k-1) 数据结构数据结构 精品课程精品课程第第 43 页页递归的应用回溯递归的应用回溯(backtracking)寻找特定问题解的一种比较可靠的方法是首先列出寻找特定问题解的一种比较可靠的方法是首先列出所有候选解，然后依次检查每一个候选解，在检查所有候选解，然后依次检查每一个候选解，在检查完所有或部分候选解后，即可找到所需要的解。完所有或部分候选解后，即可找到所需要的解。 理理论上，当候选解的数量有限并且通过检查所有或部论上，当候选解的数量有限并且通过检查所有或部分候选解能够得到所需要的解的时候，上述方法是分候选解能够得到所需要的解的时候，上述

19、方法是可行的。可行的。 对候选解进行系统检查的方法有多种，其对候选解进行系统检查的方法有多种，其中中回溯回溯和分枝限界法是比较常用的两种。和分枝限界法是比较常用的两种。6.4.2 回回 溯溯数据结构数据结构 精品课程精品课程第第 44 页页 回溯法试图通过建立部分的解决方法来回溯法试图通过建立部分的解决方法来得到整个问题的解决方案。该算法可将一个得到整个问题的解决方案。该算法可将一个局部的解决方法扩展到整个问题。局部的解决方法扩展到整个问题。 如果从局部的解决方法肯定不能得到整如果从局部的解决方法肯定不能得到整个问题的解决方案，也就是说局部的解将导个问题的解决方案，也就是说局部的解将导致走进死

20、胡同，这时就要通过移除最近加入致走进死胡同，这时就要通过移除最近加入的部分将算法回退，并且尝试其他的方法。的部分将算法回退，并且尝试其他的方法。数据结构数据结构 精品课程精品课程第第 45 页页回溯的基本思想是：为了求得问题的解，先选回溯的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至新选择，继续向前探索，如此反复进行，直至得到解或证明无解。得到解或证明无解。 回溯法解决的问题：回溯法解决的问题：货船装箱、背

21、包、最大完货船装箱、背包、最大完备子图、旅行商和电路板排列备子图、旅行商和电路板排列数据结构数据结构 精品课程精品课程第第 46 页页迷宫老鼠问题2,12,22,31,11,21,33,13,23,3数据结构数据结构 精品课程精品课程第第 47 页页 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)数据结构数据结构 精品课程精品课程第第 48 页页迷宫问题迷宫问题小型迷宫小型迷宫 路口 动作 结果 (入口) 正向走 进到 左拐弯 进到 右拐弯 进到 (

22、堵死) 回溯 退到 (堵死) 回溯 退到 正向走 进到 (堵死) 回溯 退到 右拐弯 进到 左拐弯 进到 (出口)数据结构数据结构 精品课程精品课程第第 49 页页例：例： n-皇后问题皇后问题在国际象棋中，最强大的棋子是皇后，在国际象棋中，最强大的棋子是皇后，因为她能攻击她所在行、所在列内或因为她能攻击她所在行、所在列内或沿对角方向的任何一个棋子。沿对角方向的任何一个棋子。n-皇后皇后问题要求在棋盘上放置问题要求在棋盘上放置n个皇后，使个皇后，使得没有哪个皇后能攻击其他的皇后。得没有哪个皇后能攻击其他的皇后。 数据结构数据结构 精品课程精品课程第第 50 页页在回溯中，由于每个皇后都必须放置

23、在在回溯中，由于每个皇后都必须放置在不同的行中，所以不同的行中，所以n-皇后问题的解决方皇后问题的解决方案可以表示为一个案可以表示为一个n元组元组(x1, , xn)，这，这里的里的xi 是把第是把第i个皇后放在第个皇后放在第i行的列数且行的列数且1 xi n. 由于任何两个皇后都不能出现由于任何两个皇后都不能出现在同一列中，因此在同一列中，因此n元组元组(x1, , xn)中没中没有两个元素是相同的。有两个元素是相同的。那么，应该如何判断两个皇后是否在同那么，应该如何判断两个皇后是否在同一斜角线上呢？一斜角线上呢？数据结构数据结构 精品课程精品课程第第 51 页页 如果设想棋盘的方格像二维数

24、组如果设想棋盘的方格像二维数组A(1: n, 1: n)的的下标那样标记，对于在同一条斜角线上的由左上下标那样标记，对于在同一条斜角线上的由左上方到右下方的每一个元素都有相同的方到右下方的每一个元素都有相同的“行行 列列”值，值，同样，在同一条上的由右上方到左下方的每一个同样，在同一条上的由右上方到左下方的每一个元素则有相同的元素则有相同的“行行+列列”值。假设有两个皇后被值。假设有两个皇后被放置在放置在(i, j)和和(k, l)位置上，那么根据以上所述，仅位置上，那么根据以上所述，仅当当 i j k l 或或 i+j k+l时，它们才在同一条斜角线上。将这两个等式分时，它们才在同一条斜角线

25、上。将这两个等式分别变换成别变换成 j l i k 或或 j l k i因此，当且仅当因此，当且仅当 | j l | | i k | 时，两个皇后在同时，两个皇后在同一条斜角线上，这里的一条斜角线上，这里的| j l |为为j l的绝对值。的绝对值。数据结构数据结构 精品课程精品课程第第 52 页页n-皇后问题的解为一个皇后问题的解为一个n元组，使用一个大元组，使用一个大小为小为n的数组的数组queenInRow来存储。其中来存储。其中queenInRow k表示第表示第k行的第行的第k个皇后所个皇后所在列的位置。例如在列的位置。例如queenInRow 1=7表示表示第一个皇后被放在第一行、

26、第第一个皇后被放在第一行、第7列。列。假设已经将第假设已经将第k-1个皇后放入第个皇后放入第k-1行中，行中，接下来尝试将第接下来尝试将第k个皇后放入第个皇后放入第k行的某一行的某一列。编写算法列。编写算法PLACE(k, i . result)，当第，当第k个皇后能放置于第个皇后能放置于第k行第行第i列则返回列则返回true；否；否则返回则返回false。数据结构数据结构 精品课程精品课程第第 53 页页算法算法PLACE要测试两种情况，即要测试两种情况，即queenInRow k是否不同于前面是否不同于前面queenInRow 1，queenInRowk 1的值以及在同一条斜角线上是否有别

27、的的值以及在同一条斜角线上是否有别的皇后。皇后。 数据结构数据结构 精品课程精品课程第第 54 页页算法算法PLACE( k, i . result)/*如果一个皇后能放在第如果一个皇后能放在第k行第行第i列则返回列则返回true；否则返回；否则返回false，结果保存在，结果保存在result中中 */PLACE1 初始化初始化 j1.PLACE2 判定能否放置判定能否放置 数据结构数据结构 精品课程精品课程第第 55 页页WHILE j k DO( IF queenInRow (j) = i /*列列i中已经放置皇后中已经放置皇后*/OR ABS(queenInRow j i) = ABS

28、(j k) /*斜角线上已经放皇后了斜角线上已经放皇后了*/ THEN (resultfalse. RETURN(result). ) jj+1.) resulttrue. RETURN (result). 数据结构数据结构 精品课程精品课程第第 56 页页算法算法NQUEENS( k)/*此算法使用递归算法求出在一个此算法使用递归算法求出在一个nn的棋盘上放置的棋盘上放置n个个皇后，使其不能互相攻击的所有可能位置皇后，使其不能互相攻击的所有可能位置 */NQUEENS1 FOR i = 1 TO n DO ( PLACE(k,i. canPlace). /*此处能放这个皇后吗此处能放这个皇后

29、吗*/ IF canPlace = true THEN /*能放置能放置*/ ( queenInRowki. IF k= n THEN PRINT(queenInRow). /*找找到一个解，打印到一个解，打印*/ ELSE NQUEENS(k+1). /*考虑下一个皇后考虑下一个皇后*/ ) )数据结构数据结构 精品课程精品课程第第 57 页页递归方法虽然在解决某些问题时是最直观、最方便的方法，但却不是一种高效的方法，主要原因在于递归方法过于频繁的函数调用和参数传递。在这种情况下，若采用循环或递归算法的非递归实现，将会大大提高算法的执行效率。6.5 递归的效率递归的效率 数据结构数据结构 精

30、品课程精品课程第第 58 页页斐波那契数列的递归调用树斐波那契数列的递归调用树数据结构数据结构 精品课程精品课程第第 59 页页由此可以计算出算法的复杂度为由此可以计算出算法的复杂度为O(2k)，递归算法的运行时间是指数级的。递归算法的运行时间是指数级的。如果我们采用简单的循环语句计算斐波如果我们采用简单的循环语句计算斐波那契数列的第那契数列的第n项，则算法的复杂度为项，则算法的复杂度为O(n)。用循环实现计算斐波那契数列的方法：用循环实现计算斐波那契数列的方法：如果如果n为为0或或1则返回则返回n值，否则用循环进值，否则用循环进行迭代计算。行迭代计算。数据结构数据结构 精品课程精品课程第第 60 页页计算斐波