递归程序的非递归化研究

作者简介：李汶松（1991—），男，河南商丘人，在读硕士，主要从事计算机应用技术的研究。递归程序的非递归化研究李汶松（重庆理工大学计算机科学与工程学院）摘要：递归的特点是程序简练易读，结构清晰，其正确性也易证明，但由于其执行效率往往太低，所以在程序执行较频繁的部分一般不用递归。本文列出了几种递归程序的非递归化实现方法，以解决此问题。关键字：递归；程序；算法；非递归化Abstract：Recursiveprocedureischaracterizedbyconciseandeasytoread,clearstructure,anditisalsoeasytoprovethecorrectness.However,dueinparttotheefficiencyofitsimplementationisoftentoolow,morefrequentintheprogram'sexecutionisgenerallynotrecursive.Thisarticlelistsseveralwaystoachieveanon-recursiverecursiveproceduretosolvethisproblem.Keywords:recursive;program;algorithm;non-recursive1引言递归过程普遍的应用于程序的设计中，通常以下三种情况会用到递归方法：定义是递归的、数据结构是递归的、问题的解法是递归的。设计递归算法时，通常可以先写出问题求解的递归定义，递归定义由基本项和归纳项两部分组成。基本项描述递归过程的终结状态，即不需要继续递归而可以直接求解的状态。归纳项描述了如何实现从当前状态到终结状态的转化。递归过程的特点是结构清晰、程序简练易读、其正确性也容易证明，但其执行过程却往往效率很低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。故而需要将递归过程转换为非递归过程。在递归算法中消除递归调用，使其转化为非递归算法，可采用一下几种方式：1采用一个用户自定义的栈来模拟系统的递归调用工作栈。当递归调用时当前层的信息进栈并转向递归入口，当递归返回时相应的信息从栈中弹出，并按弹出信息中的返回地址转向递归调用的下一个语句继续执行。2用递推来实现递归函数。3通过变换能将一些递归转化为尾递归，从而迭代求出结果。第一种方法通用性较强，但本质上还是递归，只不过人工做了本该由编译器做的事，优化效果不明显，后两种在时空复杂度上均有较明显优化，但应用范围有限。本文列出了几类递归算法直接转换成非递归算法的实现方法，分别说明了这几类递归算法的特点及算法实例并给出了相应的非递归算法。2转化为尾递归当递归调用是整个最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器就利用这个特点自动生成优化的代码。为了说明尾递归与非尾递归的区别，我们来看一下求阶乘的两种算法：非尾递归：intfacttail(intn){if(n0)return0;if(n==0)return1;if(n==1)elsereturnn*facetail(n-1);}尾递归：intfacttail(intn,inta){if(n0)return0;elseif(n==0)return1;elseif(n==1)returna;elsereturnfacttail(n-1,n*a);}从上面两段代码的比较中可以看出尾递归与非尾递归的区别就在于非尾递归多了一个参数“a”。非尾递归利用“a”来维护递归层次的深度，这就避免了每次还需要将返回值再乘以“n”。如此一来，就不必在栈中开辟一长串的空间来保存每次递归调用的返回地址、局部变量、参数等信息了。这是一种方法虽说仍是递归，但在空间复杂度上已经大大优化了。3自底向上的递推有一类递归函数，其函数值与其项数有关，结果形成一个数列，对与这些递归函数可以使用递推的方法进行处理。递归调用的执行过程包括自顶向下的递归调用以及自底向上的的递归返回两个过程，而递推就是自底向上的处理过程，故而这种递推是比较直接的。举例说明之：F数列的定义如下：F(1)=F(2)=1F(n)=F(n-1)+F(n-2)(n2)可以用自底向上的递推得到如下的非递归函数：intF（n）{inti=3,f1=1,f2=1,f;if（n=2）return1;elsewhile(i=n){f=f1+f2;f1=f2;f2=f;i++;}returnf;}在上述问题中，利用递推避免了递归的使用。4利用循环来避免递归有的递归参数是逐次的向基本项中指定的参数接近的，对于这类问题可以通过设置一个循环来实现非递归化，在循环中循环控制变量的初值为参数值，而循环进行的条件是循环控制变量为逮到基本项中的变量值。下面用一个简单的例子来说明：求链表长度，递归函数可表示如下：intlinklistlength(linklist*head){if(!head)return0;returnlinklistlength(linklist*head-next)+1;}上述函数中，linklist*head是逐项的向基本项接近的，故而可对其设置一个循环，如下：intlinklistlength(linklist*head){intlinklistlength=0;for(linklist*head-next=head；linklist*head！=null；linklist*head=linklist*head-next)linklistlength++;}如此一来，递归就被避免掉了。5结束语我们再设计算法的时候,往往要考虑算法执行的时间复杂度与空间复杂度,也要考虑程序的易读性,而易读性与时空复杂度往往是背道而驰的,这就需要我们根据具体情况做出相应对策.在执行效率为次要条件时,便提高其可读性;在执行较为频繁,或者主宰着程序的整体效率的地方应主要考虑如何提高运行效率,可读性便可放置于第二位。在需要考虑效率的时候往往需要把易读的递归算法转化为不太易读非递归的算法。可参照本文所提到的几点方法，对其进行转化。参考文献:[1]王晓东.计算机算法设计与分析(第3版).电子工业出版社.2009.[2]严蔚敏,等.数据结构[M].北京.清华大学出版社.1992.[3]谭浩强.C程序设计[M].北京.清华大学出版社.1999.[4]孟林,李忠.递归算法的非递归化研究[J].计算机科学.2001.28(8);96—98.