《数据结构C语言版》----第06章.ppt

《《数据结构C语言版》----第06章.ppt》由会员分享，可在线阅读，更多相关《《数据结构C语言版》----第06章.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、存在算法调用自己的情况：存在算法调用自己的情况：若一个算法直接的或间接的若一个算法直接的或间接的调用自己本身调用自己本身，则称这，则称这个算法是递归算法。个算法是递归算法。（1 1）问题的定义是递推的）问题的定义是递推的阶乘阶乘函数的函数的常见定义常见定义是：是：6.16.1递归的概念递归的概念2也可也可定义为：定义为：写成写成函数形式，则为：函数形式，则为：这种函数定义的方法是这种函数定义的方法是用阶乘函数自己本身定义了阶用阶乘函数自己本身定义了阶乘函数乘函数，称公式（称公式（63）是阶乘函数的）是阶乘函数的递推定义式递推定义式。3（2）问题的解法存在自调用）问题的解法存在自调用 一一个个典

2、典型型的的例例子子是是在在有有序序数数组组中中查查找找一一个个数数据据元元素素是是否否存在的存在的折半查找算法折半查找算法。4图图6-1 6-1 折半查找过程折半查找过程 56.26.2递归算法的执行过程递归算法的执行过程 例例6-1 6-1 给给出出按按照照公公式式6-36-3计计算算阶阶乘乘函函数数的的递递归归算算法法，并给出并给出n=3n=3时递归算法的执行过程。时递归算法的执行过程。设计：按照公式设计：按照公式6-36-3计算阶乘函数的递归算法如下：计算阶乘函数的递归算法如下：6longintFact(intn)intx;longinty;if(n0)/nhigh)return-1;/

3、查找不成功查找不成功mid=(low+high)/2;if(x=amid)returnmid;/查找成功查找成功elseif(xamid)returnBSearch(a,x,low,mid-1);/在下半区查找在下半区查找elsereturnBSearch(a,x,mid+1,high);/在上半区查找在上半区查找11测试主函数设计如下：测试主函数设计如下：#includemain(void)inta=1,3,4,5,17,18,31,33;intx=17;intbn;bn=BSearch(a,x,0,7);if(bn=-1)printf(x不在数组不在数组a中中);elseprintf(x在

4、数组在数组a的下标的下标%d中中,bn);12BSearch(aBSearch(a,x,0,7),x,0,7)的递归调用过程如图的递归调用过程如图6-36-3所示，所示，其中，其中，实箭头表示函数调用，虚箭头表示函数的返回值。实箭头表示函数调用，虚箭头表示函数的返回值。图图6-3 6-3 BSearch(aBSearch(a,x,0,7),x,0,7)的递归调用过程的递归调用过程 13146.36.3递归算法的设计方法递归算法的设计方法 递递归归算算法法既既是是一一种种有有效效的的算算法法设设计计方方法法，也也是是一一种种有有效效的的分析问题的方法。分析问题的方法。递递归归算算法法求求解解问问

5、题题的的基基本本思思想想是是：对对于于一一个个较较为为复复杂杂的的问问题题，把把原原问问题题分分解解成成若若干干个个相相对对简简单单且且类类同同的的子子问问题题,这这样样，原原问题就可递推得到解。问题就可递推得到解。15 适宜于用递归算法求解的问题的适宜于用递归算法求解的问题的充分必要条件是：充分必要条件是：（1 1）问题具有某种可借用的类同自身的子问题描述的性）问题具有某种可借用的类同自身的子问题描述的性质；质；（2 2）某一有限步的子问题（也称作本原问题）有直接的）某一有限步的子问题（也称作本原问题）有直接的解存在。解存在。当一个问题存在上述两个基本要素时，该问题的当一个问题存在上述两个基

6、本要素时，该问题的递归算递归算法的设计方法是：法的设计方法是：（1 1）把对原问题的求解设计成包含有对子问题求解的形）把对原问题的求解设计成包含有对子问题求解的形式。式。（2 2）设计递归出口。）设计递归出口。16例例6-3 6-3 设设计计模模拟拟汉汉诺诺塔塔问问题题求求解解过过程程的的算算法法。汉汉诺诺塔塔问问题题的的描描述述是是：设设有有3 3根根标标号号为为A A，B B，C C的的柱柱子子，在在A A柱柱上上放放着着n n个个盘盘子子，每每一一个个都都比比下下面面的的略略小小一一点点，要要求求把把A A柱柱上上的的盘盘子子全全部部移移到到C C柱柱上，上，移动的规则移动的规则是：是：

