《数据结构与算法》PPT课堂课件-第5章-递归.pdf
2存存在在算算法法调调用用自自己己的的情情况况：若若一一个个算算法法直直接接的的或或间间接接的的调调用用自自己己本本身身，则则称称这这个个算算法法是是递递归归算算法法。（1 1）问问题题的的定定义义是是递递推推的的阶阶乘乘函函数数的的常常见见定定义义是是：5.1递归的概念3也也可可定定义义为为：写写成成函函数数形形式式，则则为为：这这种种函函数数定定义义的的方方法法是是用用阶阶乘乘函函数数自自己己本本身身定定义义了了阶阶乘乘函函数数，称称公公式式（63）是是阶阶乘乘函函数数的的递递推推定定义义式式。4（2）问问题题的的解解法法存存在在自自调调用用 一一个个典典型型的的例例子子是是在在有有序序数数组组中中查查找找一一个个数数据据元元素素是是否否存存在在的的折折半半查查找找算算法法。 55.2递归算法的执行过程 例例6-1 6-1 给给出出按按照照公公式式6-36-3计计算算阶阶乘乘函函数数的的递递归归算算法法，并并给给出出n = 3n = 3时时递递归归算算法法的的执执行行过过程程。 设设计计：按按照照公公式式6-36-3计计算算阶阶乘乘函函数数的的递递归归算算法法如如下下：long long intint Fact(intFact(int n) n) intint x; x;long long intint y; y;if(n 0) if(n 0) /*(n 0/*(n high) return -1;if(low high) return -1;/*/*查查找找不不成成功功* */ /mid = (low + high) / 2;mid = (low + high) / 2;if(x = amid)if(x = amid)return mid;return mid;/*/*查查找找成成功功* */ /else if(x amid)else if(x amid) return return BSearch(aBSearch(a, x, low, mid-1);, x, low, mid-1);/*/*在在下下半半区区查查找找* */ /elseelsereturn return BSearch(aBSearch(a, x, mid+1, high);, x, mid+1, high);/*/*在在上上半半区区查查找找* */ / 9测测试试主主函函数数设设计计如如下下：# include # include main(void)main(void) intint a = 1, 3, 4, 5, 17, 18, 31, 33; a = 1, 3, 4, 5, 17, 18, 31, 33;intint x = 17; x = 17;intint bnbn;bnbn = = BSearch(aBSearch(a, x, 0,7);, x, 0,7);if(bnif(bn = -1) = -1) printf(xprintf(x不不在在数数组组a a中中););else else printf(xprintf(x在在数数组组a a的的下下标标%d%d中中, , bnbn);); 10BSearch(aBSearch(a, x, 0,7), x, 0,7)的的递递归归调调用用过过程程如如图图6-36-3所所示示，其其中中，实实箭箭头头表表示示函函数数调调用用，虚虚箭箭头头表表示示函函数数的的返返回回值值。115.3递归算法的设计方法 递递归归算算法法既既是是一一种种有有效效的的算算法法设设计计方方法法，也也是是一一种种有有效效的的分分析析问问题题的的方方法法。递递归归算算法法求求解解问问题题的的基基本本思思想想是是：对对于于一一个个较较为为复复杂杂的的问问题题，把把原原问问题题分分解解成成若若干干个个相相对对简简单单且且类类同同的的子子问问题题，这这样样较较为为复复杂杂的的原原问问题题就就变变成成了了相相对对简简单单的的子子问问题题；而而简简单单到到一一定定程程度度的的子子问问题题可可以以直直接接求求解解；这这样样，原原问问题题就就可可递递推推得得到到解解。 并并不不是是每每个个问问题题都都适适宜宜于于用用递递归归算算法法求求解解。适适宜宜于于用用递递归归算算法法求求解解的的问问题题的的充充分分必必要要条条件件是是：（1 1）问问题题具具有有某某种种可可借借用用的的类类同同自自身身的的子子问问题题描描述述的的性性质质；（2 2）某某一一有有限限步步的的子子问问题题（也也称称作作本本原原问问题题）有有直直接接的的解解存存在在。当当一一个个问问题题存存在在上上述述两两个个基基本本要要素素时时，设设计计该该问问题题的的递递归归算算法法的的方方法法是是：（1 1）把把对对原原问问题题的的求求解解设设计计成成包包含含有有对对子子问问题题求求解解的的形形式式。（2 2）设设计计递递归归出出口口。12Hanoi塔问题问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则：每次只能移一个圆盘圆盘可在三个塔座上任意移动任何时刻，每个塔座上不能将大盘压到小盘上解决方法：n=1时，直接把圆盘从A移到Cn1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题。执行情况：递归工作栈保存内容：形参n,x,y,z和返回地址返回地址用行编号表示n x y z 返回地址 13 main() int m; printf(Input number of disks”); scanf(%d,&m); printf(”Steps : %3d disks”,m); hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n= =1)(3) move(x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 614 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 615 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 016 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0栈空3 A B C 02 B A C 8175.4递归过程和运行时栈对对于于非非递递归归函函数数，调调用用函函数数在在调调用用被被调调用用函函数数前前，系系统统要要保保存存以以下下两两类类信信息息：（1 1）调调用用函函数数的的返返回回地地址址；（2 2）调调用用函函数数的的局局部部变变量量值值。当当执执行行完完被被调调用用函函数数，返返回回调调用用函函数数前前，系系统统首首先先要要恢恢复复调调用用函函数数的的局局部部变变量量值值，然然后后返返回回调调用用函函数数的的返返回回地地址址。递递归归函函数数被被调调用用时时，系系统统要要作作的的工工作作和和非非递递归归函函数数被被调调用用时时系系统统要要作作的的工工作作在在形形式式上上类类同同，但但保保存存信信息息的的方方法法不不同同。递递归归函函数数被被调调用用时时，系系统统的的运运行行时时栈栈也也要要保保存存上上述述两两类类信信息息。每每一一层层递递归归调调用用所所需需保保存存的的信信息息构构成成运运行行时时栈栈的的一一个个工工作作记记录录，在在每每进进入入下下一一层层递递归归调调用用时时，系系统统就就建建立立一一个个新新的的工工作作记记录录，并并把把这这个个工工作作记记录录进进栈栈成成为为运运行行时时栈栈新新的的栈栈顶顶；每每返返回回一一层层递递归归调调用用，就就退退栈栈一一个个工工作作记记录录。因因为为栈栈顶顶的的工工作作记记录录必必定定是是当当前前正正在在运运行行的的递递归归函函数数的的工工作作记记录录，所所以以栈栈顶顶的的工工作作记记录录也也称称为为活活动动记记录录。 185.5递归算法的效率分析斐斐波波那那契契数数列列Fib(n)Fib(n)的的递递推推定定义义是是：求求第第n n项项斐斐波波那那契契数数列列的的递递归归函函数数如如下下：long long Fib(intFib(int n) n) if(n = 0 | n = 1) return n; if(n = 0 | n = 1) return n; /递递归归出出口口else return Fib(n-1) + Fib(n-2); else return Fib(n-1) + Fib(n-2); /递递归归调调用用 19 用用归归纳纳法法可可以以证证明明求求Fib(n)Fib(n)的的递递归归调调用用次次数数等等于于2 2n n-1-1；计计算算斐斐波波那那契契数数列列的的递递归归函函数数Fib(n)Fib(n)的的时时间间复复杂杂度度为为O(2O(2n n) )。计计算算斐斐波波那那契契数数列列Fib(n)Fib(n)问问题题，我我们们也也可可根根据据公公式式写写出出循循环环方方式式求求解解的的函函数数如如下下： 20long Fib2(int n)long Fib2(int n) long long intint oneBackoneBack, , twoBacktwoBack, current;, current;intint i; i;if(n = 0 | n = 1) return n;if(n = 0 | n = 1) return n;elseelse oneBackoneBack = 1; = 1;twoBacktwoBack = 0; = 0;for(i = 2; i = n; i+)for(i = 2; i = n; i+) current = current = oneBackoneBack + + twoBacktwoBack; ;twoBacktwoBack = = oneBackoneBack; ;oneBackoneBack = current; = current; return current;return current; 21 上上述述循循环环方方式式的的计计算算斐斐波波那那契契数数列列的的函函数数Fib2(n)Fib2(n)的的时时间间复复杂杂度度为为O(n)O(n)。对对比比循循环环结结构构的的Fib2(n)Fib2(n)和和递递归归结结构构的的Fib(n)Fib(n)可可发发现现，循循环环结结构构的的Fib2(n)Fib2(n)算算法法在在计计算算第第n n项项的的斐斐波波那那契契数数列列时时保保存存了了当当前前已已经经计计算算得得到到的的第第n-1n-1项项和和第第n-2n-2项项的的斐斐波波那那契契数数列列，因因此此其其时时间间复复杂杂度度为为O(n)O(n)；而而递递归归结结构构的的Fib(n)Fib(n)算算法法在在计计算算第第n n项项的的斐斐波波那那契契数数列列时时，必必须须首首先先计计算算第第n n-1-1项项和和第第n-2n-2项项的的斐斐波波那那契契数数列列，而而某某次次递递归归计计算算得得出出的的斐斐波波那那契契数数列列，如如Fib(n-1)Fib(n-1)、Fib(n-2)Fib(n-2)等等无无法法保保存存，下下一一次次要要用用到到时时还还需需要要重重新新递递归归计计算算，因因此此其其时时间间复复杂杂度度为为O(2O(2n n) ) 。 225.6递归算法到非递归算法的转换 有有些些问问题题需需要要用用低低级级程程序序设设计计语语言言来来实实现现，而而低低级级程程序序设设计计语语言言（如如汇汇编编语语言言）一一般般不不支支持持递递归归，此此时时需需要要采采用用问问题题的的非非递递归归结结构构算算法法。一一般般来来说说，存存在在如如下下两两种种情情况况的的递递归归算算法法。 （1 1）存存在在不不借借助助堆堆栈栈的的循循环环结结构构的的非非递递归归算算法法，如如阶阶乘乘计计算算问问题题、斐斐波波那那契契数数列列的的计计算算问问题题、折折半半查查找找问问题题等等。 （2 2）存存在在借借助助堆堆栈栈的的循循环环结结构构的的非非递递归归算算法法，所所有有递递归归算算法法都都可可以以借借助助堆堆栈栈转转换换成成循循环环结结构构的的非非递递归归算算法法，如如下下边边例例6-46-4设设计计的的汉汉诺诺塔塔问问题题的的借借助助堆堆栈栈的的循循环环结结构构的的非非递递归归算算法法。 对对于于第第一一种种情情况况，可可以以直直接接选选用用循循环环结结构构的的算算法法。 对对于于第第二二种种情情况况，可可以以把把递递归归算算法法转转换换成成相相应应的的非非递递归归算算法法，此此时时有有两两种种转转换换方方法法：一一种种方方法法是是借借助助堆堆栈栈，用用非非递递归归算算法法形形式式化化模模拟拟递递归归算算法法的的执执行行过过程程；另另一一种种方方法法是是根根据据要要求求解解问问题题的的特特点点，设设计计借借助助堆堆栈栈的的循循环环结结构构算算法法。这这两两种种方方法法都都需需要要使使用用堆堆栈栈，这这是是因因为为堆堆栈栈的的后后进进先先出出特特点点正正好好和和递递归归函函数数的的运运行行特特点点相相吻吻合合。235.7设计举例5.7.1 5.7.1 一一般般递递归归算算法法设设计计举举例例例例6-5 6-5 设设计计一一个个输输出出如如下下形形式式数数值值的的递递归归算算法法。n n n . nn n n . n. . 3 3 3 3 3 3 2 22 21 124问问题题分分析析：该该问问题题可可以以看看成成由由两两部部分分组组成成：一一部部分分是是输输出出一一行行值值为为n n的的数数值值；另另一一部部分分是是原原问问题题的的子子问问题题，其其参参数数为为n-1n-1。当当参参数数减减到到0 0时时不不再再输输出出任任何何数数据据值值，因因此此递递归归的的出出口口是是当当参参数数n0n0时时空空语语句句返返回回。voidDisplay(intn)inti;for(i=1;i0)Display(n-1);25例例6-6 6-6 设设计计求求解解委委员员会会问问题题的的算算法法。委委员员会会问问题题是是：从从一一个个有有n n个个人人的的团团体体中中抽抽出出k k (kn)(kn)个个人人组组成成一一个个委委员员会会，计计算算共共有有多多少少种种构构成成方方法法。问问题题分分析析：从从n n个个人人中中抽抽出出k(kn)k(kn)个个人人的的问问题题是是一一个个组组合合问问题题。把把n n个个人人固固定定位位置置后后，从从n n个个人人中中抽抽出出k k个个人人的的问问题题可可分分解解为为两两部部分分之之和和：第第一一部部分分是是第第一一个个人人包包括括在在k k个个人人中中，第第二二部部分分是是第第一一个个人人不不包包括括在在k k个个人人中中。对对于于第第一一部部分分，则则问问题题简简化化为为从从n-1n-1个个人人中中抽抽出出k-1k-1个个人人的的问问题题；对对于于第第二二部部分分，则则问问题题简简化化为为从从n-1n-1个个人人中中抽抽出出k k个个人人的的问问题题。图图6-76-7给给出出了了n=5, k=2n=5, k=2时时问问题题的的分分解解示示意意图图。 2627 当当n=kn=k或或k=0k=0时时，该该问问题题可可直直接接求求解解，数数值值均均为为1 1，这这是是算算法法的的递递归归出出口口。因因此此，委委员员会会问问题题的的递递推推定定义义式式为为：intComm(intn,intk)if(n1|kn)return0;if(k=0)return1;if(n=k)return1;returnComm(n-1,k-1)+Comm(n-1,k);28例例6-7 6-7 求求两两个个正正整整数数n n和和m m最最大大公公约约数数的的递递推推定定义义式式为为：要要求求： （1 1）编编写写求求解解该该问问题题的的递递归归算算法法； （2 2）分分析析当当调调用用语语句句为为Gcd(30, Gcd(30, 4)4)时时算算法法的的执执行行过过程程和和执执行行结结果果； （3 3）分分析析当当调调用用语语句句为为Gcd(97, Gcd(97, 5)5)时时算算法法的的执执行行过过程程和和执执行行结结果果； （4 4）编编写写求求解解该该问问题题的的循循环环结结构构算算法法。 29解解：递递归归算算法法如如下下：intGcd(intn,intm)if(n0|mn)returnGcd(m,n);elsereturnGcd(m,n%m);301.1.调调用用语语句句为为Gcd(30, Gcd(30, 4)4)时时，因因mnmn，递递归归调调用用Gcd(4, Gcd(4, 2)2)；因因mnmnmn，递递归归调调用用Gcd(97, Gcd(97, 5)5)；因因mnmn，递递归归调调用用Gcd(5, Gcd(5, 2)2)；因因mnmn，递递归归调调用用Gcd(2, Gcd(2, 1)1)；因因mnmn，递递归归调调用用Gcd(1, Gcd(1, 0)0)；因因m=0m=0，到到达达递递归归出出口口，函函数数最最终终返返回回值值为为n=1n=1，即即5 5和和9797的的最最大大公公约约数数为为1 1。 分分析析：
