漫談遞歸：遞歸與循環(huán)

herowuking 2015-10-10

展開全文

所謂的遞歸慢到底是什么原因呢？

前面一篇講到了遞歸的效率問題，但是沒具體深入到數(shù)據(jù)結(jié)構(gòu)層面的解釋，這里補充一下。

大家都知道遞歸的實現(xiàn)是通過調(diào)用函數(shù)本身，函數(shù)調(diào)用的時候，每次調(diào)用時要做地址保存，參數(shù)傳遞等，這是通過一個遞歸工作棧實現(xiàn)的。具體是每次調(diào)用函數(shù)本身要保存的內(nèi)容包括：局部變量、形參、調(diào)用函數(shù)地址、返回值。那么，如果遞歸調(diào)用N次，就要分配N*局部變量、N*形參、N*調(diào)用函數(shù)地址、N*返回值。這勢必是影響效率的。

遞歸是利用系統(tǒng)的堆棧保存函數(shù)當(dāng)中的局部變量來解決問題的。遞歸說白了就是在棧處理棧上一堆的指針指向內(nèi)存中的對象，這些對象一直不被釋放，直到遞歸執(zhí)行到最后一次跳出條件的時候，才一個個出棧。所以開銷很大。

用循環(huán)效率會比遞歸效率高嗎？

遞歸與循環(huán)是兩種不同的解決問題的典型思路。當(dāng)然也并不是說循環(huán)效率就一定比遞歸高，遞歸和循環(huán)是兩碼事，遞歸帶有棧操作，循環(huán)則不一定，兩個概念不是一個層次，不同場景做不同的嘗試。

1. 遞歸算法：

優(yōu)點：代碼簡潔、清晰，并且容易驗證正確性。（如果你真的理解了算法的話，否則你更暈）
缺點：它的運行需要較多次數(shù)的函數(shù)調(diào)用，如果調(diào)用層數(shù)比較深，需要增加額外的堆棧處理（還有可能出現(xiàn)堆棧溢出的情況），比如參數(shù)傳遞需要壓棧等操作，會對執(zhí)行效率有一定影響。但是，對于某些問題，如果不使用遞歸，那將是極端難看的代碼。

2. 循環(huán)算法：

優(yōu)點：速度快，結(jié)構(gòu)簡單。
缺點：并不能解決所有的問題。有的問題適合使用遞歸而不是循環(huán)。如果使用循環(huán)并不困難的話，最好使用循環(huán)。

3. 遞歸算法和循環(huán)算法總結(jié)：

遞歸通常很直白地描述了一個求解過程，因此也是最容易被想到和實現(xiàn)的算法。循環(huán)其實和遞歸具有相同的特性（即：做重復(fù)任務(wù)），但有時，使用循環(huán)的算法并不會那么清晰地描述解決問題步驟。單從算法設(shè)計上看，遞歸和循環(huán)并無優(yōu)劣之別。然而，在實際開發(fā)中，因為函數(shù)調(diào)用的開銷，遞歸常常會帶來性能問題，特別是在求解規(guī)模不確定的情況下。而循環(huán)因為沒有函數(shù)調(diào)用開銷，所以效率會比遞歸高。除少數(shù)編程語言對遞歸進行了優(yōu)化外，大部分語言在實現(xiàn)遞歸算法時還是十分笨拙，由此帶來了如何將遞歸算法轉(zhuǎn)換為循環(huán)算法的問題。算法轉(zhuǎn)換應(yīng)當(dāng)建立在對求解過程充分理解的基礎(chǔ)上，有時甚至需要另辟蹊徑。

一般遞歸調(diào)用可以處理的算法，也通過循環(huán)去解決需要額外的低效處理。
現(xiàn)在的編譯器在優(yōu)化后，對于多次調(diào)用的函數(shù)處理會有非常好的效率優(yōu)化，效率未必低于循環(huán)。
遞歸和循環(huán)兩者完全可以互換。如果用到遞歸的地方可以很方便使用循環(huán)替換，而不影響程序的閱讀，那么替換成遞歸往往是好的。（例如：求階乘的遞歸實現(xiàn)與循環(huán)實現(xiàn)。）

要轉(zhuǎn)換成為非遞歸，兩步工作：