7、（1 1）一次只能移动一个盘子；）一次只能移动一个盘子；（2 2）移动过程中大盘子不能放在小盘子上面；）移动过程中大盘子不能放在小盘子上面；（3 3）在在移移动动过过程程中中盘盘子子可可以以放放在在A A，B B，C C的的任任意意一一个个柱柱子子上。上。17问题分析：问题分析：可以用递归方法求解可以用递归方法求解n n个盘子的汉诺塔问题。个盘子的汉诺塔问题。基本思想基本思想：1 1个盘子的汉诺塔问题可直接移动。个盘子的汉诺塔问题可直接移动。n n个盘子的汉个盘子的汉诺塔问题可递归表示为，首先把上边的诺塔问题可递归表示为，首先把上边的n-1n-1个盘子从个盘子从A A柱柱移到移到B B柱，然后

8、把最下边的一个盘子从柱，然后把最下边的一个盘子从A A柱移到柱移到C C柱，最后柱，最后把移到把移到B B柱的柱的n-1n-1个盘子再移到个盘子再移到C C柱。柱。4 4个盘子汉诺塔问题个盘子汉诺塔问题的递归求解示意图如图的递归求解示意图如图6-46-4所示。所示。18图图6-4 6-4 汉诺塔问题的递归求解示意图汉诺塔问题的递归求解示意图19算法设计：算法设计：首先，盘子的个数首先，盘子的个数n n是必须的一个输入参数，是必须的一个输入参数，对对n n个盘子个盘子,我们可从上至下依次编号为我们可从上至下依次编号为1,2,1,2,n,n；其次，输其次，输入参数还需有入参数还需有3 3个柱子的代

9、号个柱子的代号,我们令我们令3 3个柱子的参数名分别个柱子的参数名分别为为fromPegfromPeg，auxPegauxPeg和和toPegtoPeg；最后，汉诺塔问题的求解是一最后，汉诺塔问题的求解是一个处理过程，因此算法的输出是个处理过程，因此算法的输出是n n个盘子从柱子个盘子从柱子fromPegfromPeg借助借助柱子柱子auxPegauxPeg移动到柱子移动到柱子toPegtoPeg的移动步骤，我们设计每一步的移动步骤，我们设计每一步的移动为屏幕显示如下形式的信息：的移动为屏幕显示如下形式的信息：Move Disk i from Peg X to Peg YMove Disk i

10、 from Peg X to Peg Y 这样，汉诺塔问题的这样，汉诺塔问题的递归算法可设计如下：递归算法可设计如下：20voidtowers(intn,charfromPeg,chartoPeg,charauxPeg)if(n=1)/递归出口递归出口printf(%s%c%s%cn,movedisk1frompeg,fromPeg,topeg,toPeg);return;/把把n-1个圆盘从个圆盘从fromPeg借助借助toPeg移至移至auxPegtowers(n-1,fromPeg,auxPeg,toPeg);/把圆盘把圆盘n由由fromPeg直接移至直接移至toPegprintf(%s

11、%d%s%c%s%cn,movedisk,n,frompeg,fromPeg,topeg,toPeg);/把把n-1个圆盘从个圆盘从auxPeg借助借助fromPeg移至移至toPegtowers(n-1,auxPeg,toPeg,fromPeg);21测试主函数如下：测试主函数如下：#includevoidmain(void)Towers(4,A,C,B);程序运行的输出信息如下：程序运行的输出信息如下：22MoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk3fromPegAtoPegBM

12、oveDisk1fromPegCtoPegAMoveDisk2fromPegCtoPegBMoveDisk1fromPegAtoPegBMoveDisk4fromPegAtoPegCMoveDisk1fromPegBtoPegCMoveDisk2fromPegBtoPegAMoveDisk1fromPegCtoPegAMoveDisk3fromPegBtoPegCMoveDisk1fromPegAtoPegBMoveDisk2fromPegAtoPegCMoveDisk1fromPegBtoPegC23 总结如下：总结如下：递归算法的执行过程是递归算法的执行过程是不断地自调用不断地自调用，直，

