深入理解遞歸，是你誤解了遞歸
遞歸是一個神奇的算法，它是編程書籍中講解的最尷尬部分。這些書籍通常會展示一個遞歸的階乘實現(xiàn)，然后警告你，雖然它能運行但是它非常的慢并且可能會堆棧溢出而崩潰。雖然大家對它持懷疑態(tài)度，但是這不影響遞歸是算法中最強大的想法。
讓我們來看看經(jīng)典的遞歸階乘：
factorial.c
- #include <stdio.h>
- int factorial(int n)
- {
- int previous = 0xdeadbeef;
- if (n == 0 || n == 1) {
- return 1;
- }
- previous = factorial(n-1);
- return n * previous;
- }
- int main(int argc)
- {
- int answer = factorial(5);
- printf("%d\n", answer);
- }
一個函數(shù)調(diào)用自身的想法起初非常神秘。為了解釋整個過程，下圖展示了factorial(5)被調(diào)用到n == 1 棧上結(jié)構(gòu)。
每次調(diào)用factorial都會生成一個新的棧幀。這些棧幀的創(chuàng)建和銷毀使得遞歸因子比其迭代部分慢。在調(diào)用開始和返回之前的這些棧幀累積是可能耗盡棧空間并使程序崩潰。
但是這些擔(dān)憂通常是理論上的。例如，棧幀 factorial每個占用16個字節(jié)(這可以根據(jù)棧對齊和其他因素而變化)。如果您在計算機(jī)上運行現(xiàn)代x86 Linux內(nèi)核，通常默認(rèn)有8兆字節(jié)的堆棧空間，因此factorial n最多可以處理512,000。這是一個巨大數(shù)，需要8,971,833位來表示這個數(shù)，所以棧空間是我們問題中最少的：一個微弱的整數(shù) - 甚至是64位 - 在我們用完棧空間之前會溢出數(shù)萬次。
我們稍后會看一下CPU的使用情況，但是現(xiàn)在讓我們從位和字節(jié)中退一步，看看遞歸作為一種通用技術(shù)。我們的階乘算法歸結(jié)為將整數(shù)N，N-1，... 1推入堆棧，然后以相反的順序?qū)⑺鼈兿喑恕Ｎ覀兪褂贸绦虻恼{(diào)用堆棧執(zhí)行此操作的前提是：我們可以在堆上分配堆棧并使用它。雖然調(diào)用堆棧確實具有特殊屬性，但它只是您可以使用的另一種數(shù)據(jù)結(jié)構(gòu)。
一旦你看到調(diào)用堆棧作為一個數(shù)據(jù)結(jié)構(gòu)，其他東西就變得豁然開朗了：將本身之前所有這些整數(shù)累加起來再乘以自身這顯然不是明智的選擇。 使用迭代過程計算階乘更為明智。
有一個傳統(tǒng)的面試問題，在迷宮中放一只老鼠，你幫助老鼠找奶酪，假設(shè)老鼠可以在迷宮中向左或向右轉(zhuǎn)。你會如何建模并解決這個問題?
像生活中的大多數(shù)問題一樣，你可以將這種嚙齒動物的任務(wù)抽象到一個圖形，特別是一個二叉樹，其中節(jié)點代表迷宮中的位置。然后你可以盡可能地讓老鼠左轉(zhuǎn)，當(dāng)它到達(dá)死胡同時回溯然后右轉(zhuǎn)。下圖就是老鼠路徑 ：
每條邊(線)都可以左轉(zhuǎn)或右轉(zhuǎn)，老鼠可以選擇。如果任一轉(zhuǎn)彎被阻止，則相應(yīng)的邊緣不存在。無論您使用調(diào)用堆棧還是其他數(shù)據(jù)結(jié)構(gòu)，此過程本質(zhì)上都是遞歸的。但使用調(diào)用棧非常簡單：
Maze.c
- #include <stdio.h>
- #include "maze.h"
- int explore(maze_t *node)
- {
- int found = 0;
- if (node == NULL) {
- return 0;
- }
- if (node->hasCheese) {
- return 1; // found cheese
- }
- found = explore(node->left) || explore(node->right);
- return found;
- }
- int main(int argc)
- {
- int found = explore(&maze);
- }
在maze.c:13中找到奶酪，下圖是堆棧。
雖然這里很難擺脫遞歸，但這并不意味著它必須通過調(diào)用棧來完成。例如，你可以使用一個字符串 RRLL來跟蹤轉(zhuǎn)彎，并依靠字符串來決定鼠標(biāo)的下一步行動。或者你可以分配其他變量來記錄奶酪尋找的狀態(tài)。你仍然在實現(xiàn)遞歸過程，但滾動你自己的數(shù)據(jù)結(jié)構(gòu)。
這可能會更復(fù)雜，因為調(diào)用堆棧就像手套一樣。每個堆棧幀不僅記錄當(dāng)前節(jié)點，還記錄該節(jié)點中的計算狀態(tài)(在這種情況下，我們是僅采用左側(cè)還是已經(jīng)嘗試右側(cè))。然而，我們有時會因為害怕溢出而放棄了美好的東西。在我看來是非常愚蠢的。
正如我們所看到的，棧很大，并且在棧空間之前經(jīng)常會遇到其他約束。還可以檢查問題的大小并確保可以安全地處理。CPU擔(dān)心主要是由兩個廣泛的病理學(xué)例子灌輸：愚蠢的因子和可靠的O(2 n) 遞歸Fibonacci沒有記憶。這些并不表示理智的堆棧遞歸算法。
現(xiàn)實情況是棧操作很快。數(shù)據(jù)的偏移是準(zhǔn)確的，棧在緩存中，不需要冷啟動，并且有專門的指令來完成工作。同時，使用您自己的堆分配數(shù)據(jù)結(jié)構(gòu)會產(chǎn)生大量開銷。會看到其他人編寫的東西比調(diào)用堆棧遞歸更復(fù)雜，性能更差。
現(xiàn)代CPU 非常優(yōu)秀了，通常不是瓶頸。簡單往往和性能等同。
