遞歸是一個神奇的算法，它是編程書籍中講解的最尷尬部分。這些書籍通常會展示一個遞歸的階乘實(shí)現(xiàn)，然后警告你，雖然它能運(yùn)行但是它非常的慢并且可能會堆棧溢出而崩潰。雖然大家對它持懷疑態(tài)度，但是這不影響遞歸是算法中最強(qiáng)大的想法。

讓我們來看看經(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)用開始和返回之前的這些棧幀累積是可能耗盡?？臻g并使程序崩潰。

但是這些擔(dān)憂通常是理論上的。例如，棧幀 factorial每個占用16個字節(jié)(這可以根據(jù)棧對齊和其他因素而變化)。如果您在計(jì)算機(jī)上運(yùn)行現(xiàn)代x86 Linux內(nèi)核，通常默認(rèn)有8兆字節(jié)的堆?？臻g，因此factorial n最多可以處理512,000。這是一個巨大數(shù)，需要8,971,833位來表示這個數(shù)，所以?？臻g是我們問題中最少的：一個微弱的整數(shù) - 甚至是64位 - 在我們用完?？臻g之前會溢出數(shù)萬次。

我們稍后會看一下CPU的使用情況，但是現(xiàn)在讓我們從位和字節(jié)中退一步，看看遞歸作為一種通用技術(shù)。我們的階乘算法歸結(jié)為將整數(shù)N，N-1，... 1推入堆棧，然后以相反的順序?qū)⑺鼈兿喑?。我們使用程序的調(diào)用堆棧執(zhí)行此操作的前提是：我們可以在堆上分配堆棧并使用它。雖然調(diào)用堆棧確實(shí)具有特殊屬性，但它只是您可以使用的另一種數(shù)據(jù)結(jié)構(gòu)。

一旦你看到調(diào)用堆棧作為一個數(shù)據(jù)結(jié)構(gòu)，其他東西就變得豁然開朗了：將本身之前所有這些整數(shù)累加起來再乘以自身這顯然不是明智的選擇。 使用迭代過程計(jì)算階乘更為明智。

有一個傳統(tǒng)的面試問題，在迷宮中放一只老鼠，你幫助老鼠找奶酪，假設(shè)老鼠可以在迷宮中向左或向右轉(zhuǎn)。你會如何建模并解決這個問題?

像生活中的大多數(shù)問題一樣，你可以將這種嚙齒動物的任務(wù)抽象到一個圖形，特別是一個二叉樹，其中節(jié)點(diǎn)代表迷宮中的位置。然后你可以盡可能地讓老鼠左轉(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)的下一步行動?；蛘吣憧梢苑峙淦渌兞縼碛涗浤汤覍ふ业臓顟B(tài)。你仍然在實(shí)現(xiàn)遞歸過程，但滾動你自己的數(shù)據(jù)結(jié)構(gòu)。

這可能會更復(fù)雜，因?yàn)檎{(diào)用堆棧就像手套一樣。每個堆棧幀不僅記錄當(dāng)前節(jié)點(diǎn)，還記錄該節(jié)點(diǎn)中的計(jì)算狀態(tài)(在這種情況下，我們是僅采用左側(cè)還是已經(jīng)嘗試右側(cè))。然而，我們有時會因?yàn)楹ε乱绯龆艞壛嗣篮玫臇|西。在我看來是非常愚蠢的。

正如我們所看到的，棧很大，并且在棧空間之前經(jīng)常會遇到其他約束。還可以檢查問題的大小并確保可以安全地處理。CPU擔(dān)心主要是由兩個廣泛的病理學(xué)例子灌輸：愚蠢的因子和可靠的O(2 n) 遞歸Fibonacci沒有記憶。這些并不表示理智的堆棧遞歸算法。

現(xiàn)實(shí)情況是棧操作很快。數(shù)據(jù)的偏移是準(zhǔn)確的，棧在緩存中，不需要冷啟動，并且有專門的指令來完成工作。同時，使用您自己的堆分配數(shù)據(jù)結(jié)構(gòu)會產(chǎn)生大量開銷。會看到其他人編寫的東西比調(diào)用堆棧遞歸更復(fù)雜，性能更差。

現(xiàn)代CPU 非常優(yōu)秀了，通常不是瓶頸。簡單往往和性能等同。