為什麼說遞歸效率低？
我在做java後端載入一個樹形結構時，由於不確定樹形結構是多少層，所以就想到了使用遞歸載入，但是今天看見了一本書，說遞歸效率低，我現在有如下疑問：
1、遞歸為何效率低？我在這個邏輯中感覺並沒有什麼資源上的浪費，每一步都進行了有意義的運算。2、有沒有在此種情形下能代替遞歸的更高效的方法。
之前做 RapidJSON 時，解釋器用遞歸下降方式，由於沒有限定層數，有機會做極深的 JSON 請求來引發 stack overflow（如 "[[[[[...]]]]]" 一百萬層），產生安全性及穩定性問題。
之後同事再寫多了一個版本，就是自行實現 stack （所謂的用迭代取代遞歸），只要有足夠的 heap 就不會有問題。當然，在這個個例上，也可以簡單地限制層數來解決。
遞歸的額外耗時決於函數調用的成本，這成本與具體平台相關。
許多時候，可以尾調用的遞歸還不如顯式寫作迭代。不可以尾調用的遞歸，要換作迭代方式就需要自建 stack，較為複雜，但有可能降低時間和空間的係數，並且能支持更大的深度。遞歸效率低是函數調用的開銷導致的。在一個函數調用之前需要做許多工作，比如準備函數內局部變數使用的空間、搞定函數的參數等等，這些事情每次調用函數都需要做，因此會產生額外開銷導致遞歸效率偏低，所以邏輯上開銷一致時遞歸的額外開銷會多一些當然了，通過有意識的組織代碼的寫法可以把某些遞歸寫成尾遞歸，尾遞歸可以進行特殊的優化所以效率會比普通的遞歸高一些，也不會因為遞歸太多導致棧溢出遍歷樹還不用遞歸的話，那麼人肉寫一個棧+深度優先遍歷或者人肉隊列+廣度優先遍歷，再輔以黑魔法給棧或者隊列提速，應該會比遞歸快一些，加速幅度和語言和寫法相關，但在大多數情況下我覺得是得不償失的，花了很大精力很可能效率提升不明顯
說「遞歸效率低」，首先就是這個說法很不負責任。
遞歸，是，函數調用函數時，表現出來的一種形式，說它效率低，好比說，一個函數調用了另一個函數效率低，這樣有點不知所云。有其他的答案，提到了，函數調用的成本，確實，在 c++ 中，和一段連續的過程化的代碼相比，函數調用是存在成本的（調用和返回時都需要跳轉，會影響 cpu 的流水線效率），所以 c++ 有對編譯器的建議性的關鍵字，對一些簡單的函數內聯（inline），也就是把函數就地展開，省去函數調用成本（比如說如果對類的成員 get，set 寫在 .h 文件中，這些很小的 get, set 函數通常被內聯）。這些是 c++ 對運行時效率精益求精，錙銖必較的嚴謹態度的體現。
像樓主用 java，或者 c# 這一類，沒有把運行時效率放在首位，而是把程序員的開發效率，和盡量降低人的粗心（這是人的本性）因素對編程的干擾，這種語言中，談效率時，主要是說演算法，而不會覆蓋到函數調用成本這種層面來。
對於遞歸，有人提到了兩點：
（1）對棧的容量的壓力。（2）個別問題的遞歸解法，其演算法的低效性。這兩個因素我簡短點評下，
（1）對棧的容量壓力：
通常遞歸的深度很大造成的。對於這一點當然應該有程序員編碼時，來衡量和把握。win32 中一個新建的線程，默認的棧通常在 1 MB 大小。那麼如果你的遞歸函數，深度很大，顯然程序員應該對這種情況有預估，和對風險的避免。
這就和你選擇，把內存分配在棧上還是堆上，會考慮到分配的內存大小的因素一樣。
當然，如果在函數內分配很大的棧上空間，在函數體內定義一個很大的數組，這樣不需要很深的深度，也會讓棧溢出。這當然也是程序員自己應該控制的。
（2）個別問題的遞歸解法，演算法的低效。
這個低效主要在於這個問題的演算法本身。而不是在遞歸這種方法上。比如說求斐波那契的某一項，子問題會大量重複出現，會產生很多重複計算，這個是很多演算法書上，是用來引導出動態規劃或者查表法的。
這主要是演算法本身的效率問題，而不是遞歸的問題。這一點是必須應該明確的。
（3）我們可以看到，在和樹有關的演算法中，經常會有遞歸函數。
例如，遍歷文件夾，刪除註冊表的某一個 key （及其所有子key）。
尤其對一般樹的前序，後序遍歷，二叉樹的中序遍歷。這主要原因是因為樹的定義，就是「遞歸性」的：
樹就是，某一個節點有多個子節點，每個子節點是一個樹。
我們再此可以看到，遞歸的顯著優點，是對解的描述的直觀性，代碼的簡潔性。
樓主就是在和樹有關的問題中，採用了 java 或者 c# ，或者 c++ 等編程語言，寫出對應的遞歸方法，
從可預見的情況看，其完全不需要考慮（1）和（2）。也就是即不會產生可觀的對棧容量的壓力，也不會有演算法上的明顯低效部分。那麼當然這種情況下，是可以很安心很放心的使用遞歸的。
比如說，提供一個根節點，我們釋放一個二叉樹，大概的代碼是什麼樣的呢：
void FreeTree(NODE* p)
{
if(p != NULL) {
FreeTree(p-&>leftChild);
FreeTree(p-&>rightChild);
free(p);
}
}
當然，你也可以寫一個非遞歸版本，自己在 heap 上分配一段內存來作為輔助 stack。那麼
第一，對內存成本的轉移，由於棧的成本是固定的，所以對於實際問題來說，非遞歸版本增加了內存成本。
第二，對於一個小規模的樹，兩者時間成本，我覺得恐怕微乎其微到沒有差異的程度，可能是一般測量方法無法分辨的。
注意：在內存中創建一個完整的樹（比如說滿二叉樹），這個樹的規模不能太大。因為樹對內存的需求對於樹深度來說，增長速度是指數級的。（比如說在 ACM 中這種做法，可能會導致內存使用超出限制）。
第三，編寫一個非遞歸版本的函數，開發成本顯然會更高。先把遞歸的寫出來再說。
排除演算法設計本身的因素，遞歸帶來的效率問題主要是函數調用帶來的額外開銷（函數的入棧出棧），以及棧容量的限制（次數太多可能會stack overflow）
有的程序語言的遞歸會重複運算 參數值相同 返回值相同的函數，
不過用空間換時間，可以把 參數值相同 的返回結果先存起來，但這又增加了點程序的複雜性。
尾遞歸沒有這個問題，尾遞歸的思路和循環基本一樣，在有的語言會把尾遞歸轉換成循環。應該是怎麼方便怎麼寫，遞歸寫得正確最多比循環慢一倍（重複運算就是指數級的了），又不是指數級別的差距，多數情況下不用關心。1.不是所有人都能寫出正確的遞歸。2.遞歸的原理就是相同函數的不斷入棧出棧，這都是有時間損耗的。
遞歸很多時候效率低是因為演算法設計得不合理，每次遞歸調用有重複計算的數據存在。並且現代編譯器很多時候會做內聯優化，編譯完了之後就是一個函數。
遞歸的調試難度奇高，就決定了實際項目中很少用遞歸。而且遞歸確實運行效率低，因為函數一層一層調用存在調用棧，在切換到更深層的函數時要產生斷點，為了保證回來時繼續運行，必須保存現在所處函數的各種狀態，回來時恢復狀態，這樣一層層下去性能損失就不斷增加。
用我在新浪博客的文章回答這個問題吧。首先說明遞歸的低效，然後說明了一種尾遞歸的方法提高效率。
文章是結合兩篇別人的文章而來，不喜勿噴。
說到遞歸，大家一定會聯繫到迭代，這裡就一起分析下吧。。
1.所謂的遞歸慢到底是什麼原因呢？
大家都知道遞歸的實現是通過調用函數本身，函數調用的時候，每次調用時要做地址保存，參數傳遞等，這是通過一個遞歸工作棧實現的。具體是每次調用函數本身要保存的內容包括：局部變數、形參、調用函數地址、返回值。那麼，如果遞歸調用N次，就要分配N*局部變數、N*形參、N*調用函數地址、N*返回值。這勢必是影響效率的。
2.用循環效率會比遞歸效率高嗎？
遞歸與循環是兩種不同的解決問題的典型思路。當然也並不是說循環效率就一定比遞歸高，遞歸和循環是兩碼事，遞歸帶有棧操作，循環則不一定，兩個概念不是一個層次，不同場景做不同的嘗試。
2.1遞歸演算法：
優點：代碼簡潔、清晰，並且容易驗證正確性。（如果你真的理解了演算法的話，否則你更暈）
缺點：它的運行需要較多次數的函數調用，如果調用層數比較深，需要增加額外的堆棧處理（還有可能出現堆棧溢出的情況），比如參數傳遞需要壓棧等操作，會對執行效率有一定影響。但是，對於某些問題，如果不使用遞歸，那將是極端難看的代碼。
2.2循環演算法：
優點：速度快，結構簡單。
缺點：並不能解決所有的問題。有的問題適合使用遞歸而不是循環。如果使用循環並不困難的話，最好使用循環。
2.3遞歸演算法和循環演算法總結：
1.一般遞歸調用可以處理的演算法，也通過循環去解決常需要額外的低效處理。
2.現在的編譯器在優化後，對於多次調用的函數處理會有非常好的效率優化，效率未必低於循環。
3.遞歸和循環兩者完全可以互換。如果用到遞歸的地方可以很方便使用循環替換，而不影響程序的閱讀，那麼替換成遞歸往往是好的。（例如：求階乘的遞歸實現與循環實現。）
3.那麼遞歸使用的棧是什麼樣的一個棧呢？
首先，看一下系統棧和用戶棧的用途。
3.1系統棧（也叫核心棧、內核棧）是內存中屬於操作系統空間的一塊區域，其主要用途為：(1)保存中斷現場，對於嵌套中斷，被中斷程序的現場信息依次壓入系統棧，中斷返回時逆序彈出；(2)保存操作系統子程序間相互調用的參數、返回值、返回點以及子程序(函數)的局部變數。
3.2用戶棧是用戶進程空間中的一塊區域，用於保存用戶進程的子程序間相互調用的參數、返回值、返回點以及子程序(函數)的局部變數。
我們編寫的遞歸程序屬於用戶程序，因此使用的是用戶棧。
那麼遞歸就不能在代碼簡潔的好處，同時給我們帶來更快的速率么？真是不科學。科學往往會告訴你，一切皆有可能。
尾遞歸應運而生了。。
我們讓遞歸和尾遞歸來做一個對比。
1、遞歸
用線性遞歸實現Fibonacci函數，程序如下所示：
int FibonacciRecursive(int n) {if( n &< 2)return n;return (FibonacciRecursive(n-1)+FibonacciRecursive(n-2)); }遞歸寫的代碼非常容易懂，完全是根據函數的條件進行選擇計算機步驟。例如現在要計算n=5時的值，遞歸調用過程如下圖所示：2、尾遞歸
顧名思義，尾遞歸就是從最後開始計算,每遞歸一次就算出相應的結果, 也就是說, 函數調用出現在調用者函數的尾部, 因為是尾部,所以根本沒有必要去保存任何局部變數.直接讓被調用的函數返回時越過調用者, 返回到調用者的調用者去。尾遞歸就是把當前的運算結果（或路徑）放在參數里傳給下層函數，深層函數所面對的不是越來越簡單的問題，而是越來越複雜的問題，因為參數裡帶有前面若干步的運算路徑。
尾遞歸是極其重要的，不用尾遞歸，函數的堆棧耗用難以估量，需要保存很多中間函數的堆棧。比如f(n, sum) = f(n-1) + value(n) + sum; 會保存n個函數調用堆棧，而使用尾遞歸f(n, sum) = f(n-1, sum+value(n)); 這樣則只保留後一個函數堆棧即可，之前的可優化刪去。
採用尾遞歸實現Fibonacci函數，程序如下所示：
int FibonacciTailRecursive(int n,int ret1,int ret2) {if(n==0)return ret1; return FibonacciTailRecursive(n-1,ret2,ret1+ret2); }例如現在要計算n=5時的值，尾遞歸調用過程如下圖所示：從圖可以看出，為遞歸不需要向上返回了，但是需要引入而外的兩個空間來保持當前的結果。遞歸效率低是相對於迭代來說的，因為遞歸不是圖靈機的原生程序結構，迭代基本可以算是。（迭代是遞歸在有限狀態機裡面的等價形式）第二個問題就是遞歸層次多的話，可能會爆棧，雖然有些遞歸演算法可以寫成尾調用的形式避免爆棧。
拖延症有兩種，一種是deadlock，還有一種就是頭遞歸。
－－－－－－－－－9月5日更新－－－－－－－－－－－－
請暫時忽視我的答案 說法並不準確我查查資料 有時間再訂正...－－－－－－－－－－－－－－－－－－－－－－－－－－不是遞歸效率低
是C＋＋這些主流編程語言里 有一個叫「內存管理」的東西遞歸時主要用的是「棧內存」「棧內存」存在於棧區（stack） 效率 要低於 堆內存 和 靜態內存並且大小有限制超過限制就會棧溢出 即 stackoverflow 新手最常犯的錯誤 目前最主流的程序員問題網站得名的原因－－－－－－－－－－－－9月4號更新－－－－－－－－－－－－－－－－－－被評論提問 今天複習了一下 發現自己的說法不準確其實 棧內存 的 效率是要比 堆內存 高的我居然一直誤解了...遞歸效率慢 是因為
1. 大量開闢在棧區的內存 直到每一層的遞歸結束或整個遞歸結束才釋放 且這個內存空間可能呈幾何級數增加 空間效率不佳2. 遞歸頻繁進行調用函數的操作 而每次函數在底層上 都有 傳遞行參 調用函數指針 等等操作 頻繁的操作會降低效率 時間效率不佳3. 在完成每一層的遞歸時會有大量的 壓棧出棧 操作 即 釋放無用棧區空間開闢新的棧區空間 類似於new／delete 這樣頻繁的內存操作 會極大影響效率 時間效率不佳綜上 可以說 遞歸效率不佳是因為內存分配在棧區但其實不是因為棧內存效率低這主要是因為計算機程序的函數調用機制，在函數進行調用時，會把所有的參數進行壓棧（儲存在「棧」內），直到返回時才把參數彈出，而「棧」實際上是真實存在於計算機內存當中的一段存儲空間。試想，如果你的函數調用了一百萬次自己才達到base condition準備返回，那內存是不是就要溢出了？這也就是為什麼有時即使代碼沒有邏輯上的錯誤，依然會在運行的時候報出「stack overflow」的錯誤啦。另外，調用函數也是要花時間的，所以通常情況下循環結構會比遞歸結構運行速度要快一些。
遞歸就是棧，用得好就不低
開發效率VS運行效率場景下自己找tradeoff咯。非遞歸大部分就是自己模擬棧。
很多人的誤區，當我們說遞歸效率低的時候，潛在的思維是，是將 用計算機遞歸調用方法的實現，和遞歸優化後的程序(最簡單如尾遞歸優化)作比較的。所以要搞清楚這裡的比較對象。遞歸是一種思維方法，慢的是遞歸的各種實現。至於程序或編譯器或系統對遞歸優化，相信這裡會有更好的回答。
因為遞歸相比於普通循環來說，多了函數調用開銷。遞歸發生函數調用時，返回地址和正在調用的函數的所有局部變數的值以及形式參數的值會被保存到環境棧中。這個過程涉及的壓棧出棧操作都是花費時間的，完成同一件事情，增大了時間開銷，那麼其效率自然會降低。
對性能部分不是很了解，我也是遞歸構造了tree結構，寫個介面給前台用，，一般都是做許可權菜單用的東西，菜單不會超過多少的，300個菜單，最深的是三層，測試了一下，花費了438ms，用的fastjson,還給菜單排序了，我感覺花費時間還算可以吧。
我覺得不能光看函數調用的次數問題，我們知道棧的性能是優於堆的(堆的分配必須通過一定演算法獲得，這方面會浪費時間)，棧的分配只是簡單的指針移動，再說反覆調用相同的代碼CPU也會有緩存機制，如果不考慮空間因素，棧是一種很好的演算法，但是很多問題只能重複的調用函數來解決，如果問題的規模不確定，你不用遞歸用什麼，很多時候我們覺得中間數據大部分使用堆內存，其實這是錯誤的，只有很少一部分數據才會變動，所以棧太小是系統的問題。舉個例子，漢諾塔問題的根源就是空間不夠如果有8根柱子，會計算這麼久嗎？如果我們設計方案的時候百分之八十的空間都能估計到，為什麼要用百分之八十的精力浪費在堆的分配上面，說這麼多我看來是不適合解決問題，反而善於推翻問題，一個方法或者函數是處理數據到數據的映射關係，我覺得可以不產生中間數據就盡量不產生，可以用棧就不要用堆，或者一個棧不夠了我們可以用堆再生成一個，彙編中可能要改堆棧段的地址，C解決不了，函數式編程也許是這樣做的吧，我急需關於函數編程的內存處理，有沒得這方面研究得透徹的指導指導
推薦閱讀：
※從N個數組中找出出現最多的前K個數？
※為什麼Windows系統自帶的記事本(notepad.exe)程序打開大文件這麼慢？
※堆排序缺點何在？
※有沒有什麼演算法可以確定兩圖是否同構？
※N個數最少比較多少次才能保證知道大小順序?