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