算法 | 深入理解遞歸，是你誤解了遞歸
遞歸是一個(gè)神奇的算法，它是編程書籍中講解的最尷尬部分。這些書籍通常會展示一個(gè)遞歸的階乘實(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);
- }
一個(gè)函數(shù)調(diào)用自身的想法起初非常神秘。為了解釋整個(gè)過程，下圖展示了factorial(5)被調(diào)用到n == 1 棧上結(jié)構(gòu)。
每次調(diào)用factorial都會生成一個(gè)新的棧幀。這些棧幀的創(chuàng)建和銷毀使得遞歸因子比其迭代部分慢。在調(diào)用開始和返回之前的這些棧幀累積是可能耗盡?？臻g并使程序崩潰。
但是這些擔(dān)憂通常是理論上的。例如，棧幀 factorial每個(gè)占用16個(gè)字節(jié)(這可以根據(jù)棧對齊和其他因素而變化)。如果您在計(jì)算機(jī)上運(yùn)行現(xiàn)代x86 Linux內(nèi)核，通常默認(rèn)有8兆字節(jié)的堆?？臻g，因此factorial n最多可以處理512,000。這是一個(gè)巨大數(shù)，需要8,971,833位來表示這個(gè)數(shù)，所以?？臻g是我們問題中最少的：一個(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)用堆棧作為一個(gè)數(shù)據(jù)結(jié)構(gòu)，其他東西就變得豁然開朗了：將本身之前所有這些整數(shù)累加起來再乘以自身這顯然不是明智的選擇。 使用迭代過程計(jì)算階乘更為明智。
有一個(gè)傳統(tǒng)的面試問題，在迷宮中放一只老鼠，你幫助老鼠找奶酪，假設(shè)老鼠可以在迷宮中向左或向右轉(zhuǎn)。你會如何建模并解決這個(gè)問題?
像生活中的大多數(shù)問題一樣，你可以將這種嚙齒動物的任務(wù)抽象到一個(gè)圖形，特別是一個(gè)二叉樹，其中節(jié)點(diǎn)代表迷宮中的位置。然后你可以盡可能地讓老鼠左轉(zhuǎn)，當(dāng)它到達(dá)死胡同時(shí)回溯然后右轉(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)用棧來完成。例如，你可以使用一個(gè)字符串 RRLL來跟蹤轉(zhuǎn)彎，并依靠字符串來決定鼠標(biāo)的下一步行動?；蛘吣憧梢苑峙淦渌兞縼碛涗浤汤覍ふ业臓顟B(tài)。你仍然在實(shí)現(xiàn)遞歸過程，但滾動你自己的數(shù)據(jù)結(jié)構(gòu)。
這可能會更復(fù)雜，因?yàn)檎{(diào)用堆棧就像手套一樣。每個(gè)堆棧幀不僅記錄當(dāng)前節(jié)點(diǎn)，還記錄該節(jié)點(diǎn)中的計(jì)算狀態(tài)(在這種情況下，我們是僅采用左側(cè)還是已經(jīng)嘗試右側(cè))。然而，我們有時(shí)會因?yàn)楹ε乱绯龆艞壛嗣篮玫臇|西。在我看來是非常愚蠢的。
正如我們所看到的，棧很大，并且在?？臻g之前經(jīng)常會遇到其他約束。還可以檢查問題的大小并確?？梢园踩靥幚怼PU擔(dān)心主要是由兩個(gè)廣泛的病理學(xué)例子灌輸：愚蠢的因子和可靠的O(2 n) 遞歸Fibonacci沒有記憶。這些并不表示理智的堆棧遞歸算法。
現(xiàn)實(shí)情況是棧操作很快。數(shù)據(jù)的偏移是準(zhǔn)確的，棧在緩存中，不需要冷啟動，并且有專門的指令來完成工作。同時(shí)，使用您自己的堆分配數(shù)據(jù)結(jié)構(gòu)會產(chǎn)生大量開銷。會看到其他人編寫的東西比調(diào)用堆棧遞歸更復(fù)雜，性能更差。
現(xiàn)代CPU 非常優(yōu)秀了，通常不是瓶頸。簡單往往和性能等同。
