数据结构(严蔚敏)chapter6recu.ppt

Data Structures and Algorithms with Java,Chapter6 Recursion,本章掌握内容,掌握内容递归的概念递归的实例和应用：三角数字、阶乘、递归的二分查找、汉诺塔问题，归并排序等问题递归的优缺点，递归的方法转换为基于栈的非递归方法,本章掌握重点,三角数字阶乘变位数递归的二分查找,汉诺塔 归并排序 消除递归 一些有趣的递归应用,递归的概念递归是一种方法(函数)调用自己的编程技术。Recursion is a programming technique in which a method(function)calls itself,三角数字 Triangular Numbers,1,3,6,10,15,21,The n-th term in the series is obtained by adding n to the previous term.,通常想到的解决方案,查找第n项，依次递减n，直至其减小到0，退出循环,使用递归查找第n项,The value of the nth term can be thought of as the sum of only two things,instead of a whole series.,1.The first(tallest)column,which has the value n.2.The sum of all the remaining columns.,If we knew about a method that found the sum of all the remaining columns,then we could write our triangle()method,sumAllColumns方法所做的事情与triangle方法一致,The condition that leads to a recursive method returning without making another recursive call is referred to as the base case.基值情况每个递归过程都有一个基值(终止)条件，以防止无限地递归下去，以及由此引发的程序崩溃,THE triangle.java PROGRAM,main()方法提示用户输入一个n值，调用triangle()方法，并且显示返回的结果。Triangle()方法反复地调用自身来做所有的工作。某个例子的输出结果：Enter a number:1000 Triangle=500500,递归方法的特征,尽管triangle()方法很短，但它拥有所有递归算法都具备的关键特性：调用自己.当调用自身的时候,目的是为了解决更小的问题.存在某个足够简单的问题层次，在这一层算法不需要调用自己就可以直接解答，且返回结果.在递归算法每次调用自身的过程中，参数变小，这反映了问题变小或变简单。当参数达到一定的最小值时，将会触发一个条件，此时方法不需要调用自身而可以返回,采用递归方法，只是从概念上简化了问题，而不是因为本质上它更有效率：与一般处理(while循环)相比，递归需要调用方法，会有一些额外的开销。控制必须从这个调用的位置转移到这个方法的开始处。除此之外，传给这个方法的参数以及这个方法返回的地址都要被压入到一个内部的栈里，为的是这个方法可以访问参数值和知道返回到哪里。递归需要存储中间参数以及返回值。如果中间变量过多，将影响效率。,递归方法的效率,递归就是程序设计中的数学归纳法。数学归纳法是一种通过自身的语汇定义某事物自己的方法。（语汇也被用于描述证明原理的相关方法）。使用数学归纳法，可以用数学的方法定义三角数字：,数学归纳法,阶乘 Factorials,阶乘在概念上和三角数字是类似的，只是用乘法取代了加法。5！=5*4*3*2*1=120,变位字 Anagrams,排列是指按照一定的顺序安排事物。假设想要列出一个指定单词的所有变位字，也就是列出该词的全排列。这个操作是变位一个单词或全排列一个单词。比如全排列cat，会产生：,试着自己手动全排列一个单词。所有字母都不同,全排列单词的数量？若同一字母出现多次，单词数就会少一些,你会怎样写一个程序来全排列单词呢？假定这个词有n个字母，全排列最右边的n-1个字母；轮换所有的n个字母；重复以上步骤n次。,轮换单词意味着所有的字母向左移一位，但最左边的字母例外，它“转换”至最右边字母的右边。,全排列单词 cat,如何全排列最右边的n-1个字母？通过调用自己,void doAnagram(int nCount,int n,int*val)if(1=n)/输出 else/分配一个临时数组temp和val保存数据一致/依次取出temp的一个数据,/进入递归 doAnagram(nCount,n-1,temp);,The anagram.java Program,递归的二分查找 A Recursive Binary Search,用最短的时间在有序数组中找到给定的数据项。方法是把数组从中间分成两半，然后看要查找的数据项在数组的哪一半，再次地折半，如此这样下去，find()方法如下：,RECURSION REPLACES THE LOOP,汉诺塔 The Towers of Hanoi,汉诺塔问题是由很多放置在三个塔座上的盘子组成的一个古老的难题。,问题定义：所有盘子的直径是不同的，并且盘子中央都有一个洞以使他们刚好放在塔座上。所有的盘子刚开始都放在塔座A上。这个难题的目标是将所有的盘子都从塔座A移动到塔座C上。每一次只可以移动一个盘子，并且任何一个盘子都不可以放在比自己小的盘子之上。,在印度的某地流传着一个古老的神话，在一个偏僻的庙宇，僧侣们日夜不停的劳动，要把64个金制的盘子从三个镶嵌着钻石的塔中的一个搬到另外一个里。当他们完成这个任务的时候，世界就将灭亡了。这可能会使人感到某种恐慌，但是，如果知道这个难题中即使只是搬比64少得多的盘子也要花多么长的时间的话，这种恐慌就会消失了。,以少量的盘子为例，手动解决这个难题，看看有什么规律：在塔座A上盘子初始的树形排列成为一棵树。Applet演示过程中，会发现，出现这样的较小的树形堆是问题解决的关键。这些所含盘子数小于盘子总数的较小的树称为子树。举例来说，如果要移动四个盘子，会发现中间的一个状态是有3个盘子的子树在塔座B上，如下图。,需要补充的是，当手动解决这个难题的时候，有一个经验法则，可以提供帮助。如果试图移动的子树包含有奇数个盘子，开始时直接把最顶端的盘子移动到想要的把这颗子树移动到的那个塔座上。如果试图要移动一颗含有偶数个盘子的子树，那么开始时要把最顶端的盘子移动到中介塔座上。如盘子总数为1，2或3,递归的算法,假定源塔为S，目标塔为D，中介塔为I，S上有n个盘子，算法如下：从S上移动n-1个盘子的子树到塔座I上；从塔S移动剩余的盘子(最大的盘子)到D上；从塔座I移动子树到塔座D上,当然，这个方法没有解决如何把包括盘子1，2和3的子树移动到塔座B上的问题，因为不能一次性的移动一棵子树；每次只能移动一个盘子。移动3个盘子的子树不是那么容易的，但这比移动4个盘子更容易。问题化小 基值条件：当移动一个盘子时，只要移动它就可以了,THE towers.java PROGRAM,归并排序 Mergesort,冒泡、插入和选择排序需要O(N2)的时间,而归并排序需要O(N*logN)的时间。,归并排序的中心是归并两个已经有序的数组。归并两个有序的数组A和B，就生成了第三个数组C，数组C包括数组A和B的所有数据项，并有序地出现在C中。,每次比较后，较小的数据项被放入到C中,思考：归并排序的缺点？,试想如果数组A和B的规模较大，会发生什么？,它需要在存储器中有另一个大小等于被排序的数据项数目的数组。如果初始数组几乎占满整个存储器，那么归并排序将不能工作；但如果有足够的空间，归并排序会是一个很好的选择。,Listing 6.5 The merge.java Program,通过归并进行排序 SORTING BY MERGING,归并排序的思想是把一个数组分成两半，排序每一半，然后用merge()方法把数组的两半归并成一个有序的数组。依次类推.,数组大小是2的乘方,数组的大小不是2的乘方,mergeSort.java程序,归并排序的效率 MERGESORT,mergesort take O(N*logN)time.Number of Copies,8*log2(8)*2=48,比较的次数比较的最大次数总是比正在被归并的数据项个数少一，并且比较的最少次数是正在被归并的数据项数目的一半。,消除递归,有一些算法趋向于用递归，另一些算法则不是。正如前面已经看到的那样，递归的triangle()和factorial()方法可以用一个简单的循环来实现，那样效率更高。但各种分治算法，比如归并排序的递归函数，能工作得非常好。一个算法利用递归，从概念上容易理解，但是，实际应用中，证明递归的效率往往不太高。需要将递归转化为非递归算法，这种转换用到了栈。,递归和栈 递归和栈之间有一种紧密的联系。事实上，大部分的编译器都是使用栈来实现递归的。正如前面我们提到的，编译器会把这个方法的所有参数及其返回地址都压入栈中，然后把控制转移给这个方法。这个方法返回时，这些值都退栈。参数消失了，并且控制权重新回到返回地址处。,模拟递归方法过程，调用一个方法时发生的操作：当一个方法调用时，它的参数以及返回地址被压入一个栈中；这个方法可以通过获取栈顶元素的值来访问它的参数；当这个方法返回的时候，它查看栈以获得返回地址，然后这个地址以及方法的所有参数退栈，并销毁。,见教材程序代码,一些递归的应用,求一个数的乘方 int power(x,y)if(y=1)return x;else return x*power(x,y-1);,基于x的y次方:等于x*x的y/2次方这个原理 long power(x,y)/y是偶数 if(y=1)return x;else return power(x*x,y/2);如果y是奇数，额外地乘以x，就可以了。,背包问题背包问题是计算机科学里的经典问题。在最简单的形式中，包括试图将不同重量的数据项放到背包中，以使背包最后达到指定的总重量。不需要把所有的选项都放入背包中。例如：假设想要背包精确地承重20磅，并且有5个可以选择放入的数据项，它们的重量依次为11，8，7，6和5磅。对于选择放入的数据项数量不大时，人类用观察法就可以解决这个问题，8+7+5=20.计算机解决这个问题，需要详细的指令，算法如下：,1、如果在这个过程中任意时刻，选择的数据项的总和符合目标重量，工作就完成了。2、从选择第一个数据项开始。剩余的数据项的加和必须符合背包的目标重量减去第一个数据项的重量：这是一个新的目标重量。3、逐个地试每种剩余数据项组合的可能性。但是，注意并不需要去试所有的组合，因为只要数据项的和大于目标重量的时候，就停止添加数据项。4、如果没有组合合适的话，放弃第一个数据项，并且从第二个数据项开始再重复一遍整个过程。5、继续从第三个数据项开始，如此下去知道你已经尝试了所有的数据组合，这时知道没有解决答案。,组合：选择一支队在数学中，组合是对事物的一种选择，而不考虑它们的顺序。例如：有5个登山队员，名字为A、B、C、D和E。想要从这群登山队员中选择三个队员，组成一支登山队去攀登陡峭的冰雪覆盖的Anaconda峰。但是，由于担心登山队的成员如何相处，所以决定列出所有组队的可能性：即挑出三个队员的所有可能组合。ABC，ABD，ABE，ACD，ACE，ADE，BCD，BCE，BDE，CDE,如何来写一个组队的递归程序？解决方法是将组合分成两部分：由A开始的组合和不是由A开始的组合，假设把从5个人中选出3个人的组合简写为(5，3)。规定n是这群人的大小，并且k是组队的大小。根据法则有：(n,k)=(n-1,k-1)+(n-1,k)对于5个人中选出3个组队的例子，有(5,3)=(4,2)+(4,3),基值条件是指没有意义的组合：某个数字是0以及队员数大于人群数的情况。组合(1,1)是合法的，但继续分解它就没有必要了。在图中虚线表示了基值条件；只是需要返回而不是继续分解。,int comb(int n,int r)if(rn)return 0;if(r=0|n=0|n=1)return 1;return comb(n-1,r)+comb(n-1,r-1);,Summary,一个递归方法每次用不同的参数值反复调用自身。某种参数值使递归的方法返回，而不再调用自身。这称为基值情况。当递归方法返回时，递归过程通过逐渐完成各层方法实例的未执行部分，而从最内层返回到最外层的原始调用处。三角数字是它本身以及所有比它小的数字(整数)的和。例如，4的三角数字是10，因为4+3+2+1=10.一个数的阶乘是它自身和所有比它小的数的成绩。例如，4的阶乘是4*3*2*1=24.,Summary,三角数字和阶乘都可以通过递归的方法或简单的循环方法来实现。一个单词的全排列，可以通过反复地轮换它的字母以及全排列它最右边的n-1个字母来递归得到。二分查找可以通过检查查找关键字在有序序列的哪一半，然后在这一半做相同的事情，这些都可以用递归来实现。汉诺塔的问题包含三个塔座和任意数量的盘子。,Summary,汉诺塔难题可以递归来解决：把除了最低端盘子外的所有盘子形成的子树移动到一个中介塔座上，然后把最低端的盘子移动到目标塔座上，最终把那个子树移动到目标塔座上。归并两个有序数组意思是创建第三个数组，这个数组按顺序存储从这两个有序数组中取到的所有数据项。在归并排序中，一个大数组的单个数据项的子数组归并为两个数据项的子数组，然后两个数据项的子数组归并为4个数据项的子数组，如此下去直到所有的数组数据项有序。,Summary,归并排序需要O(N*logN)的时间。归并排序需要一个大小等于原来数组的工作空间。对于三角数字、阶乘、单词字母全排列以及二分查找，它们的递归方法只包含一次对自身的调用。（二分查找的代码中显示两次，但任何给定的代码的运行中只有一次自身调用）对于汉诺塔和归并排序问题，它们的递归的方法包括两次递归调用。任何可以用递归完成的操作都可以用一个栈来实现。,递归的方法可能效率低。如果是这样的话，有时可以用一个简单的循环或是一个基于栈的方法来替代它。,补充，递归实现逆序操作,以下递归函数实现的功能 int invert(long m)printf(%ld,m%10);m=m/10;if(m0)invert(m);,public class RTest public static void main(String args)String str=“中华人民共和国”;out(str);public static void out(String str)int count=str.length();System.out.println(str.charAt(-count);if(count0)String s=str.substring(0,count);str=s;out(str);/实现将字符串逆序操作,认真做课后习题，自己总结和梳理下本章内容。,