13、直到到达递归出口才结束自调用过程；到达递归出口后，递到到达递归出口才结束自调用过程；到达递归出口后，递归算法开始按归算法开始按最后调用的过程最先返回最后调用的过程最先返回的次序返回；返回的次序返回；返回到最外层的调用语句时递归算法执行过程结束到最外层的调用语句时递归算法执行过程结束。246.46.4递归过程和运行时栈递归过程和运行时栈对于非递归函数，调用函数在调用被调用函数前，系对于非递归函数，调用函数在调用被调用函数前，系统要统要保存保存以下两类以下两类信息信息：（1 1）调用函数的返回地址；）调用函数的返回地址；（2 2）调用函数的局部变量值。）调用函数的局部变量值。当执行完被调用函数，返

14、回调用函数前，系统首先要当执行完被调用函数，返回调用函数前，系统首先要恢复恢复调用函数的调用函数的局部变量值局部变量值，然后，然后返回返回调用函数的调用函数的返回返回地址地址。25 递归函数被调用时，系统要作的工作和非递归函递归函数被调用时，系统要作的工作和非递归函数被调用时系统要作的工作在数被调用时系统要作的工作在形式上类同形式上类同，但，但保存信息保存信息的方法不同的方法不同。递归函数被调用时，系统需要一个运行时栈递归函数被调用时，系统需要一个运行时栈.系统的系统的运行时栈也要保存上述两类信息。每一层递归调用所需运行时栈也要保存上述两类信息。每一层递归调用所需保存的信息构成运行时栈的一个工

15、作记录，在每进入下保存的信息构成运行时栈的一个工作记录，在每进入下一层递归调用时，系统就建立一个新的一层递归调用时，系统就建立一个新的工作记录工作记录，并把，并把这个工作记录进栈成为运行时栈新的栈顶；每返回一层这个工作记录进栈成为运行时栈新的栈顶；每返回一层递归调用，就退栈一个工作记录。因为栈顶的工作记录递归调用，就退栈一个工作记录。因为栈顶的工作记录必定是当前正在运行的递归函数的工作记录，所以栈顶必定是当前正在运行的递归函数的工作记录，所以栈顶的工作记录也称为的工作记录也称为活动记录活动记录。266.56.5递归算法的效率分析递归算法的效率分析斐波那契数列斐波那契数列Fib(n)Fib(n)

16、的递推定义是：的递推定义是：求第求第n n项斐波那契数列的项斐波那契数列的递归函数递归函数如下：如下：longFib(intn)if(n=0|n=1)returnn;/递归出口递归出口elsereturnFib(n-1)+Fib(n-2);/递归调用递归调用27用归纳法可以证明求用归纳法可以证明求Fib(n)的递归的递归调用次数调用次数等于等于2n-1；计算斐波计算斐波那契数列的递归函数那契数列的递归函数Fib(n)的的时间复杂度为时间复杂度为O(2n)。计算斐波那契数计算斐波那契数列列Fib(n)问题，我们也可根据公式写出问题，我们也可根据公式写出循环方式求解的函数如下：循环方式求解的函数如

