资源描述：
《数据结构中递归算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构中递归算法的研究与实现-----------------------Page1-----------------------第期总第期机械管理开发年月6(99)200712No.6(SUMNo.99)MECHANICALMANAGEMENTANDDEVELOPMENTDec.2007数据结构中递归算法的研究与实现郭韶升张炜(青岛科技大学信息科学技术学院山东青岛266042)【摘要】递归是一种重要的编程工具,在数据结构中多处使用。递归算法掌握的好坏直接影响数据结构的学习,从数据结构的角度出发,提出了一种有效的递归教学方法。【关键
2、词】递归算法;数据结构;教学方法【中图分类号】【文献标识码】【文章编号】()G462A1003-773X200706-0090-020引言个非递归函数,反映了递归问题的结构。递归是软件设计的重要方法和技术。递归省略了(2)递归原理。递归是把一个不能或不好直接求程序设计中许多细节操作,简化了程序设计过程,递解的“大问题”转化为一个或几个“小问题”来解决;再归函数结构清晰、程序易读,而且它的正确性容易得把这些“小问题”进一步转化为更小的“小问题”来解到验证。在许多实际问题求解时,采用递归方法要比决;如此“回推”,直到每个“小问题”都可直接
3、解决(此非递归方法容易实现。时“回推”到递归出口);再从递归出口返回到原问题的1递归是程序设计中强有力的一个工具求解过程[2]。(1)有很多数学函数是递归定义的,例如大家熟求f(Sn)的“回推”过程为:f(Sn)→f(Sn-1)→…悉的阶乘函数Fact(n)=!1若n=0。→f(S1)→f(S0)。一旦遇到递归出口,“回推”过程结·()若nFactn-1n>0束,开始求值过程。所以“回推”过程是“量变”过程,即(2)有的数据结构,例如二叉树、广义表,由于结构本原来的“大问题”在慢慢变小,但尚未解决,遇到递归出身固有的递归特性,它的许多
4、操作可按递归描述。(3)口后,便发生了“质变”,即递归问题变成了直接问题。还有一类问题,虽然问题本身没有明显的递归性,但上面的求解过程如下:f(S)=M→f(S)=g(f(S),用递归求解比迭代求解更简单,如八皇后问题、0010Hanoi塔问题等。(4)由于递归在“数据结构”中多处使用,因C1)→f(S2)=g(f(S1),C2)→…→f(Sn)=g(f此正确理解并准确使用递归,对于提高程序设计能力(Sn-1),Cn)。这样f(Sn)便计算出来了。可以看出,求的培养是非常重要的。值过程是从一个已知值推出下一个值。实际上这是一鉴于上述情
5、况,结合自己的教学实践和学生的实个递推过程。因此,一个递归问题可以分为“回推”和际情况,总结出递归的讲解方法:首先确定求解问题“递推”两个阶段,要经过许多步才能求出最后的值。的递归模型,了解递归原理;在此基础上介绍了一种(3)递归程序的阅读。阅读递归程序的简单直观阅读递归程序的有效方法,使学生在对递归程序有一方法是图形化方法。该方法借助具体的图形,运用遍历定熟练程度后,开始递归程序的设计[1]。树的思考,对抽象的函数递归调用的运行轨迹进行层2递归算法的分析与设计层剖析,使函数递归调用的过程如折扇一样展开,形象(1)递归模型。递归算法的
6、设计要先确定递归模化地呈现在学生面前。该方法描述为:1)按次序写出型。一个递归模型由递归出口和递归体两部分组成,程序当前调用层上实际执行的各语句,并用有向弧表前者确定递归到何时为止,后者确定递归的方式。递示该语句的执行次序。2)对程序中每个调用语句,写归出口即结束递归过程的条件。计算机是用栈来管理出其调用形式,并在其下边写出本次调用函数实际执递归的,如果不设置结束递归的条件,无限制的递归行的语句。同时在被调层的前面注明各形参的值;从调调用必然造成因栈溢出而中断或死机。所以要使递归用操作处画一有向弧指向被调函数的入口表示调用线正常结束,
7、就必须有一个递归出口。递归出口的一般路;从被调函数的末尾处画一有向弧指向调用操作的格式为:f(S0)=M0(如阶乘函数中的Fact(0)=1);这下面,表示返回线路。3)在返回线路上标出本次调用里的S和M均为常量,有的递归问题可能有几个递所得到的函数值。00归出口。递归体的一般格式为:f(S)=g(f(S1),f经这样表示后,有向弧的方向指出了程序的实际运行轨迹,程序执行的各个中间环节就会一目了然。例(S2),…,f(Sn),C1,C2,…Cn);这里的S是一个递如:如下递归函数的图形化示例。归“大问题”,S1,S2,…,Sn为递归“
8、小问题”,C1,C2,()()subintnifn==1a=1;!;();…Cn是可以直接解决(用非递归方法)的问题,g是一intaa=n+subn-1作者简介:郭韶升,男,1973年生,山东科技大学毕业,硕士研究生,从
