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

孙召伟,赵建利,朱东生

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

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

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

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

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

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

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

1 递归算法的一般模型

1.1 常见数据结构的递归本质

所有的线性关系可以理解成由第1个元素和(除去第1个元素)剩余的元素组成,而剩余的元素又是一个相对较小的线性关系,如图1所示。

图1 线性表的递归结构Fig.1 Recursion structure of linear list

广义表可以理解成由第1个元素和(除去第1个元素)剩余元素的广义表组成,如图2所示。

图2 广义表的递归结构Fig.2 Recursion structure of generalized list

树是由根和除根外的若干棵子树组成,如图3所示。图可以理解成由某一顶点(起始点 —任意顶点都可作为起始点)及所有后继节点为起始点形成的子图组成,如图4所示。

数据结构都是由某一个元素和所有后继构成的相同的数据结构组成,数据结构的定义基本上是递归的。

1.2 递归算法一般模型

递归算法由2部分组成:1)最小问题,称为基本项;2)原问题与子问题的关系。它包含2部分内容,一是可以继续分解的子问题,称为递归项;二是不能继续划分的子问题,称为有解子问题。一般的表现形式如下。

最小问题决定了递归的出口。不能继续划分的子问题是按照问题的要求被处理,如输出、比较大小等。研究递归算法,主要是研究有解子问题,线性表处理的是第1个元素,树处理的是树根,广义表处理的是第1个节点,图处理的是起始顶点。根据递归项中有解子问题的处理顺序,将递归分为前序递归、中序递归和后序递归。

2 递归转非递归

2.1 一般原则

本文提出了一个自然问答系统，对于事实性问题，它能够生成完整自然语言句子形式的答案。首先获得大量的问题答案对，并将其与知识库进行对齐，为模型训练提供数据基础。然后提出了基于全局知识表示的两阶段答案生成模型。对于一个问题，第一阶段基于全局知识表示匹配想对应的事实三元组；第二阶段结合匹配事实和问题利用序列学习模型分别从前向和后向两个方法生成答案句子。在公开数据集的实验结果表明了该方法的有效性。未来计划从下面两个方向扩展现有的工作：(1)回答复杂的问题，它不仅需要检索多个事实，各个事实之间可能具有更复杂的结构；(2)设计更加灵活的模型纳入更多的外部资源(文本等)。

在将递归算法转换为非递归算法时,对递归算法中3项内容的处理对应3个基本原则。

原则1 有解子问题的处理不变。原来是输出内容现在仍是输出,原来是求和现在仍是求和。对当前节点的处理方式不会发生变化。

原则2 遇到递归项,一要入、出栈,二要进行循环。一般情况下,有几个递归语句就要有几重循环,而有时循环的重数可以简化。碰到递归语句要入栈,为的是将来某个时候访问当前节点或当前节点的后继;递归调用结束时要出栈,为的是访问当前节点或是将其后继节点入栈。对于尾递归,可以不进行入栈,而对于多条递归语句的后序递归,一个节点可能要多次入栈和出栈,需要作标记。

原则3 递归出口成为循环结束条件。循环结束条件除了递归出口之外还有“栈不空”这个条件。

2.2 前序递归转非递归

前序递归指递归项中先处理有解子问题,再处理可继续划分的子问题。一条递归语句的前序递归主要是针对线性表的,转换过程简单。如果为尾递归(即递归语句出现在代码最后),则只需直接进行缩小问题规模的操作,不用入栈。

2.2.1 2条递归语句

2条递归语句的递归算法主要针对广义表和二叉树,转换模型见模型1。此递归算法的递归项中有2个递归调用,按照一般原则,算法结构应为双重循环。内层循环由第6行的递归语句转换而来,外层循环由第7行的递归语句转换而来。模型1见图5。

图5 模型1Fig.5 Conversion model 1

2)有解子问题的处理不变。

