《数据结构与算法》PPT课堂课件-第5章-递归.ppt

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-1n-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。分析：分析：