递归算法

递归算法[递归的描述]由上面的例子可以看出，一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。因此，在考虑使用递归算法编写程序时，应满足两点：1）该问题能够被递归形式描述；2）存在递归结束的边界条件。递归的能力在于用有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分简洁易懂。[例2]给出一棵二叉树的中序与后序排列。求出它的先序排列。[分析]通过对比二叉树的中序与后序排列，我们可以找出根节点及左右子树。同样的，有可以通过对比左子树的中序与后序排列，找出左子树的根节点……可见，该问题能够被递归描述。当找到最后一个根节点时，递归无法再进行下去，这就是递归结束的边界条件。由此可见，递归算法中常常隐含了分治思想。程序如下：programchu01_3;varz,h:string;procedurefind(a,b:string);vars,l:integer;beginl:=length(b);ifl=1thenWrite(b){边界条件及递归返回段}elsebegin{递归前进段}Write(b[l]);s:=pos(b[l],a);ifs-10thenfind(copy(a,1,s-1),copy(b,1,s-1));{递归左子树}ifl-s0thenfind(copy(a,s+1,l-s),copy(b,s,l-s));{递归右子树}end;end;beginReadln(z);Readln(h);Find(z,h);Readln;end.[递归的应用]1.经典递归例如hanoi塔问题：经典的递归，原问题包含子问题。有些问题或者数据结构本来就是递归描述的，用递归做很自然。2.递归与递推利用递归的思想建立递推关系，如由兔子生崽而来的fibonacci数列。但递推由于没有返回段，因此更为简单，有时可以直接用循环实现。3.分治不少分治方法是源于递归思想，或是递归分解+合并处理。4.回溯规模较小的问题用回溯解决比较自然。注意递归前后要保证现场的保存和恢复，即正确的转化问题。5.动态规划动态规划的子问题重叠性质与递归有某种相似之处。递归+动态修改查表是一种不错的建立动态规划模型的方法。6.其他其他么，就是不好归类。例如表达式处理，排列组合等。附带说一下，用递归来处理打印方案的问题还是很方便的。[例3]求把一个整数n无序划分成k份互不相同的正整数之和的方法总数。[分析]这是一道动态规划题，动态方程如下：f[i-1,j]+f[i,j-i]+1（(jmodi=0)and(jdivi=1)）f[i,j]:=f[i-1,j](i=j)f[i-1,j]+f[i,j-i]（else）s:=f(k,n-k)本题可以用循环来实现递推,也可以考虑用递归求解。主过程如下：方案一：Procedurework(I,j:longint;vars:longint);Vart:longint;BeginIf(i=1)or(j=1)thens:=1Elseif(i=0)or(j=0)thens:=0Elsebeginif(jmodi=0)and(jdivi=1)thenbeginwork(i-1,j,s);t:=s;work(i,j-1,s);s:=s+t+1;endelseif(i=j)thenwork(i-1,j)elsebeginwork(i-1,j,s);t:=s;work(I,j-1,s);s:=s+t;end;End;方案二：proceduresearch(v,w,last:byte);vari:byte;beginifw=0theninc(count)elseifw=1thenifv=lastthensearch(0,0,0)elseelsefori:=lasttov-1dosearch(v-i,w-1,i);end;可以看出，方案一的程序较为冗长，消耗栈空间较大；而方案二较为简洁明了，所用的栈空间也较小，效率较高。因此，使用递归算法也有一个优化问题。算法的简洁与否直接制约了程序的可行性和效率。[总结]递归使一些复杂的问题处理起来简单明了，尤其在学习算法设计、数据结构时更能体会到这一点。但是，递归在每一次执行时都要为局部变量、返回地址分配栈空间，这就降低了运行效率，也限制了递归的深度。因此，在必要的时候可以只使用递归的思想来求解，而程序则转用非递归的方式书写。1、打靶问题一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种，下面用递归算法实现：(C++代码)#includeiostreamusingnamespacestd;intsum=0;intstore[10];voidOutput(){for(inti=9;i=0;--i){coutstore[i]'';}coutendl;++sum;}voidCompute(intscore,intnum){if(score0||score10*(num+1))return;if(num==0){store[num]=score;Output();return;}for(inti=0;i=10;++i){store[num]=i;Compute(score-i,num-1);}}intmain(){Compute(90,9);coutSum=sumendl;return0;}2、八皇后问题这是一个古老而著名的问题，是回溯算法的典型例题：在8*8格的国际象棋盘上摆放8格皇后，使其不能相互攻击，即任意两个皇后都不能处在同一行、列或同一斜线上，问有多少种摆法。算法分析：数组a、b、c分别用来标记冲突，a数组代表列冲突，从a[0]~a[7]代表第0列到第7列。如果某列上已经有皇后，则为1，否则为0.数组b代表主对角线冲突，为b[i-j+7]，即从b[0]~b[14]。如果某条对角线上已经有皇后，则为1，否则为0。数组c代表从对角线冲突，为c[i+j]，即从c[0]~c[14]。如果某条从对角线上已经有皇后，则为1，否则为0。代码如下：#includestdio.hstaticcharQueen[8][8];staticinta[8];staticintb[15];staticintc[15];staticintiQueenNum=0;voidqu(inti);/*iisrownumber*/intmain(){intiLine,iColumn;for(iLine=0;iLine8;++iLine){a[iLine]=0;for(iColumn=0;iColumn8;++iColumn)Queen[iLine][iColumn]='*';}for(iLine=0;iLine15;++iLine)b[iLine]=c[iLine]=0;qu(0);return0;}voidqu(inti){intiColumn;if(i==8){intiLine;printf(Status%d:\n,++iQueenNum);for(iLine=0;iLine8;iLine++){for(iColumn=0;iColumn8;++iColumn)printf(%c,Queen[iLine][iColumn]);printf(\n);}printf(\n\n);}for(iColumn=0;iColumn8;++iColumn){if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0){Queen[i][iColumn]='@';/*placequeenhere*/a[iColumn]=1;b[i-iColumn+7]=1;c[i+iColumn]=1;qu(i+1);Queen[i][iColumn]='*';a[iColumn]=0;b[i-iColumn+7]=0;c[i+iColumn]=0;}}}大牛生小牛的问题问题：一只刚出生的小牛，4年后生一只小牛，以后每年生一只。现有一只刚出生的小牛，问20年后共有牛多少只？思路：这种子生孙，孙生子，子子孙孙的问题，循环里面还有循环的嵌套循环，一看就知道是第归问题。于是乎,第一个版本出现：publiclongCompute1(uintyears){//初始化为1头牛longcount=1;if(years=3){returncount;}inti=4;while(i=years){intsubYears=i-3;count+=Compute1((uint)(subYears));i++;}return(long)count;}可是这种循环在循环的做法可要把cpu老兄累坏了，你不信输入一个100年测试一下上面的方法，我等了半天，都没结果，改进一下吧，老牛（牛魔王）和小牛（红孩儿，奶奶的串种了），具有相同的生育能力，他们的生育曲线是一样的，所以小牛可以复用老牛的生育经验亚，这样就解决了重复计算一只牛第n年的时候一共生多少只的问题了，当年龄比较大的时候，明显大大降低cpu的运算次数，下面是基于这种思路的算法Hashtabletable=newHashtable();publiclongCompute(uintyears){//初始化为1头牛longcount=1;if(years=3){returncount;}inti=4;while(i=years){intsubYears=i-3;if(table.ContainsKey(subYears)){count=(long)table[subYears];}else{count+=Compute((uint)(subYears));}if(!table.ContainsKey(subYears)){table.Add(subYears,count);}i++;}return(long)count;}用测试程序测试一下上面的推论吧，结果如下:1)当输入years比较小的时候，第一种方法耗时短，但两者的时间基本在一个数量级上2）当输入years比较大的时候，比如40以上的，第二种算法比第一种性能比在100以上，而且输入years越高，性能比越悬殊。测试结果截图：20年递归算法学习系列一（分而治之策略）分而治之的概念分而治之是一种使用递归解决问题的算法，主要的技巧是将一个大的复杂的问题划分为多个子问题，而这些子问题可以作为终止条件，或者在一个递归步骤中得到解决，所有子问题的解决结合起来就构成了对原问题的解决2.分而治之的优点和缺点分而治之算法通常包括一个或者多个递归方法的调用，当这些调用将数据分隔成为独立的集合从而处理较小集合的时候，分而治之的策略将会有很高的效率，而在数据进行分解的时候，分而治之的策略可能会产生大量的重复计算，从而导致性能的降低。3.画标尺程序的分析讲解画标尺是分而治之的策略的一个简单应用，标尺是由长度为1英寸的单元构成的序列，每个单元的末端有最长的记号，每个寸单元的1/2英寸处的记号要比末端的短，在1/4处的记号比1/2的要短，1/8处比1/4处短，编写一个程序，在一条线上，用规则间隔来绘制标记，在特定位置有特定大小的记号。分析：在一个直线上，我们可以首先将这条直线一分为二,然后对分出来的二个再进行拆分。直到满足一定的精度要求，比如以最小刻度为1/8英寸为例，drawRuler作为画标尺的第归函数，在drawRuler函数中用一段线段的两端(起点（startPos），终点(endPos))，和变量h作为参数,标记的基础高度为baseHeight，而标记的高度应该为h*baseHeight,则标尺的画法可以分析如下：计算间隔（0.0，1.0）的中点：midPos=(startPost+endPos)/2;在中点1/2处画一个标记，高度为3*baseHeight将中点分隔开的为两条直线，再使用第归函数drawRule，对应的起点，终点为（0.0，0.5）和(0.5,1.0)，参数h-1,这样可以使高度相比短些第归步骤