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

每次比较后，较小的数据项被放入到C中试想如果数组A和B的规模较大，会发生什么？它需要在存储器中有另一个大小等于被排序的数据项数目的数组。如果初始数组几乎占满整个存储器，那么归并排序将不能工作；但如果有足够的空间，归并排序会是一个很好的选择。思考：归并排序的缺点？BookListing6.5Themerge.javaProgram数组大小是2的乘方归并排序的思想是把一个数组分成两半，排序每一半，然后用merge()方法把数组的两半归并成一个有序的数组。依次类推......通过归并进行排序SORTINGBYMERGING数组的大小不是2的乘方mergeSort.java程序BookAPPLET归并排序的效率MERGESORTmergesorttakeO(N*logN)time.NumberofCopies8*log2(8)*2=48√√√√××比较的次数比较的最大次数总是比正在被归并的数据项个数少一，并且比较的最少次数是正在被归并的数据项数目的一半。有一些算法趋向于用递归，另一些算法则不是。正如前面已经看到的那样，递归的triangle()和factorial()方法可以用一个简单的循环来实现，那样效率更高。但各种分治算法，比如归并排序的递归函数，能工作得非常好。一个算法利用递归，从概念上容易理解，但是，实际应用中，证明递归的效率往往不太高。需要将递归转化为非递归算法，这种转换用到了栈。12⑦消除递归递归和栈递归和栈之间有一种紧密的联系。事实上，大部分的编译器都是使用栈来实现递归的。正如前面我们提到的，编译器会把这个方法的所有参数及其返回地址都压入栈中，然后把控制转移给这个方法。这个方法返回时，这些值都退栈。参数消失了，并且控制权重新回到返回地址处。模拟递归方法过程，调用一个方法时发生的操作：当一个方法调用时，它的参数以及返回地址被压入一个栈中；这个方法可以通过获取栈顶元素的值来访问它的参数；当这个方法返回的时候，它查看栈以获得返回地址，然后这个地址以及方法的所有参数退栈，并销毁。见教材程序代码intpower(x,y)01{02if(y==1)03returnx;04else05returnx*power(x,y-1);06}07求一个数的乘方⑧一些递归的应用DataStructuresandAlgorithmswithJavaChapter6Recursion递归的概念递归的优缺点，递归的方法转换为基于栈的非递归方法递归的实例和应用：三角数字、阶乘、递归的二分查找、汉诺塔问题，归并排序等问题掌握内容本章掌握内容本章掌握重点三角数字阶乘变位数递归的二分查找汉诺塔归并排序消除递归一些有趣的递归应用递归是一种方法(函数)调用自己的编程技术。01Recursionisaprogrammingtechniqueinwhichamethod(function)callsitself02递归的概念①三角数字TriangularNumbers1,3,6,10,15,21,…Then-thtermintheseriesisobtainedbyaddingntothepreviousterm.通常想到的解决方案查找第n项，依次递减n，直至其减小到0，退出循环使用递归查找第n项1.Thefirst(tallest)column,whichhasthevaluen.2.Thesumofalltheremainingcolumns.Thevalueofthenthtermcanbethoughtofasthesumofonlytwothings,insteadofawholeseries.Ifweknewaboutamethodthatfoundthesumofalltheremainingcolumns,thenwecouldwriteourtriangle()methodsumAllColumns方法所做的事情与triangle方法一致Theconditionthatleadstoarecursivemethodreturningwithoutmakinganotherrecursivecallisreferredtoasthebasecase.基值情况每个递归过程都有一个