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