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

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

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

0 引言

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

在程序設計中，程序的可讀性與程序的執行效率往往是互相制約的。遞歸算法只需要寫出問題的分解形式和組合答案的方法，至于如何遞歸地求解各個子問題則由系統幫助解決；而遞推算法常以循環的形式出現，編寫程序時必須明確寫出循環內的每一步是如何實現的。……