第四章 递归算法,前面已经介绍了关于递归调用这样一种操作，而递归程序设计是C+语言程序设计中的一种重要的方法，它使许多复杂的问题变得简单，容易解决了。递归特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。,【例1】 给定n（n=1）,用递归的方法计算1+2+3+4+.+(n-1)+n。 【算法分析】 本题可以用递归方法求解，其原因在于它符合递归的三个条件： (1)本题是累加问题：当前和=前一次和+当前项，而前一次和的计算方法与其相同，只是数据不同s(n)=s(n-1)+n; (2)给定n,所以是有限次的递归调用； (3)结束条件是当n=1，则s=1。 【参考程序】 #include using namespace std; int fac(int); /递归函数 int main() int t; cint; /输入t的值 couts=fac(t)endl; /计算1到t的累加和，输出结果 int fac(int n) if (n=1) return 1; return(fac(n-1)+n); /调用下一层递归 ,运行程序，当T=5时，输出结果：S=15，其递归调用执行过程是：（设T=3）,递归调用过程，实质上是不断调用过程或函数的过程，由于递归调用一次，所有子程序的变量（局部变量、变参等）、地址在计算机内部都有用特殊的管理方法栈（先进后出）来管理，一旦递归调用结束，计算机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。,【例2】 设有N个数已经按从大到小的顺序排列，现在输入X，判断它是否在这N个数中，如果存在则输出：“YES” 否则输出“NO”。 【算法分析】 该问题属于数据的查找问题，数据查找有多种方法，通常方法是：顺序查找和二分查找，当N个数排好序时，用二分查找方法速度大大加快。二分查找算法： （1） 设有N个数，存放在A数组中，待查找数为X，用L指向数据的高端，用R指向数据的低端，MID指向中间： （2） 若X=AMID 输出 “YES”； （3）若XAMID则到数据前半段查找：L不变，R=MID-1，计算新的MID值，并进行新的一段查找； （5）若LR都没有查找到，则输出“NO”。 该算法符合递归程序设计的基本规律，可以用递归方法设计。,【参考程序】 #include #include using namespace std; int a11; void search(int,int,int); int main() /主程序 int k,x,L=1,R=10; coutak; cinx; search(x,L,R); system(pause); void search(int x,int top,int bot) /二分查找递归过程 int mid; if (top=bot) mid=(top+bot)/2; /求中间数的位置,if (x=amid) coutYESendl; /找到就输出 else if (xamid) search(x,mid+1,bot); /判断在前半段还是后半段查找 else search(x,top,mid-1); else coutNOendl; ,【例3】Hanoi汉诺塔问题 有N个圆盘，依半径大小（半径都不同），自下而上套在A柱上，每次只允许移动最上面一个盘子到另外的柱子上去（除A柱外，还有B柱和C柱，开始时这两个柱子上无盘子），但绝不允许发生柱子上出现大盘子在上，小盘子在下的情况，现要求设计将A柱子上N个盘子搬移到C柱去的方法。 【算法分析】 本题是典型的递归程序设计题。 (1)当N=1 时，只有一个盘子，只需要移动一次:AC; (2)当N=2时，则需要移动三次： A-1 - B, A -2 - C, B -1- C. (3)如果N=3，则具体移动步骤为：,假设把第3步，第4步，第7步抽出来就相当于N=2的情况（把上面2片捆在一起，视为一片）：,所以可按“N=2”的移动步骤设计： 如果N=0，则退出，即结束程序;否则继续往下执行; 用C柱作为协助过渡，将A柱上的（N-1）片移到B柱上，调用过程mov(n-1, a,b,c); 将A柱上剩下的一片直接移到C柱上; 用A柱作为协助过渡，将B柱上的（N-1）移到C柱上，调用过程mov (n-1,b,c,a)。 【参考程序】 #include using namespace std; int k=0,n; void mov(int n,char a,char c,char b) /用b柱作为协助过渡，将a柱上的（n）移到c柱上 if (n=0) return; /如果n=0，则退出，即结束程序 mov(n-1,a,b,c ); /用c柱作为协助过渡，将a柱上的（n-1）片移到b柱上 k+; cout cendl; mov(n-1,b,c,a ); /用a柱作为协助过渡，将b柱上的（n-1）移到c柱上 ,int main() coutn; mov(n,a,c,b); ,程序定义了把n片从A柱移到C柱的过程mov (n,a,c,b)，这个过程把移动分为以下三步来进行： 先调用过程mov (n-1, a, b, c)，把(n-1)片从A柱移到B柱, C柱作为过渡柱; 直接执行 writeln(a, -, c)，把A柱上剩下的一片直接移到C柱上，; 调用mov (n-1,b,c,a)，把B柱上的(n-1)片从B移到C柱上，A柱是过渡柱。 对于B柱上的(n-1)片如何移到C柱，仍然调用上述的三步。只是把(n-1)当成了n，每调用一次，要移到目标柱上的片数N就减少了一片，直至减少到n=0时就退出，不再调用。exit是退出指令，执行该指令能在循环或递归调用过程中一下子全部退出来。 mov过程中出现了自己调用自己的情况，在Pascal中称为递归调用，这是Pascal语言的一个特色。对于没有递归调用功能的程序设计语言，则需要将递归过程重新设计为非递归过程的程序。,【例4】用递归的方法求斐波那契数列中的第N个数,【参考程序】 #include using namespace std; int a11; int fib(int); int main() int m; cinm; coutfib(m)=fib(m); ,int fib(int n) if (n=0) return 0; /满足边界条件，递归返回 if (n=1) return 1; /满足边界条件，递归返回 return (fib(n-1)+fib(n-2); /递归公式，进一步递归 输入 15 输出 fib(15)=610,【例5】集合的划分 【问题描述】 设S是一个具有n个元素的集合，Sa1，a2，an，现将S划分成k个满足下列条件的子集合S1，S2，Sk ，且满足： 则称S1，S2，Sk是集合S的一个划分。它相当于把S集合中的n个元素a1 ，a2，an 放入k个（0kn30无标号的盒子中，使得没有一个盒子为空。请你确定n个元素a1 ，a2 ，an 放入k个无标号盒子中去的划分数S(n，k)。 【输入样例】setsub.in 23 7 【输出样例】setsub.out 4382641999117305,【算法分析】 先举个例子，设S1，2，3，4，k3，不难得出S有6种不同的划分方案，即划分数S(4，3)=6，具体方案为： 1，234 1，324 1，423 2，314 2，413 3，412 考虑一般情况，对于任意的含有n个元素a1 ，a2，an的集合S，放入k个无标号的盒子中去，划分数为S(n，k)，我们很难凭直觉和经验计算划分数和枚举划分的所有方案，必须归纳出问题的本质。其实对于任一个元素an，则必然出现以下两种情况： 1、an是k个子集中的一个，于是我们只要把a1，a2，an-1 划分为k1子集，便解决了本题，这种情况下的划分数共有S(n1，k1)个； 2、an不是k个子集中的一个，则an必与其它的元素构成一个子集。则问题相当于先把a1，a2，an-1 划分成k个子集，这种情况下划分数共有S(n1，k)个；然后再把元素an加入到k个子集中的任一个中去，共有k种加入方式，这样对于an的每一种加入方式，都可以使集合划分为k个子集，因此根据乘法原理，划分数共有k * S(n1，k)个。,综合上述两种情况，应用加法原理，得出n个元素的集合a1，a2，an划分为k个子集的划分数为以下递归公式：S(n，k)S(n1，k1) + k * S(n1，k) (nk，k0)。 下面，我们来确定S(n，k)的边界条件,首先不能把n个元素不放进任何一个集合中去，即k=0时，S(n，k)0；也不可能在不允许空盒的情况下把n个元素放进多于n的k个集合中去，即kn时,S(n，k)0；再者，把n个元素放进一个集合或把n个元素放进n个集合，方案数显然都是1，即k=1或k=n时，S(n,k)=1。 因此，我们可以得出划分数S(n，k)的递归关系式为： S(n，k)S(n1，k1) + k * S(n1，k) (nk，k0) S(n，k)0 (nk)或(k0) S(n，k)1 (k=1)或(kn),【参考程序】 #include using namespace std; int s(int n, int k) /数据还有可能越界，请用高精度计算 if (n n k; cout s(n,k); return 0; ,【例6】数的计数(Noip2001) 【问题描述】 我们要求找出具有下列性质数的个数（包括输入的自然数n）。先输入一个自然数n（n1000），然后对此自然数按照如下方法进行处理： 不作任何处理； 在它的左边加上一个自然数，但该自然数不能超过原数的一半； 加上数后，继续按此规则进行处理，直到不能再加自然数为止。 输入：自然数n（n1000） 输出：满足条件的数 【输入样例】 6 满足条件的数为 6 (此部分不必输出) 16 26 126 36 136 【输出样例】 6,【方法一】 用递归，f(n)=1+f(1)+f(2)+f(div/2)，当n较大时会超时，时间应该为指数级。 【参考程序】 #include using namespace std; int ans; void dfs(int m) /统计m所扩展出的数据个数 int i; ans+; /每出现一个原数，累加器加1； for (i = 1; i n; dfs(n); cout ans; return 0; ,【方法二】：用记忆化搜索，实际上是对方法一的改进。设hi表示自然数i满足题意三个条件的数的个数。如果用递归求解，会重复来求一些子问题。例如在求h4时，需要再求h1和h2的值。现在我们用h数组记录在记忆求解过程中得出的所有子问题的解，当遇到重叠子问题时，直接使用前面记忆的结果。 【参考程序】 #include using namespace std; int h1001; void dfs(int m) int i; if (hm != -1) return; /说明前面已经求得hm的值，直接引用即可，不需要再递归 hm = 1; /将hm置为1，表示m本身为一种情况