17、下：图图6-6 Fib(5)6-6 Fib(5)的递归调用树的递归调用树 28longFib2(intn)longintoneBack,twoBack,current;inti;if(n=0|n=1)returnn;elseoneBack=1;twoBack=0;for(i=2;i=n;i+)current=oneBack+twoBack;twoBack=oneBack;oneBack=current;returncurrent;29上述循环方式的计算斐波那契数列的函数上述循环方式的计算斐波那契数列的函数Fib2(n)的时的时间复杂度为间复杂度为O(n)。对比循环结构的对比循环结构的Fib2(

18、n)和递归结构的和递归结构的Fib(n)可发现，可发现，循环结构循环结构的的Fib2(n)算法在计算第算法在计算第n项的斐项的斐波那契数列时波那契数列时保存了保存了当前已经计算得到的当前已经计算得到的第第n-1项和第项和第n-2项的斐波那契数列项的斐波那契数列，因此其，因此其时间复杂度为时间复杂度为O(n)；而而递归递归结构结构的的Fib(n)算法在计算第算法在计算第n项的斐波那契数列时，项的斐波那契数列时，必须必须首先计算第首先计算第n-1项和第项和第n-2项的斐波那契数列项的斐波那契数列，而某次递归，而某次递归计算得出的斐波那契数列，如计算得出的斐波那契数列，如Fib(n-1)、Fib(n

19、-2)等等无法无法保存保存，下一次要用到时还需要重新递归计算，因此其，下一次要用到时还需要重新递归计算，因此其时时间复杂度为间复杂度为O(2n)。30*6.66.6递归算法到非递归算法的转换递归算法到非递归算法的转换 有些问题需要用低级程序设计语言来实现，而低级有些问题需要用低级程序设计语言来实现，而低级程序设计语言（如汇编语言）一般不支持递归，此时程序设计语言（如汇编语言）一般不支持递归，此时需要采用问题的非递归结构算法。一般来说，存在如需要采用问题的非递归结构算法。一般来说，存在如下下两种情况的递归算法两种情况的递归算法。（1 1）存在）存在不借助堆栈的循环结构的非递归算法不借助堆栈的循环

20、结构的非递归算法，如，如阶乘计算问题、斐波那契数列的计算问题、折半查找阶乘计算问题、斐波那契数列的计算问题、折半查找问题等。这种情况，问题等。这种情况，可以直接选用循环结构的算法可以直接选用循环结构的算法。31（2 2）存在）存在借助堆栈的循环结构的非递归算法借助堆栈的循环结构的非递归算法，所有递归算法都，所有递归算法都可以借助堆栈转换成循环结构的非递归算法，如下边例可以借助堆栈转换成循环结构的非递归算法，如下边例6-46-4设计设计的汉诺塔问题的借助堆栈的循环结构的非递归算法。此时的汉诺塔问题的借助堆栈的循环结构的非递归算法。此时可以可以把递归算法转换成相应的非递归算法把递归算法转换成相应的

21、非递归算法，有两种转换方法：有两种转换方法：一种一种方法是借助堆栈方法是借助堆栈，用非递归算法形式化模拟递归算法的执行过，用非递归算法形式化模拟递归算法的执行过程；程；另一种方法是另一种方法是根据要求解问题的特点，根据要求解问题的特点，设计借助堆栈的循设计借助堆栈的循环结构算法环结构算法。这两种方法都需要使用堆栈，这是因为堆栈的后这两种方法都需要使用堆栈，这是因为堆栈的后进先出特点正好和递归函数的运行特点相吻合。下面讨论的例进先出特点正好和递归函数的运行特点相吻合。下面讨论的例6-46-4是第二种情况下的第一种转换方法的例子是第二种情况下的第一种转换方法的例子 326.76.7设计举例设计举例

22、6.7.1 6.7.1 一般递归算法设计举例一般递归算法设计举例例例6-5 6-5 设设计计一一个个输输出出如如下下形形式式数数值值的的递递归归算法。算法。n n n .nn n n .n.3 3 3 3 3 3 2 22 21 133问问题题分分析析：该该问问题题可可以以看看成成由由两两部部分分组组成成：一一部部分分是是输输出出一一行行值值为为n的的数数值值；另另一一部部分分是是原原问问题题的的子子问问题题，其其参参数数为为n-1。当当参参数数减减到到0时时不不再再输输出出任任何何数数据据值值，因因此此递递归归的的出出口口是是当当参参数数n0时空语句返回。时空语句返回。算法设计：递归算法设计

23、如下：算法设计：递归算法设计如下：voidDisplay(intn)inti;for(i=1;i=n;i+)coutsetw(s)n;cout0)Display(n-1);/递归递归/n=0为递归出口，递归出口为空语句为递归出口，递归出口为空语句34例例6-6设计求解设计求解委员会问题委员会问题的算法。委员会问题是：的算法。委员会问题是：从一个有从一个有n个人的团体中抽出个人的团体中抽出k(kn)个人组成一个委个人组成一个委员会，计算共有多少种构成方法。员会，计算共有多少种构成方法。问题分析：问题分析：从从n个人中抽出个人中抽出k(kn)个人的问题是一个个人的问题是一个组合问题。把组合问题。把

