《递归与分治策略讲义课件》由会员分享，可在线阅读，更多相关《递归与分治策略讲义课件（64页珍藏版）》请在金锄头文库上搜索。
1、第2章 递归与分治策略,Recursion ,divide and conquer method,学习要点: 理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。 （1）二分搜索技术； （2）合并排序 （3）快速排序； （4）最接近点对问题；,递归(recursion)是数学与计算机科学中的基本概念。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 递归程序不能无限制地自我调用，否则就会永不终止，递归程序必须有终止条件。 尽管递归程序在执行时间上往往比非递归程序要付出更多的代价，但有很多问题的数学模型或算法设计方法本来就是递归的，用
2、递归过程来描述它们不仅非常自然， 而且证明该算法的正确性要比相应的非递归形式容易得多，因此递归不失为一种强有力的程序设计方法。,2.1 递归,构成递归需具备的条件:,1.不能无限制地调用本身，须有个出口，化简为非递归状况处理(边界条件); 2.子问题与原问题为同一类型,且更为简单(递归模式).,递归程序的书写方式:,Procedure(parameter list) if return(initial value); else return(parameter exchange); end,例1 阶乘函数 阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递
3、归函数只有具备了这两个要素，才能在有限次计算后得出结果。,int factorial(int n) if (n= 0) return 1; return n*factorial( n-1); ,例2 Fibonacci(斐波那齐)数列 无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：,边界条件,递归方程,第n个Fibonacci数可递归地计算如下： int fibonacci(int n) if (n = 1) return 1; return fibonacci(n-1)+fibonacci(n-2); ,斐波那齐数列算法的递归结构(n
4、=5),递归程序结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。,递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,求斐波那齐数列的非递归程序：,void fibonacci (int n) int prev,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); ,使用递归子程序时，最好以较难的问题为主，将处理栈的复杂问题全交给编译
5、程序去处理。,具有编译递归程序能力的程序设计语言有：C、Pascal 、 ALGOL、 PL/A 、 ADA、 QBASIC等，不具有编译递归程序能力的程序设计语言有：FORTRAN、 COBOL、BASIC、 低级语言。,前2例中的函数都可以找到相应的非递归方式定义：,例1 阶乘函数,例2 Fibonacci(斐波那齐)数列,例3 Hanoi塔问题 设x,y,z是3个塔座。开始时，在塔座x上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座x上的这一叠圆盘移到塔座z上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动
6、1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至x,y,z中任一塔座上。,x,y,z,汉诺塔的执行过程,(n=4),void hanoi (int n, int x, int y, int z) / 将塔座 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,
7、z); / 将编号为 n 的圆盘从 x 移到 z hanoi(n-1, y, x, z); /将y上编号为1至n-1的圆盘移到z,x作辅助塔 ,Hanoi塔问题的递归程序,递归函数的运行轨迹,在递归函数中，调用函数和被调用函数是同一个函数，需要注意的是递归函数的调用层次，如果把调用递归函数的主函数称为第0层，进入函数后，首次递归调用自身称为第1层调用；从第i层递归调用自身称为第i+1层。反之，退出第i+1层调用应该返回第i层。采用图示方法描述递归函数的运行轨迹，从中可较直观地了解到各调用层次及其执行情况。,汉诺塔的递归程序易于理解，也容易证明它的正确性，但很难用手工移动的方式来模拟这个算法，尤
8、其是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),Move (C,B),Move (A,C),Hanio(2,B,A,C),Hanio(1,B,C,A),Move (B,C),Hanio(1,A,B,C),Move (A,C),Move (B,A),递归函数的内部执行过程,一个递归函数的调用过程类似于多个函数的嵌套调用，只不过调用函数和被调用函数是同一个函数。为了保证递归函数的正确执行，系统需设立一个工作栈。具体地说，递归调用的内部执行过程如下： （1）运行开始
9、时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址； （2）每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈； （3）每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。,缺点：递归算法是一种自身调用自身的算法，随着递归深度的增加，工作栈所需要的空间增大，递归调用时的辅助操作增多，因此，递归算法的运行效率较低。因此无论是耗费的计算时间还是占用的存储空间都比非递归算法要多
10、。,解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。,递归小结,2.2分治法,将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问
11、题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。,分治法的基本思想:,2. 独立子问题：各子问题之间相互独立，这涉及到分治法的效率，如果各子问题不是独立的，则分治法需要重复地解公共的子问题。,1. 平衡(balancing)子问题：最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题（通常k2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。,启发式规则：,分治法的典型情况,分治法的求解过程,一般来说，分治法的求解过程由以下
12、三个阶段组成： （1）划分：既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。 （2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现。 （3）合并：把各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现。,例：计算an，应用分治技术得到如下计算方法：,分析时 间性能,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有
13、最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,divide-and-
14、conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 ,分治法的算法设计模式,问 题 的 规 模,阀值,设问题P(n)分解成k个规模为n/m的子问题,阀值n0=1,求解P(1)的 时间耗费为O(1).将P(n)分解及合并成P(n)的解的时间为f(n),则 分治法解规
15、模为n的问题的最坏时间复杂性函数T(n)满足:,Divide-and-Conquer(P) if ( |P|=n0) Adhoc(P); divide P into smaller subinstances P1 ,P2,. ,Pk; for (i = 1;i = k; i+) yi=Divide-and-Conquer(Pi); return Merge( yl ,., yk);,f(n),kT(n/m),O(1),分治法的复杂性分析,T(n) = kT(n / m) + f(n) = k(kT(n / m2) + f(n / m) + f(n) = k2T(n / m2) + kf(n /
16、 m) + f(n) = k3T(n / m3) + k2f(n / m2) +kf(n / m) + f(n) = ,这里ma = n，所以a = log m n。于是：,由此可知，T(n)的首项是n的常数幂。,解得:,二分搜索技术,问题描述 已知一个排好次序的元素表a1,a2,an，判定某个给定元素x是否在该表中出现，若是，则返回该元素在表中的位置，否则，返回-1。 一般解决方法（从头到尾查找一遍）,x,最坏情况下，顺序搜索算法需要O(n)次比较。,分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件,分析：比较x和a的中间元素amid，若x=amid
