數據結構中遞歸轉非遞歸算法分析及模型設計研究

孫召偉,趙建利,朱東生

數據結構中遞歸轉非遞歸算法分析及模型設計研究

孫召偉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-),男,河北趙縣人,學士,主要從事數據挖掘與算法分析方面的研究。