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

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

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

遞歸是利用系統(tǒng)的堆棧保存函數(shù)當(dāng)中的局部變量來解決問題的。遞歸說白了就是在棧處理?xiàng)Ｉ弦欢训闹羔樦赶騼?nèi)存中的對(duì)象，這些對(duì)象一直不被釋放，直到遞歸執(zhí)行到最后一次跳出條件的時(shí)候，才一個(gè)個(gè)出棧。所以開銷很大。

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

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

1. 遞歸算法：

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

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

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

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

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

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

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

1. 第一步，可以自己建立一個(gè)堆棧保存這些局部變量，替換系統(tǒng)棧；
2. 第二步把對(duì)遞歸的調(diào)用轉(zhuǎn)變?yōu)檠h(huán)處理就可以了。

那么遞歸使用的棧是什么樣的一個(gè)棧呢？

首先，看一下系統(tǒng)棧和用戶棧的用途。

1. 系統(tǒng)棧（也叫核心棧、內(nèi)核棧）是內(nèi)存中屬于操作系統(tǒng)空間的一塊區(qū)域，其主要用途為：
• 保存中斷現(xiàn)場(chǎng)，對(duì)于嵌套中斷，被中斷程序的現(xiàn)場(chǎng)信息依次壓入系統(tǒng)棧，中斷返回時(shí)逆序彈出；
• 保存操作系統(tǒng)子程序間相互調(diào)用的參數(shù)、返回值、返回點(diǎn)以及子程序(函數(shù))的局部變量。
2. 用戶棧是用戶進(jìn)程空間中的一塊區(qū)域，用于保存用戶進(jìn)程的子程序間相互調(diào)用的參數(shù)、返回值、返回點(diǎn)以及子程序(函數(shù))的局部變量。

我們編寫的遞歸程序?qū)儆谟脩舫绦颍虼耸褂玫氖怯脩魲！?/p>