基于遞歸程序到非遞歸程序轉(zhuǎn)換的實(shí)現(xiàn)

洪　莉

摘要：基于遞歸程序時(shí)空性能不好的缺點(diǎn)，提出了用非遞歸方法來解決遞歸問題的實(shí)現(xiàn)方法。

關(guān)鍵詞：遞歸程序棧

遞歸技術(shù)是許多軟件設(shè)計(jì)人員常用的方法，但在實(shí)際應(yīng)用時(shí)，也存在一些問題，主要表現(xiàn)在以下兩個(gè)方面：

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

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

1用循環(huán)法消除遞歸

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

借助于棧將遞歸程序轉(zhuǎn)換為非遞歸程序很方便，尤其是要想將有些復(fù)雜的遞歸程序轉(zhuǎn)換為非遞歸程序，如果不借助于棧，只用簡單的循環(huán)方法是很難實(shí)現(xiàn)的?；跅５姆椒?，可以將任何一個(gè)遞歸問題對應(yīng)的程序轉(zhuǎn)換為一個(gè)非遞歸程序。

3結(jié)束語

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