资源描述：
《递归算法设计及其非递归化研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、递归算法设计及其非递归化研究汤亚玲(安徽工业大学计算机学院,安徽马鞍山243002)摘要:递归做为一种算法设计思想在求解实际问题和程序设计中广泛应用,采用递归设计的算法具有思路清晰、易于描述复杂问题等优点。文中对递归算法的理论依据、设计思想、应用、递归的内部执行过程做了较为全面的探讨,并以火车进站问题为例,重点分析了如何根据问题的递归表达函数扩充为递归算法。同时,对递归的非递归化作了较为深入的分析和探讨,并给出了实例源程序。理论分析和实践证明,在具体应用问题中,通过寻找问题对应的递归表达函数,可以容易和准确地设计出求解的递归算法,提高算法设计效率。关键词:递归;算法设计;递归表达函数
2、;栈文章编号:1673-629X(2009)11-0085-04中图分类号:TP301.6文献标识码:AResearchonRecursiveAlgorithmDesignandItsNon-recursiveFormTANGYa2ling(SchoolofComputer,AnhuiUniversityofTechnology,Maanshan243002,China)Abstract:Recursionasakindofalgorithmideaiswidelyusedinsolvingrealityquestionsandprograming.Algorithmwhichisd
3、ecribedbyrecursivemodehastheadvantagesofclarityanddecribingquestioneasily.Thispaperdoesresearchonfoundation,idea,applicationandexecutingprocedureofrecursionthroughly,andasaexampleofquestionofthetrainpullinginitanalyzeshowtoexpandtherecursionfuc2tiontorecursionalgorithminemphasis.Finallyitdoesst
4、udyfurtherlyonhowtotransformrecursionalgorithmintonon-recursivealgo2rithmandofferssourcecodeofexamples.Itprovesthatwecaneasilydesignthealgorithmfortheproblemonfindingouttherecursionex2pressionfunctionsandimprovedesigningefficiencybytheoryandpratice.Keywords:recursion;algorithmdesign;recursionex
5、pressionfunction;stack0引言1递归的理论根源人们对递归的研究源于数论,递归思想始于可计在运用计算机求解实际问题的过程中,针对具体的问题往往会选择不同的、最适合解决问题的算法去完成。这其中,有一类问题规模较大,但可以把问题化解成求解若干个规模较小和原问题类似的子问题,并且可以一直这样做下去,直到规模最小的问题可以求解,这种情形下往往会选择递归思想来分析和求解该类问题。程序设计中,递归表现为过程或函数在其定义中直接或间接调用自身的一种方法。递归的优点在于仅需少量的代码就可描述出解题过程所需要的多次重复计算,大大地减少了程序设计的代码量,其能力在于用有限的语句来定义对
6、象的无限集合,用递归思想描述的算法往往也十分简洁易懂。算性理论,在高级数理逻辑里有较为详细的定义和证明1～3。早在1936年,Church提出一般初等函数都可以定义为递归函数,Turing也提出论点:一般所说的可计算函数,是可用Turing机所计算的函数,而Kleene则证明了,一般递归函数也就是可用Turing机可计算的函数,这就是后来著名的Church-Turing论点1,2。实际上在设计算法时,可以对数论中对递归的论证加以简化,仅仅考虑简单的基于自然数集的递归问题(广义的递归论基于一般的序数,包括无穷序数)。一般地,简单递归函数可以定义如下:设有函数f(e1,e2)及g(e1)
7、,构造递归函数h的形式定义:h(u,0)=Ch(u,Sx)=f(x,h(u,g(x)))或者定义一个带参数v的递归函数h:h(v,u,0)=Ch(v,u,Sx)=f(v,x,h(v,u,g(v,x)))(1)(2)收稿日期:2009-03-28;修回日期:2009-06-29基金项目:安徽省自然科学基金项目(2006KJ062B);安徽省优秀青年人才基金项目(2009SQRZ076)作者简介:汤亚玲(1974-),男,硕士,副教授,研究方向为智能化信息处理