24、n个人固定位置后，从个人固定位置后，从n个人中抽出个人中抽出k个个人的问题可分解为两部分之和：第一部分是第一个人人的问题可分解为两部分之和：第一部分是第一个人包括在包括在k个人中，第二部分是第一个人不包括在个人中，第二部分是第一个人不包括在k个人个人中。对于第一部分，则问题简化为从中。对于第一部分，则问题简化为从n-1个人中抽出个人中抽出k-1个人的问题；对于第二部分，则问题简化为从个人的问题；对于第二部分，则问题简化为从n-1个个人中抽出人中抽出k个人的问题。图个人的问题。图6-7给出了给出了n=5,k=2时问题时问题的分解示意图。的分解示意图。35图图6-7 6-7 委员会问题分解示意图委

25、员会问题分解示意图 36当当n=k或或k=0时，该问题可直接求解，数值均为时，该问题可直接求解，数值均为1，这是算法的递归出口。因此，委员会问题的这是算法的递归出口。因此，委员会问题的递推定递推定义式义式为：为：37intComm(intn,intk)if(n1|kn)return0;if(k=0)return1;if(n=k)return1;returnComm(n-1,k-1)+Comm(n-1,k);38例例6-7求两个正整数求两个正整数n和和m最大公约数的最大公约数的递推定义式递推定义式为：为：要求：要求：（1 1）编写求解该问题的递归算法；）编写求解该问题的递归算法；（2 2）分分析

26、析当当调调用用语语句句为为Gcd(30,Gcd(30,4)4)时时算算法法的的执执行行过过程程和和执执行行结果；结果；（3 3）分分析析当当调调用用语语句句为为Gcd(97,Gcd(97,5)5)时时算算法法的的执执行行过过程程和和执执行行结果；结果；（4 4）编写求解该问题的循环结构算法。）编写求解该问题的循环结构算法。39解：（解：（1）递归算法如下：）递归算法如下：intGcd(intn,intm)if(n0|mn)returnGcd(m,n);elsereturnGcd(m,n%m);40 （2 2）调用语句为）调用语句为Gcd(30,4)Gcd(30,4)时，因时，因mnmn，递归调

27、用，递归调用Gcd(4,2)Gcd(4,2)；因；因mnmnmn，递归调用，递归调用Gcd(97,5)Gcd(97,5)；因；因mnmn，递归调用，递归调用Gcd(5,2)Gcd(5,2)；因；因mnmn，递，递归调用归调用Gcd(2,1)Gcd(2,1)；因；因mnmn，递归调用，递归调用Gcd(1,0)Gcd(1,0)；因；因m=0m=0，到达递归出口，函数最终返回值为，到达递归出口，函数最终返回值为n=1n=1，即，即5 5和和9797的最大公约数为的最大公约数为1 1。416.7.2 6.7.2 回溯法及其回溯法及其设计举例设计举例 回溯法是递归算法的一种特殊形式，回溯法的回溯法是递归

28、算法的一种特殊形式，回溯法的基本思基本思想是：想是：对一个包括有很多结点，每个结点有若干个搜索分对一个包括有很多结点，每个结点有若干个搜索分支的问题，把原问题分解为对若干个子问题求解的算法。支的问题，把原问题分解为对若干个子问题求解的算法。当搜索到某个结点、发现无法再继续搜索下去时，就让搜当搜索到某个结点、发现无法再继续搜索下去时，就让搜索过程回溯退到该结点的前一结点，继续搜索这个结点的索过程回溯退到该结点的前一结点，继续搜索这个结点的其他尚未搜索过的分支；其他尚未搜索过的分支；如果发现这个结点也无法再继续如果发现这个结点也无法再继续搜索下去时，就让搜索过程回溯（即退回）到这个结点的搜索下去时，就让搜索过程回溯（即退回）到这个结点的前一结点继续这样的搜索过程；这样的搜索过程一直进行前一结点继续这样的搜索过程；这样的搜索过程一直进行到搜索到问题的解或搜索完了全部可搜索分支没有解存在到搜索到问题的解或搜索完了全部可搜索分支没有解存在为止。为止。42