基于遞歸程序到非遞歸程序轉換的實現

洪　莉

摘要：基于遞歸程序時空性能不好的缺點，提出了用非遞歸方法來解決遞歸問題的實現方法。

關鍵詞：遞歸程序棧

遞歸技術是許多軟件設計人員常用的方法，但在實際應用時，也存在一些問題，主要表現在以下兩個方面：

(1)程序設計語言對遞歸的支持方面的限制。較典型的是FORTRAN語言，它明確規定不允許直接或間接遞歸。還有一些語言雖然可以使用遞歸，但由于沒有較好的內部支持機制，因而在這方面的性能不太好，編程太麻煩，且所編程序可讀性差；(2)程序運行的時間性能方面。對同一問題的求解程序，遞歸程序比非遞歸程序要花費更多的時間。

鑒于上述問題，在許多情況下，要求能寫出求解問題的非遞歸程序。由于許多復雜問題的求解程序的遞歸程序比非遞歸程序要容易設計，因此，常常是先設計出遞歸程序，然后再將其轉換為等價的非遞歸程序。轉換的方法有兩種。

1用循環法消除遞歸

循環法是利用“依賴圖”進行分析和化簡的。下面通過例子來說明遞歸程序向非遞歸程序的轉化過程。求n!的遞歸程序：

借助于棧將遞歸程序轉換為非遞歸程序很方便，尤其是要想將有些復雜的遞歸程序轉換為非遞歸程序，如果不借助于棧，只用簡單的循環方法是很難實現的。基于棧的方法，可以將任何一個遞歸問題對應的程序轉換為一個非遞歸程序。

3結束語

遞歸程序簡單、清晰、可讀性好，且易于驗證其正確性，但浪費空間且執行效率低，因此，有時需要把遞歸程序轉換成非遞歸程序，這種轉化帶來的優點有，第一，有利于提高算法的時空性能：第二，有助于深刻理解遞歸機制，而這種理解是熟練掌握遞歸程序設計的必要前提。