数据结构中递归转非递归算法分析及模型设计研究

2011-11-02孙召伟赵建利朱东生

河北科技大学学报 2011年1期

关键词：模型

孙召伟,赵建利,朱东生

数据结构中递归转非递归算法分析及模型设计研究

孙召伟1,赵建利2,朱东生3

(1.河北省大中专院校学生信息咨询与就业指导中心,河北石家庄 050061;2.河北工业大学电气工程学院,天津 300130;3.河北师范大学数学与信息科学学院,河北石家庄 050016)

为构建数据结构中递归算法的统一知识体系,分析了常见数据结构的递归本质及递归算法的组成要素,提出了递归算法转非递归算法的一般原则,根据递归算法的分类设计转换模型,通过实例分析其可行性。

递归算法;数据结构;非递归;模型设计

递归以其思路明确、代码简洁在数据结构算法中,特别是在解决树、图等问题过程中得到了广泛应用[1-6]。但其求解过程中系统开辟的栈,以存储每一层的返回点、局部量等信息,开销大,算法运行效率较低,且递归层次深,易造成栈溢出等问题。为了避免这种情况的发生,通常采用算法实现递归到非递归的转换。文献[7]—文献[9]给出了针对某些特定问题的递归到非递归的转换算法。

集合、线性表、广义表、树、图这5大数据结构都可以看作是由某一个元素和所有后继构成的相同的数据结构所组成,递归是众多数据结构物理构造和逻辑意义上的统一体。这使得与数据结构相关的众多递归算法在表现形式上有许多共性,将它们转换为非递归算法时有一些通用模型。