第2章 递归与分治策略

第2章递归与分治策略Recursion,divideandconquermethod学习要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学习分治策略设计技巧。（1）二分搜索技术；（2）合并排序（3）快速排序；（4）最接近点对问题；递归(recursion)是数学与计算机科学中的基本概念。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。递归程序不能无限制地自我调用，否则就会永不终止，递归程序必须有终止条件。尽管递归程序在执行时间上往往比非递归程序要付出更多的代价，但有很多问题的数学模型或算法设计方法本来就是递归的，用递归过程来描述它们不仅非常自然，而且证明该算法的正确性要比相应的非递归形式容易得多，因此递归不失为一种强有力的程序设计方法。2.1递归构成递归需具备的条件:1.不能无限制地调用本身，须有个出口，化简为非递归状况处理(边界条件);2.子问题与原问题为同一类型,且更为简单(递归模式).递归程序的书写方式:Procedurename(parameterlist)ifinitialconditionreturn(initialvalue);elsereturn(name(parameterexchange));end例1阶乘函数阶乘函数可递归地定义为：00)!1(1!nnnnn边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。intfactorial(intn){if(n==0)return1;returnn*factorial(n-1);}例2Fibonacci(斐波那齐)数列无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为：边界条件递归方程110)2()1(11)(nnnnFnFnF第n个Fibonacci数可递归地计算如下：intfibonacci(intn){if(n=1)return1;returnfibonacci(n-1)+fibonacci(n-2);}斐波那齐数列算法的递归结构(n=5)F(6)F(5)F(4)F(3)F(2)F(1)F(0)F(1)F(1)F(0)F(2)F(3)F(2)F(1)F(0)F(1)F(2)F(1)F(0)F(3)F(1)F(4)F(2)F(1)F(0)递归程序结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。求斐波那齐数列的非递归程序：voidfibonacci(intn){intprev,now,next,j;if(n=1)return(1);else{prev=1;now=1;for(j=2;j=n;j++){next=prev+now;prev=now;now=next;}return(next);}}使用递归子程序时，最好以较难的问题为主，将处理栈的复杂问题全交给编译程序去处理。具有编译递归程序能力的程序设计语言有：C、Pascal、ALGOL、PL/A、ADA、QBASIC等，不具有编译递归程序能力的程序设计语言有：FORTRAN、COBOL、BASIC、低级语言。前2例中的函数都可以找到相应的非递归方式定义：nnnnF)1(321!)(1125125151)(nnnF例1阶乘函数例2Fibonacci(斐波那齐)数列例3Hanoi塔问题设x,y,z是3个塔座。开始时，在塔座x上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座x上的这一叠圆盘移到塔座z上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至x,y,z中任一塔座上。xyzHANOI(2,Z,X,Y)HANOI(4,X,Y,Z)HANOI(3,X,Z,Y)HANOI(2,X,Y,Z)HANOI(1,X,Z,Y)MOVE(X,1,Y)MOVE(X,2,Z)HANOI(1,Y,X,Z)MOVE(Y,1,Z)MOVE(X,3,Y)HANOI(1,Z,Y,X)MOVE(Z,1,X)MOVE(Z,2,Y)HANOI(1,X,Z,Y)MOVE(X,1,Y)MOVE(X,4,Z)HANOI(3,Y,X,Z)HANOI(2,Y,Z,X)HANOI(1,Y,X,Z)MOVE(Y,1,Z)MOVE(Y,2,X)HANOI(1,Z,Y,X)MOVE(Z,1,X)MOVE(Y,3,Z)HANOI(2,X,Y,Z)HANOI(1,X,Z,Y)MOVE(X,1,Y)MOVE(X,2,Z)HANOI(1,Y,X,Z)MOVE(Y,1,Z)XYZ汉诺塔的执行过程(n=4)HANOI(2,Z,X,Y)HANOI(4,X,Y,Z)HANOI(3,X,Z,Y)HANOI(2,X,Y,Z)HANOI(1,X,Z,Y)MOVE(X,1,Y)MOVE(X,2,Z)HANOI(1,Y,X,Z)MOVE(Y,1,Z)MOVE(X,3,Y)HANOI(1,Z,Y,X)MOVE(Z,1,X)MOVE(Z,2,Y)HANOI(1,X,Z,Y)MOVE(X,1,Y)MOVE(X,4,Z)HANOI(3,Y,X,Z)HANOI(2,Y,Z,X)HANOI(1,Y,X,Z)MOVE(Y,1,Z)MOVE(Y,2,X)HANOI(1,Z,Y,X)MOVE(Z,1,X)MOVE(Y,3,Z)HANOI(2,X,Y,Z)HANOI(1,X,Z,Y)MOVE(X,1,Y)MOVE(X,2,Z)HANOI(1,Y,X,Z)MOVE(Y,1,Z)XYZvoidhanoi(intn,intx,inty,intz)//将塔座x上按直径由小到大且至上而下编号为1至n//的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。{if(n==1){move(x,1,z);//将编号为1的圆盘从x移到z}else{hanoi(n-1,x,z,y);//将x上编号为1至n-1的圆盘移到y,z作辅助塔move(x,n,z);//将编号为n的圆盘从x移到zhanoi(n-1,y,x,z);//将y上编号为1至n-1的圆盘移到z,x作辅助塔}}Hanoi塔问题的递归程序递归函数的运行轨迹在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。采用图示方法描述递归函数的运行轨迹，从中可较直观地了解到各调用层次及其执行情况。汉诺塔的递归程序易于理解，也容易证明它的正确性，但很难用手工移动的方式来模拟这个算法，尤其是n较大的时候。Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束递归函数的内部执行过程一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下：（1）运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；（2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；（3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。递归小结优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。因此无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。解决方法：在递归算法中消除递归调用，使其转化为非递归算法。1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。2、用递推来实现递归函数。3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。后两种方法在时空复杂度上均有较大改善，但其适用范围有限。递归小结2.2分治法将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。分治法的基本思想:2.独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。1.平衡(balancing)子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。启发式规则：子问题1的规模是n/2子问题1的解子问题2的解子问题2的规模是n/2原问题的解原问题的规模是n分治法的典型情况分治法的求解过程一般来说，分治法的求解过程由以下三个阶段组成：（1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。（3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。例：计算an，应用分治技术得到如下计算方法：3432328131319313193333分解问题求解每个子问题合并子问题的解分析时间性能´1122naanaannn如果如果分治法的适用条件分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。divide-and-conquer(P){if(|P|=n0)adhoc(P);//解决小规模的问题dividePintosmallersubinstancesP1,P2,.