递归算法详解.doc

.递归冯文科一、递归的基本概念。一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。二、递归的最简单应用：通过各项关系及初值求数列的某一项。在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及与前面临近几项之间的关系。要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。比如阶乘数列1、2、6、24、120、720如果用上面的方式来描述它，应该是：如果需要写一个函数来求的值，那么可以很容易地写成这样：int f(int n)if(n=1)return 1; return n*f(n-1);这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况这也是递归函数的第一个出口，再处理递归关系这形成递归函数的第二个出口。递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。以上面求阶乘数列的函数为例。如在求时，由于3不是特殊值，因此需要计算，但是对它自己的调用，于是再计算，2也不是特殊值，需要计算，需要知道的值，再计算，1是特殊值，于是直接得出，返回上一步，得，再返回上一步，得，从而得最终解。用图解来说明，就是的执行过程（特殊值判断：），继续向下。（递归关系处理：）求，需要先计算，调用，且本身挂起得到，由正常出口返回的执行过程（特殊值判断：），继续向下。（递归关系处理：）求，需要先计算，调用，且本身挂起得到，由正常出口返回的执行过程（特殊值判断：），由特殊情况出口直接返回1。下面再看一个稍复杂点的例子。【例1】数列的前几项为1、输入，编程求的精确分数解。分析：这个题目较易，发现，其它情况下有。如要求实数解的话，这基本已经可以写出递归函数了。但由于题目要求精确的分数解，还需做一些调整。设，则由递归关系，有，再约分化简，即得。但发现一个问题：求出时，需要返回两个整数：分子与分母，而通常的函数只能返回一个整数。这个问题一般有两类解决办法，一种是让求值函数返回一个结构体变量，这样就可以返回两个变量了（其实还可以不只两个呢）；另一种是在求值函数的参数表中加入两个指针变量或引用变量，通过参数给带回数值。但由于后一种做法会使程序结构不清晰返回值是由参数表得到的，因此我们使用前一种方法。另外，在通过得出后，就已经是最简分数了，无须化简。证明如下：若是最简分数，即说明的最大公约数为1，即对任何，都有与不全为0，不防记、，则有只要与不全为0，且，就有与不全为0。因此对任何的，有与不全为0。而对于的情况而言，记，则有由于，因此同样有与不全为0。所以对任意，都有与不全为0，因此它们的最大公约数为1，即是最简分数。虽然这是个要求（即）是最简分数的结论，但由于数列第二项为，是最简分数，因此可以证明第三项也是最简分数，同时也证明对所有的，求出的就是最简分数，无须化简。具体代码如下：/ Exam1.cpp#include using namespace std;struct FS unsigned long long q, p;FS f(int n) FS r; if(n=1) r.q=1; r.p=1; return r; r=f(n-1); r.p=r.p+r.q; r.q=r.p-r.q; return r;int main() FS r; int n; cinn; r=f(n); coutr.q/r.pendl; system(pause); return 0;三、递归的精髓：只考虑当前一步，剩下的让下一步去做吧。对大多数问题而言，当它的规模缩小至“特殊情况”时，都可以非常轻易地得出问题的解，因此我们不过多地讨论“特殊情况”，只详细地讨论递归关系的确定。寻找递归关系，最低标准是它能使问题的规模变小，且变小后的问题与原问题在本质上是一样的。当找到递归关系后，我们的递归函数只须处理特殊情况与递归关系，不需要处理其它的信息至于下一步的事情，就让下一步去做吧。另一个需要考虑的事情就是递归函数的参数表，首先，在通常情况下，参数表都要使用变量参数，且递归函数中尽量使用局部变量这会减少很多不必要的麻烦；其次，参数表中，大多都有一个表示当前在执行第几步的参数。【例2】下图是一个有向图，输入，打印的所有路径。1357902468分析：仔细研究这个图的特点，发现以下规律：对任何结点，都可以走到和，当然如果它们不超过9的话。由于要打印路径，因此需要保存查找过程中的部分路径信息。可以做一个全局数组path来存储这个信息，由于结点0没有来路，且是所有路径的起点，因此记path0=0，递归函数负责填写之后的路径结点。我们这样设计递归函数：首先，这个递归函数的参数表中至少需要一个参数i，它的意义是表示现在在填路径中的第几个结点，而pathi可以填的数，要么是上一个结点加1，要么是上一个结点加2，即pathi=pathi-1+1或pathi=pathi-1+2；其次，特殊情况的讨论：我们要找的是终止到的路径，因此若出现pathi-1=的情况，就说明已经找到路径，无须将当前层再填入结点，可以将path中的信息输出并结束函数了这是递归函数的特殊情况出口；第三、递归关系的处理：若还没到达结点，则填写本结点pathi，上文已说明，pathi=pathi-1+1或pathi=pathi-1+2，当然如果它们都不过9的话。将结点填好后，说明路径向下走了一步，距离结点更近了一步，问题规模已经变小。不要处理其它东西，直接递归，通过递归调用去填写i+1结点就可以了。这里有处和【例1】不相同的地方，即pathi是有两种可能可选的，我们的处理这这样的，先令pathi=pathi-1+1，然后递归调用，填写i+1结点，当这个调用返回时，说明所有pathi为pathi-1+1的路径都已经讨论完成了，再令pathi=pathi-1+2，再递归，当它返回时，整个函数执行完毕，形成正常的执行完成时的出口。具体代码如下：/ Exam2.cpp#include using namespace std;#define MAX 9int pathMAX, N;int write(int i) int j; for(j=0;ji;j+) coutpathj; coutpathiendl;void f(int i) if(pathi-1=N) write(i-1); return; if(pathi-1+1=N) pathi=pathi-1+1; f(i+1); if(pathi-1+2N; path0=0; f(1); system(pause); return 0;【例3】我的画笔。Windows中的画笔从Windows3.x时代开始就已经有了，虽然功能与Photoshop不能相比，但它小巧而迅速，一般的简单功能还是很方便的。画笔中的填色工具是油漆桶，选定它，再指定一个颜色，在图片中一点，所有与这个点颜色相同且相连的象素就都被填充了。如下图示：画笔的油漆桶工具填充的是一个叫“四连通”的区域，即它只从上、下、左、右四个方向向外扩展。请编写程序，模拟油漆通工具。输入文件：Exam3In.txt中有10行，每行是一个10字符的字符串，表示一个10*10的图象，不同的字符表示不同的颜色；之后的一行有两个用空格分开的整数，表示油漆桶点中的位置，再后面一行是一个字符，表示油漆桶的填充颜色。输出文件：Exam3Out.txt，输出10行，每行10个字符的字符串，表示填充后的图象。分析：本题给了一个点的位置，查找所有与它“四连通”的点就成为本题的核心问题。我们的算法是这样的：先从这个起点出发，沿四个方向展开，看这“直接相连”的四个点是否可以填充，若有可以的，则再以这个点为中心，再向四个方向展开直到所有可能展开的点都不能再展开了为止。递归函数这样设计：首先它的参数表需要两个参数，表示本次从哪个位置点展开；其次，依次讨论它四个方向上相邻的点是否可填充与起点颜色相同，如果可以，则填充，并以此点为中心，递归调用。代码如下：/ Exam3.cpp#include using namespace std;#define N 10ifstream fin(Exam3In.txt);ofstream fout(Exam3Out.txt);char picNN+1, c, p;int col, row;void fill(int i, int j) if(i-1=0 & pici-1j=p) pici-1j=c; fill(i-1, j); if(i+1=0 & picij-1=p) picij-1=c; fill(i, j-1); if(j+1N & picij+1=p) picij+1=c; fill(i, j+1); int main() int i; for(i=0;ipici; finrowcol; finc; p=picrowcol; picrowcol=c; fill(row, col); for(i=0;iN;i+) foutpiciendl; return 0;本题中的递归函数fill似乎与常规的递归函数比较起来缺少了处理特殊情况的部分，其实不然，它的特殊情况处理已经被融合到递归关系的处理当中了，正常与非正常的出口合并到一起。特殊情况就是：当向四个方向都无法展开时，程序直接退出。这个程序的fill函数运用的算法就是“种子填充算法”的递归写法。它另有动态规划的写法当然比这个要快得多，大家可以想一想如何实现。四、递归函数的必然用法：处理递归定义的数据结构。一些常用的数据结构本身就是递归定义的，写一个递归的函数来处理它，当然是再正常不过的事情，就比如说二叉树、广义表【例4】二叉树的操作。用字符串的形式给定一个完全二叉树，保存在输入文件Exam4In.txt中，编写程序输出其后序遍历的结果至输出文件Exam4Out.txt中。分析：本题的程序是简单的，唯一要注意的是：C+的数组从下标0开始，因此对于结点,它的左孩子编号应该是，右孩子编号应该是。其它的地方没什么难度。代码如下：/ Exam4.cpp#include using namespace std;#define M 100ifstream fin(Exam4In.txt);ofstream fout(Exam4Out.txt);char treeM;int L;void run(int i) if(2*i+1L) run(2*i+1); if(2*(i+1)L) run(2*(i+1); fouttree; L=strlen(tree); run(0); return 0;【例5】以字符串形式给出一棵完全二叉树的先序遍历与中序遍历序列，编程输出用字符串形式表示的完全二叉树的结构。分析：先序遍历的首结点一定是整棵树的根，因此可以直接标在0处。在中序遍历序列中，它左边的结点构成左子树，右边的结点构成右子树，从而可以知道，左子树与右子树的结点个数，进而得到及左子树与右子树的先序遍历与中序遍历序列，递归查找所有子树的根即可。为了得到整棵树的结构，设置全局数组tree来存储，全局数组s的意义是：si存储整数表示第i层结点的起始下标。代码如下：/ Exam5.cpp#include using namespace std;#define M 100ifstream fin(Exam5In.txt);ofstream fout(Exam5Out.txt);char preM, midM, treeM;int L, sM;void build(int layer, int ps, int pe, int ms, int me) treeslayer=preps; slayer+; if(ps=pe) return; int i; i=ms; while(midi!=preps) i+; build(layer+1, ps+1, ps+i-ms, ms, i-1); build(layer+1, ps+i-ms+1, pe, i+1, me);int main() finpremid; L=strlen(pre); s0=0; int i, j; i=1; j=2; while(siL) si=j-1; j=j*2; i+; build(0, 0, L-1, 0, L-1); treeL=0; fouttree; return 0;五、递归与回溯法。递归的另一个常用的地方是实现回溯法。所谓回溯法，一般就是指先将问题分成几步，在每一步时尝试所有的可能，直到达到最终要求，或最后一步将所有可能尝试完成后，再回到上一步，使上一步尝试下一种可能，并继续的作法。由于回溯的“步骤性”明显，因此用递归实现回溯是相当方便的事。看下面的一个例题：【例6】n皇后问题。输入整数n，打印n皇后问题的所有解及解的总数。代码如下：/ Exam6.cpp#include using namespace std;#define MAX 100int n, qMAX, c;bool markMAX;void write() int i; char tMAX; memset(t, ., MAX*sizeof(char); tn=0; for(i=0;in;i+) tqi=Q; couttendl; tqi=.; coutendl;bool test(int i, int k) int j; j=0; while(jk & abs(j-k)!=abs(qj-i) j+; if(j=k & marki=false) return true; else return false;void search(int k) if(k=n) write(); c+; return; int i; for(i=0;in; memset(mark, 0, MAX*sizeof(bool); c=0; search(0); coutcendl; system(pause); return 0;六、练习【练习】为给定的表达式建立表达式树，并求值。给定的表达式中，所有数字都是1位正整数，出现的符号可能为、*、/、（、）。分析：这是一个与一般数据结构书上讲的用栈计算的方法本质不同的方法。在详细说明这个算法之前，需要首先明确这个算法用到的概念1、单元：一个单元可能是用括号括起来的一个表达式，或是一个整数；2、项：一个项是指由*与/连接起来的若干单元；3、表达式：一个表达式是指由或连接起来的若干项。要建立表达式树，需要三个函数互相调用的函数：一个是getunit，用于建立一个单元；一个是getexpr，用于建立一个项，另一个就是build，用于建立一个表达式。getunit函数较易，如果字符串首字母是（的话，那么从它后面的字符开始用build建立一个表达式，这个表达式就是一个单元；否则，就处理一个整数；getexpr函数是建立在getunit之上的，它先用getunit建立一个单元，然后不停地考察之后地连接符号是不是*或/，若是，则不停地重复读连接符、建立另一个单元、建立连接的操作，直到连接符号不是*或/为止。build函数是用于最终建立表达式的，它先用getexpr建立一个项，再用符号将剩余的各项连接成二叉树。代码如下：/ Exer.cpp#include using namespace std;struct NODE int n; char c; NODE *left, *right; NODE() left=NULL; right=NULL; ;char s100;int cur;NODE *tree;void clear(NODE *root) if(root=NULL) return; clear(root-left); clear(root-right); delete root;void cal(NODE *root) if(root-left!=NULL) cal(root-left); cal(root-right); switch(root-c) case +: root-n=root-left-n+root-right-n; break; case -: root-n=root-left-n-root-right-n; break; case *: root-n=root-left-n*root-right-n; break; case /: root-n=root-left-n/root-right-n; NODE *build();NODE *getunit() NODE *a; if(scur=() cur+; a=build(); else a=new NODE; a-n=scur-0; cur+; return a;NODE *getexpr() NODE *a, *b, *c; a=getunit(); while(scur=* | scur=/) b=new NODE; b-c=scur; cur+; c=getunit(); b-left=a; b-right=c; a=b; return a;NODE *build() NODE *a, *b, *c; a=getexpr(); while(scur!=0 & scur!=) b=new NODE; b-c=scur; cur+; c=getexpr(); b-left=a; b-right=c; a=b; if(scur=) cur+; return a;int main() cins; cur=0; tree=build(); cal(tree); coutn0又例如，Fibonacci(斐波那契)数列可递归定义为 0 若n=0Fib(n) = 1 若n=1 Fib(n-1)+Fib(n-2) 若n1 据此可以写出实现求n 的阶乘和求Fibonacci数列中第n项的递归算法，如算法21和算法22所示。long int fact(int n) /求非负整数n的阶乘if(!n) return 1; /0!=1else return n*fact(n-1); /n!=n*(n-1)!/fact算法21 求阶乘的递归算法long int fib(int n) /求斐波那契数列中的第n个数if(n1,f(n)=f(n-1)+f(n-2)/fib算法22 求斐波那契数的递归算法 一般地说，每一个递归函数的定义都包含两个部分。(1) 递归基础 对无需递归的规模最小的问题直接进行处理。(2) 递归步骤 将一般情况的问题简化成一个或多个规模较小的同性质的问题，递归地调用同样的方法求解这些问题，使这些问题最终简化成基础问题。 算法21的递归基础是n=0时，直接返回1（0！=1）。一般情况下，将fact(n)简化成规模较小的问题fact(n-1)，求出fact(n-1)后再与n相乘即求得了fact(n) 。 算法22的递归基础是n=01. if(n0) /若n=0,则不需做任何动作,仅当n0时2. hanoi(n-1,x,z,y); /先将n-1个盘从x柱经z柱搬到y柱 coutMove Disk n from x to zendl;/将第n个盘从x搬到z4. hanoi(n-1,y,x,z); /再将y柱上的n-1个盘经x柱搬到z柱5. /if6./hanoi算法23 求解汉诺塔问题的递归算法3 背包问题 设有一个背包可以放入总重量为S的物品，现有n件物品，重量分别为w1 ，w2，wn 。问能否从这n件物品中选择若干件放入背包，使得放入的物品总重量恰好为S。如果存在一组符合上述要求的物品，则称此背包问题有解(用TRUE表示问题有解)，否则称此问题无解(用FALSE表示无解)。假如我们定义一个维数组W存储各物品的重量，用布尔函数knap(S,n)求解背包问题。其参数S表示背包还留有的容量，n为可供选择的物品个数。显然，如果S=0，背包问题总有解，即knap(0,n)为TRUE，因为不选择任何物品放入背包即可。当S0但n0且n1，我们要求解背包问题有两种途径：一种是选择第n件物品放入背包，于是背包剩余的容量为SWn(Wn中存储wn ，即第n件物品的重量)，可选择的物品是前n-1件。如果knapn(s-wn,n-1)有解，则knap(S,n)也有解，否则knap(S,n)无解，说明选择第n件物品是错的。另一种是不选第n件物品，此时背包问题简化为knap(S,n-1)，如果它有解，则knap(S,n)也有解,如果它无解，则knap(S,n)也无解，从而背包问题可以递归地定义如下： TRUE 若S=0 knap(,n) = FALSE 若0且n0且n1上述递归定义是确定的，因为每次递归，n总减少1，S也可能减小Wn，所以递归若干次之后，递归基础的条件（S0或n1）必定成立,所以递归过程在有限步之后总能结束。 例5 用递归方法求解背包问题。根据knap(S,n)的定义，容易写出背包问题的递归算法，如算法24所示。const int MAXN=11; /假设最多只有十件物品int wMAXN=0,3,5,6,3,7,1,2,4,9,8; /假设物品的重量已存在w1.w10中int knap(int s,int n) / s为背包的容量,n为可供选择物品的最大编号if(s=0) return TRUE; /若背包已装满,则有解if(s0)&(n1)return FALSE;/若背包容量为负数或已无物品可选,则必无解 if(knap(s-wn,n-1) /先试探将第n个物品装入背包中,若因此有解,则原题有解 coutwn0)|!StackEmpty(s)/若尚未找到解且有物品可选或栈非空 if (n0) /如果还有物品可选 if (t=wn) /而且背包还能放得下 t-=wn; /就将物品n放入背包,t因此减少wn if (!StackFull(s) /若栈未满 Push(s,n); /将n入栈,即将物品n放入背包 -n; /因此可选物品的编号小1 if (t=0) found=1; /若背包已满,则求得一解 else exit(ERROR); /若栈已满,则出错 else -n; /若背包放不下物品n,则尝试选择物品n-1 /if(n0)/whileif (found) /如果找到一解,就将所选物品的重量输出 for (i=s.top; i0; -i) Pop(s,e); coutwe0;-i) /first中存储的数逐渐向第n个斐波那契数靠近 temp=first; first=second; second+=temp;/first移向下一个斐波那契数return first; /for语句结束时,first已是第n个斐波那契数/Fibo算法28 求斐波那契数的非递归算法 显然，也可以用图10来解释Fibo的执行过程。由于Fibo消除了递归，省掉了n次函数调用的开销，所以它的效率更高。 尾递归函数是一种特殊的递归函数。如果一个递归函数的返回值是直接计算而得或恰是一个递归调用自身而得到的返回值，那么这个递归函数就称为尾递归函数。换句话说，如果递归函数中有一个递归调用（自身）的语句是这个函数的最后一个可执行语句，那么这个函数就被称做尾递归函数。应该注意，最后一个可执行语句并不一定是程序中的最后一条语句。例如，Fib 的返回值或者是first（若n=0），或者是递归调用Fib的返回值，所以它是尾递归函数。从算法27中也可以看出。Fib函数中的递归调用语句