3)第6行的递归语句。实参入栈,问题规模变小;从头执行(就是循环)。入栈内容是当前节点,因为当前节点的右子树还没被访问过。

4)遇到递归结束,出栈,并对栈中元素进行适当的处理。

5)第7行的递归语句。由于是尾递归,所以不用入栈,只是问题规模的缩小。外层循环结束的条件,除了是基本项的非之外,还增加了对栈非空的判定。

2.2.2 多条递归语句转换一般形式

多条递归语句的递归算法主要针对广义表、树和图。转换时可以在访问该节点的时候,用一个循环就将这个节点的所有后继都入栈,从而将循环的重数简化为两重。具体过程的模型见图6,一般模型见图7。

图6 模型2Fig.6 Coversion model 2

图7 模型3Fig.7 Conversion model 3

2.3 多条语句的后序递归转非递归

在多条递归语句的后序递归中,一个节点可能会多次入栈和出栈,为了确定是否到了访问该节点的时机,增加1个标志来表示该节点当前的访问状态,而且标志信息同该节点一起入栈、出栈。

1)增加1个结构体,作为存储入栈信息。2)一般模型(见图7)。一般的,如果当前节点没有右子树,在第1次入栈时就可将其标志置为0,这样可以减少一些不必要的入栈和出栈操作。即灰色代码部分可以改写为

带标志的节点入栈。

3 结 语

在详细分析递归算法组成要素的基础上,根据递归算法的分类,系统地提出了递归转非递归的一般原则和实用模型,完善了数据结构中递归算法的知识体系,为研究众多与数据结构相关递归算法的转换过程提供了有效的解决方案,可推广性强。

[1] 徐孝凯.数据结构实用教程[M].北京:清华大学出版社,2004.

[2] 严蔚敏.数据结构(C语言版)[M].北京:清华大学出版社,1997.

[3] BRASSARD G,BRA TLEY P.Fundamentals of Algorithmics[M].London:Prentice-Hall International,1996.

[4] 周 康,同小军,许 进.基于闭环DNA模型的八皇后问题算法[J].计算机工程与应用(Computer Engineering and Applications),2007,43(6):4-6.

[5] 田烽楠,王 于.求解0-1背包问题算法综述[J].软件导刊(Software Guide),2009,8(1):59-61.

[6] 张 斌,金晨辉.基于回溯法的逆推攻击[J].电子与信息学报(Journal of Electronics and Info rmation Technology),2008,30(10):2 464-2 467.

[7] 游 珍,薛锦云.Hanoi塔非递归算法的形式化推导和正确性验证[J].计算机研究与发展(Journal of Computer Research and Development),2008(S1):143-147.

[8] 朱振元,朱 承.递归算法的非递归化实现[J].小型微型计算机系统(Journal of Chinese Computer Systems),2003(3):567-570.

[9] 孙 涌.递归算法的非递归实现[J].计算机研究与发展(Journal of Computer Research and Development),1995(11):1-7.

Analysis and model design of conversion algorithm from recursion to non-recursion in data structure

SUN Zhao-wei1,ZHAO Jian-li2,ZHU Dong-sheng3

(1.Hebei College Students Information and Emp loyment Center,Shijiazhuang Hebei 050061,China;2.School of Electrical Engineering and Automation,Hebei University of Technology,Tianjin 300130,China;3.College of Mathematics and Information Science,Hebei No rmal University,Shijiazhuang Hebei 050016,China)

In order to construct the scientific systematization of know ledge of recursion in data structure,this paper analyzed the recursion essence of common data structure and the componentsof recursive algo rithm,then p roposed the general p rincip les of the conversion from recursion to non-recursion.Based on the classifications of the recursion algo rithm,it also designed the conversion model w hose p ractical is verified.

recursion algo rithm;data structure;non-recursion;model design

TP183

A

1008-1542(2011)01-0043-04

2010-07-15;责任编辑:张 军

孙召伟(1978-),男,河北赵县人,学士,主要从事数据挖掘与算法分析方面的研究。