基于復雜遞歸類問題的可重用程序模板研究

摘要：構建復雜遞歸類問題的可重用程序模板主要是為了提高學習者分析和解決類似問題的能力。文章分析了構建可重用程序模板的理由及其設計思想，并且深入地研究了復雜遞歸類問題的非遞歸算法，實現了部分復雜遞歸類問題的可重用程序模板；在求解同類型問題時，只需向可重用程序模板輸入問題的相應參數，就可獲得該類問題的實例，并且通過此模板自動推理產生程序設計的全過程。文章實現了既有問題又有解答的無限題庫，為生成無限題庫提供了技術支持和理論依據。

關鍵詞：遞歸問題；可重用程序模板；自動推理；軟件重用

0 引言

使用遞歸方法設計程序會使很多復雜問題變得簡單和通用。遞歸是程序設計中的一個強有力的工具。對于一些本身沒有明顯遞歸結構的問題也可以利用遞歸技術設計出簡單易懂的算法程序，但其難度相應要大許多。利用遞歸方法編寫出來的程序，結構簡練、清晰，可讀性強，而且它的正確性容易得到證明。正是由于它以簡潔、抽象的語句解決了復雜的問題，而使得初學者感到遞歸程序深不可測，遞歸程序的設計更是望塵莫及。

在程序設計中，程序的可讀性與程序的執行效率往往是互相制約的。遞歸算法只需要寫出問題的分解形式和組合答案的方法，至于如何遞歸地求解各個子問題則由系統幫助解決；而遞推算法常以循環的形式出現，編寫程序時必須明確寫出循環內的每一步是如何實現的。另外，對于復雜遞歸問題的求解需要復雜的數據結構和控制方法，這使得初學者難以理解復雜遞歸問題的非遞歸實現，更不用說復雜遞歸問題的非遞歸實現的推導和證明。

為此，本文設計了一個能解決部分復雜遞歸類問題的可重用程序模板并在系統中實現了自動推理，其中利用了PAR方法的解題步驟形式化地推導程序，清晰地闡述了程序設計的全過程。這不但可以幫助初學者有效地理解和掌握遞歸算法的非遞歸實現，而且也可以提高他們設計算法和揭示事物本質特征和規律的能力。

1 設計思想

復雜遞歸類問題的可重用程序模板的構建主要是利用了軟件重用技術和事物相似性原理，其基本思想是：從一組類似的事物中抽象出一種框架型的模板，任何一個類似的事物都可作為以模板為超類派生的類型的實例Ⅲ。若能用一個形式模型來刻劃問題的本質，那將是十分有益的事，一旦將問題形式化，就可以依據這個模型對問題進行求解。

遞歸問題作為一類特殊問題，本文對該類問題的非遞歸算法作了大量深入的研究并尋找這些算法的共同特征，發現有些問題的求解方式有很多相似之處。對于一些復雜的遞歸類問題(如樹的遍歷、圖的深度優先遍歷、快速排序等)，常用的方法是將問題分劃為三個部分：已處理完成部分(用序列或集合x表示)，當前正在處理的部分和尚未及時得到處理的部分(用棧s保存)。正是基于這種相似之處，借鑒泛型程序設計思想，構造了復雜遞歸類問題可重用程序模板。

2 可重用程序模板

在數據結構中，對于樹是采用遞歸形式定義的。實際上樹和遞歸有著很緊密的聯系，遞歸問題的結構一般是某一種形式的樹狀結構。遞歸問題從大到小的分解和樹狀結構從整體到局部的分解都是類似的。遞歸的逐層深入和返回也就是樹狀結構的穿線過程。遞歸的第一次調用就是樹狀結構的根結點；以后的逐層調用就對應于樹狀結構每一層展開的子結點；遞歸調用的結束(也就是遞歸的終值)就對應于樹的葉子結點；并且在一個遞歸過程中往往存在多次的選擇調用關系，于是就形成了樹的分支。所以對應遞歸問題的調用關系就可以將其轉化為樹狀結構，遞歸的實現可以轉化成樹的遍歷。并且充分運用樹狀結構局部與整體的自相似將可以對遞歸問題的每一步進行充分的分解，使其復雜的嵌套過程變得層次清晰、關系明了。

有些問題本身具有樹狀形式的數據結構，例如二叉樹、廣義表、圖等，這些問題的求解一般是以樹的遍歷為基礎，在遍歷的基礎上綜合求出問題的解。在此，我們采用三種遍歷樹的方法實現對復雜遞歸類問題的劃分：前序，中序，后序。

前序：

Oper(Q(T))=Oper(t◇Q(T.I)◇Q(T.r))

中序：

Oper(Q(T))=Oper(Q(T.I)◇t◇Q(T.r))

后序：

Oper(Q(T))=Oper(Q(T)◇Q(T.r)◇t)

其中T表示要進行操作的數據(二叉樹、數組、圖)，Oper表示對原數據結構進行變換的操作，為可選項。當選擇Oper項，則Q(T)表示為allnodes(T)，它表示T中所有元素或標識構成