《递归算法详解》由会员分享，可在线阅读，更多相关《递归算法详解（55页珍藏版）》请在金锄头文库上搜索。
1、冯文科一、递归的基本概念。一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。二、递归的最简单应用：通过各项关系及初值求数列的某一项。在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及an与前面临近几项之间的关系。要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。
2、比如阶乘数列1、2、6、24、120、720如果用上面的方式来描述它，应该是：1,n1nani,n1如果需要写一个函数来求an的值，那么可以很容易地写成这样:intf(intn)if(n=1)return1;returnn*f(n-1);这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一些特殊情况一一这也是递归函数的第一个出口，再处理递归关系一一这形成递归函数的第二个出口。递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。以上面求阶乘数列的函数f(n)为例
3、。如在求f(3)时，由于3不是特殊值，因此需要计算3*f(2),但f(2)是对它自己的调用，于是再计算f(2),2也不是特殊值，需要计算2*f(1),需要知道f(1)的值，再计算f(1),1是特殊值，于是直接得出f(1)1,返回上步，得 f (2) 2* f (1) 2 ,再返回上一步，得f(3)3*f(2)3*26,从而得最终解。用图解来说明，就是f (3)的执行过程(特殊值判断：)3 1 ,继续向下。(递归关系处理：)(特殊值判断：)2 1,继续向下。(递归关系处理：)f (2)的执行过程f (1)的执行过程(特殊值判断：)1 1 ,由特殊情况出口直接返回1。求3* f (2),需要先求2
4、* f(1),需要先计算f(2),调用且本身挂起常出口返回3*2得到f (2) 2,由正计算f(1),调用且本身挂起得到f(1) 1 ,由正常出口返回2*1卜面再看一个稍复杂点的例子。【例1】数列a。的前几项为1、111 1输入n ,编程求an的精确分数解。分析：这个题目较易，发现a1 1,其它情况下有an1、。如要求实数解的话，这基本1 an 1已经可以写出递归函数了。但由于题目要求精确的分数解，还需做一些调整。设an 1 9 ,P则由递归关系，有an11 an 1p,再约分化简，即得an。但发现一个问题: p q求出an1时，需要返回两个整数：分子q与分母p,而通常的函数只能返回一个整数。
5、这个问题一般有两类解决办法，一种是让求值函数返回一个结构体变量，这样就可以返回两个变量了（其实还可以不只两个呢）；另一种是在求值函数的参数表中加入两个指针变量或引用变量，通过参数给带回数值。但由于后一种做法会使程序结构不清晰一一返回值是由参数表得到的，因此我们使用前一种方法。另外，在通过aniq得出anp后，an就已经是最简分数了，无须化简。证明ppq如下：若q是最简分数，即说明p,q的最大公约数为1,即对任何1rq,都有qmodr与Ppmodr不全为0,不防记qmodra、pmodrb,则有（pq）modr（ab）modr只要a与b不全为0,且ar,br,就有a与（ab）modr不全为0。因
6、此对任何的1rq,有pmodr与（pq）modr不全为0。而对于qrp的情况而言，记pmodra,则有（pq）modr（aq）modr由于0ar,0qr,因此同样有pmodr与（pq）modr不全为0。所以对任意1rp,者B有pmodr与（pq）modr不全为0,因此它们的最大公约数为1,即一p-是最简分数。虽然这是个要求an1（即q）是最简分数的结论，但由于数pqp1列第二项为1,是最简分数，因此可以证明第三项也是最简分数，同时也证明对所有的an,2求出的一p-就是最简分数，无须化简。pq具体代码如下：/Exam1.cpp#includeusingnamespacestd;structFSu
7、nsignedlonglongq,p;；FSf(intn)FSr;if(n=1)r.q=1;r.p=1;returnr;r=f(n-1);r.p=r.p+r.q;r.q=r.p-r.q;returnr;intmain()FSr;intn;cinn;r=f(n);coutr.q/r.pendl;system(pause);return0;三、递归的精髓：只考虑当前一步，剩下的让下一步去做吧。对大多数问题而言，当它的规模缩小至“特殊情况”时，都可以非常轻易地得出问题的解，因此我们不过多地讨论“特殊情况”，只详细地讨论递归关系的确定。寻找递归关系，最低标准是它能使问题的规模变小，且变小后的问题与原问
8、题在本质上是一样的。当找到递归关系后，我们的递归函数只须处理特殊情况与递归关系，不需要处理其它的信息一一至于下一步的事情，就让下一步去做吧。另一个需要考虑的事情就是递归函数的参数表，首先，在通常情况下，参数表都要使用变量参数，且递归函数中尽量使用局部变量一一这会减少很多不必要的麻烦；其次，参数表中，大多都有一个表示当前在执行第几步的参数。【例2】下图是一个有向图，输入N(0N9),打印0N的所有路径。分析：仔细研究这个图的特点，发现以下规律：对任何结点i,都可以走到i1和i2,当然如果它们不超过9的话。由于要打印路径，因此需要保存查找过程中的部分路径信息。可以做一个全局数组path口来存储这个
9、信息，由于结点0没有来路，且是所有路径的起点，因此记path0=0,递归函数负责填写之后的路径结点。我们这样设计递归函数：首先，这个递归函数的参数表中至少需要一个参数i,它的意义是表示现在在填路径中的第几个结点，而pathi可以填的数，要么是上一个结点加1,要么是上一个结点加2,即pathi=pathi-1+1或pathi=pathi-1+2；其次，特殊情况的讨论：我们要找的是终止到N的路径，因此若出现pathi-1=N的情况，就说明已经找到路径，无须将当前层再填入结点，可以将path中的信息输出并结束函数了一一这是递归函数的特殊情况出口；第三、递归关系的处理：若还没到达结点N,则填写本结点p
10、athi,上文已说明，pathi=pathi-1+1或pathi=pathi-1+2,当然如果它们都不过9的话。将结点i填好后，说明路径向下走了一步，距离结点N更近了一步，问题规模已经变小。不要处理其它东西，直接递归，通过递归调用去填写i+1结点就可以了。这里有处和【例1】不相同的地方，即pathi是有两种可能可选的，我们的处理这这样的，先令pathi=pathi-1+1,然后递归调用，填写i+1结点，当这个调用返回时，说明所有pathi为pathi-1+1的路径都已经讨论完成了，再令pathi=pathi-1+2,再递归，当它返回时，整个函数执行完毕，形成正常的执行完成时的出口。具体代码如下
11、：/Exam2.cpp#includeusingnamespacestd;#defineMAX9intpathMAX,N;intwrite(inti)intj;for(j=0;ji;j+)coutpathj;coutpathiendl;voidf(inti)if(pathi-1=N)write(i-l);return;if(pathi-1+1=N)pathi=pathi-1+1;f(i+1)；if(pathi-1+2N;path0=0;f(1)；system(pause);return0;【例3】我的画笔。Windows中的画笔从Windows3.x时代开始就已经有了，虽然功能与Photosh
12、op不能相比，但它小巧而迅速，一般的简单功能还是很方便的。画笔中的填色工具是油漆桶，选定它，再指定一个颜色，在图片中一点，所有与这个点颜色相同且相连的象素就都被填充了。如下图示：画笔的油漆桶工具填充的是一个叫“四连通”的区域，即它只从上、下、左、右四个方向向外扩展。请编写程序，模拟油漆通工具。输入文件：Exam3In.txt中有10行，每行是一个10字符的字符串，表示一个10*10的图象，不同的字符表示不同的颜色；之后的一行有两个用空格分开的整数，表示油漆桶点中的位置，再后面一行是一个字符，表示油漆桶的填充颜色。输出文件：Exam3Out.txt,输出10行，每行10个字符的字符串，表示填充后
13、的图象。分析：本题给了一个点的位置，查找所有与它“四连通”的点就成为本题的核心问题。我们的算法是这样的：先从这个起点出发，沿四个方向展开，看这“直接相连”的四个点是否可以填充，若有可以的，则再以这个点为中心，再向四个方向展开直到所有可能展开的点都不能再展开了为止。递归函数这样设计：首先它的参数表需要两个参数，表示本次从哪个位置点展开；其次,依次讨论它四个方向上相邻的点是否可填充一一与起点颜色相同，如果可以，则填充，并以此点为中心，递归调用。代码如下：/Exam3.cpp#includeusingnamespacestd;#defineN10ifstreamfin(Exam3In.txt);ofstreamfout(Exam3Out.txt);charpicNN+1,c,p;intcol,row;voidfill(inti,intj)if(i-1=0&pici-1j=p)pici-1j=c;fill(i-1,j);if(i+1=0&picij-1=p)pic皿-1=c;fill(i,j-1);if(j+1N&picij+1=p)pic皿+1=c;fill(i,j+1)；intmain()inti;for(i=0;ipici;finrowcol;finc;p=picrowcol;picrowcol=c;fill(row,col);for(i=0
