《函数的递归调用与分治策略》由会员分享，可在线阅读，更多相关《函数的递归调用与分治策略（16页珍藏版）》请在金锄头文库上搜索。
1、编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页 共1页函数的递归调用与分治策略递归方法是算法和程序设计中的一种重要技术。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题。递归方法具有易于描述和理解、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。递归方法中所使用的“分而治之”的策略也称分治策略。递归方法的构造构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。下面由一个求n的阶乘的程序为例，总结出构造递归方法的一般步骤。例1从键盘输入正整数N（0=N=1时，N
2、!=N*(N-1)!（N=1时，0!=1），这就是一种递归关系。对于特定的K!，它只与K与(K-1)!有关。步骤2确定递归边界 在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：#include int f(int x) return(f(x-1);main() cout=1时n!= 1 当N=0时再将这种关系翻译为代码，即一个函数：long f(int n) if (
3、n=0) return(1); else return(n*f(n-1);步骤4完善程序 主要的递归函数已经完成，将程序依题意补充完整即可。/ex1.cpp#include long f(int n) if (n=0) return(1); else return(n*f(n-1);main() int n; cinn; coutendl=3）。从键盘输入N，输出A(N)。分析递归关系十分明显，由A(N)的表达式给出。需要注意的是本例中对于N=3，A(N)的值与A(N-1)和A(N-2)都有关。代码/ex2.cpp#include long fibonacci(int x) if ( (x=1
4、) | (x=2) ) return(1); else return(fibonacci(x-1)+fibonacci(x-2);main() int n; cinn; coutendlfibonacci(n); 例3Hanoi塔问题。 问题描述在霍比特人的圣庙里，有一块黄铜板，上面插着3根宝石针（分别为A号，B号和C号）。在A号针上从下到上套着从大到小的n个圆形金片。现要将A针上的金片全部移到C针上，且仍按照原来的顺序叠置。移动的规则如下：这些金片只能在3根针间移动，一次只能一片，且任何时候都不允许将较大的金片压在较小的上面。从键盘输入n，要求给出移动的次数和方案。分析由金片的个数建立递归关
5、系。当n=1时，只要将唯一的金片从A移到C即可。当n1时，只要把较小的(n-1)片按移动规则从A移到B，再将剩下的最大的从A移到C（即中间“借助”B把金片从A移到C），再将B上的(n-1)个金片按照规则从B移到C（中间“借助”A）。本题的特点在于不容易用数学语言写出具体的递归函数，但递归关系明显，仍可用递归方法求解。代码/ex3.cpp#include hanoi(int n,char t1,char t2,char t3) if (n=1) cout1 t1 t3endl; else hanoi(n-1,t1,t3,t2); coutn t1 t3endl; hanoi(n-1,t2,t1,
6、t3); main() int n; coutn; coutAnswer:endl; hanoi(n,A,B,C);函数递归调用的应用与分治策略许多算法都采用了分治策略求解，而可以说分治与递归是一对孪生兄弟，它们经常同时被应用于算法的设计中。下面讨论著名的Catalan数问题，人们在对它的研究中充分应用了分治策略。例4Catalan数问题。问题描述一个凸多边形，通过不相交于n边形内部的对角线，剖分为若干个三角形。求不同的剖分方案总数H(n)。H(n)即为Catalan数。例如，n=5时H(5)=5。分析Catalan数问题有着明显的递归子问题特征。在计算Catalan数时虽然可以推导出只关于n
7、的一般公式，但在推导过程中却要用到递归公式。下面讨论三种不同的解法，其中第三种解法没有使用递归，它是由前两种解法推导而出的。解法1对于多边形V1V2Vn，对角线V1Vi（i=3,4,n-1）将其分为两部分，一部分是i边形，另一部分是n-i+1边形。因此，以对角线V1Vi为一个剖分方案的剖分方案数为H(i)*H(n-i+1)。还有一种的特殊情形，是对角线V2Vn将其分为一个三角形V1V2Vn和一个n-2+1边形。为了让它同样符合粗体字给出的公式，规定H(2)=1。于是得到公式：H(n)=H(i)*H(n-i+1) （i=2,3,n-1） -公式(1)H(2)=1有了这个递归关系式，就可以用递推法
8、或递归法解出H(n)。解法2从V1向除了V2和Vn外的n-3个顶点可作n-3条对角线。每一条对角线V1Vi把多边形剖分成两部分，剖分方案数为H(i)*H(n-i+2)，由于Vi可以是V3V4Vn-1中的任一点，且V1可换成V2，V3，Vn中任一点也有同样的结果。考虑到同一条对角线在2个顶点被重复计算了一次，于是对每个由顶点和对角线确定的剖分方案都乘以1/2，故有H(n)=n(1/2)H(i)*H(n-i+2) （i=3,4,n-1）把(1/2)提到外面，H(n)=n/(2*(n-3)H(i)*H(n-i+2) （i=3,4,n-1） -公式(2)规定H(2)=H(3)=1，这是合理的。由公式(
9、2)和H(2)=1，同样可以用递推法或递归法解出H(n)。解法3 把公式(1)中的自变量改为n+1，再将刚刚得出的公式(2)代入公式(1)，得到H(n+1)=H(i)*H(n-i+2) （i=2,3,n） 由公式(1)H(n+1)=2*H(n)+H(i)*H(n-i+2) （i=3,4,n-1） 由H(2)=1H(n+1)=(4n-6)/n*H(n) 由公式(2)H(n)=(4n-10)/(n-1)*H(n-1) -公式(3)这是一个较之前两种解法更为简单的递归公式，还可以继续简化为H(n)=1/(n-1)*C(n-2,2n-4) -公式(4)这就不需要再使用递归算法了。然而在程序设计上，公式
10、(4)反而显得更加复杂，因为要计算阶乘。因此最后给出由公式(3)作为理论依据范例程序代码。代码相当简单，这都归功于刚才的推导。如果用前两种解法中的递归关系，程序会变得复杂且容易写错。因此，有时对具体问题将递归关系公式进行必要的化简也是至关重要的。代码/ex4.cpp#include #define MAXN 100long f(int x) if (x=3) return(1); else return(4*x-10)*f(x-1)/(x-1);main() int n; coutn; if ( (n=3) ) coutThe answer is:f(n);本例编程时还有一个细节问题需要注意。
11、注意函数f中的斜体部分，按照公式(4)计算时一定要先进行乘法再进行除法运算，因为(4*x-10)并不总能整除(x-1)，如果先进行除法则除出的小数部分将自动被舍去，从而导致得到不正确的解。数学上许多有重要意义的计数问题都可以归结为对Catalan数的研究。可以看到，本例中的递归关系经简化还是相当简单的。下面讨论一个递归关系略为复杂的例子。例5快速排序问题。快速排序是程序设计中经常涉及的一种排序算法。它的最好时间复杂度为O(nlog2n)，最差为O(n2)，是一种不稳定的排序方法（大小相同的数在排序后可能交换位置）。算法描述快速排序的一种基本思想是：要将n个数按由小到大排列，在待排序的n个数中选
12、取任一个数（在本例中取第一个），称为基准数，在每一次快速排序过程中设置两个指示器i和j，对基准数左边和右边的数同时从最左（i）和最右（j）开始进行扫描（i逐1递增，j逐1递减），直到找到从左边开始的某个i大于或等于基准数，从右边开始的某个j小于或等于基准数。一旦发现这样的i和j（暂且称之为一个“逆序对”），则把第i个数和第j个数交换位置，这样它们就不再是逆序对了，紧接着再将i递增1，j递减1。如此反复，在交换过有限个逆序对后，i和j将越来越靠近，最后“相遇”，即i和j指向同一个数，暂且称之为相遇数（极端情况下，如果一开始就不存在逆序对，i和j将直接“相遇”）。相遇后就保证数列中没有逆序对了（除了在上述的极端情
