知識星球
作者 | Gustavo Duarte
譯者 | qhwdw ? ? ? ? ? 共計翻譯：105 篇 貢獻時間：177 天
“方其夢也，不知其夢也。夢之中又佔其夢焉，覺而後知其夢也。”
—— 《莊子·齊物論》
遞迴是很神奇的，但是在大多數的程式設計類書藉中對遞迴講解的並不好。它們只是給你展示一個遞迴階乘的實現，然後警告你遞迴執行的很慢，並且還有可能因為棧緩衝區上限溢位而崩潰。“你可以將頭伸進微波爐中去烘乾你的頭髮，但是需要警惕顱內高壓並讓你的頭髮生爆炸，或者你可以使用毛巾來擦乾頭髮。”難怪人們不願意使用遞迴。但這種建議是很糟糕的，因為在演演算法中，遞迴是一個非常強大的思想。
我們來看一下這個經典的遞迴階乘：
#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.c
函式呼叫自身的這個觀點在一開始是讓人很難理解的。為了讓這個過程更形象具體，下圖展示的是當呼叫 factorial(5) 並且達到 n == 1這行程式碼 時，棧上[1] 端點的情況：
每次呼叫 factorial 都生成一個新的 棧幀[2]。這些棧幀的建立和 銷毀[3] 是使得遞迴版本的階乘慢於其相應的迭代版本的原因。在呼叫傳回之前，累積的這些棧幀可能會耗盡棧空間，進而使你的程式崩潰。
而這些擔心經常是存在於理論上的。例如，對於每個 factorial 的棧幀佔用 16 位元組（這可能取決於棧排列以及其它因素）。如果在你的電腦上執行著現代的 x86 的 Linux 核心，一般情況下你擁有 8 GB 的棧空間，因此，factorial 程式中的 n 最多可以達到 512,000 左右。這是一個 巨大無比的結果[4]，它將花費 8,971,833 位元來表示這個結果，因此，棧空間根本就不是什麼問題：一個極小的整數 —— 甚至是一個 64 位的整數 —— 在我們的棧空間被耗盡之前就早已經上限溢位了成千上萬次了。
過一會兒我們再去看 CPU 的使用，現在，我們先從位元和位元組回退一步，把遞迴看作一種通用技術。我們的階乘演演算法可歸結為：將整數 N、N-1、 … 1 推入到一個棧，然後將它們按相反的順序相乘。實際上我們使用了程式呼叫棧來實現這一點，這是它的細節：我們在堆上分配一個棧並使用它。雖然呼叫棧具有特殊的特性，但是它也只是又一種資料結構而已，你可以隨意使用。我希望這個示意圖可以讓你明白這一點。
當你將棧呼叫視為一種資料結構，有些事情將變得更加清晰明瞭：將那些整數堆積起來，然後再將它們相乘，這並不是一個好的想法。那是一種有缺陷的實現：就像你拿螺絲刀去釘釘子一樣。相對更合理的是使用一個迭代過程去計算階乘。
但是，螺絲釘太多了，我們只能挑一個。有一個經典的面試題，在迷宮裡有一隻老鼠，你必須幫助這隻老鼠找到一個乳酪。假設老鼠能夠在迷宮中向左或者向右轉彎。你該怎麼去建模來解決這個問題？
就像現實生活中的很多問題一樣，你可以將這個老鼠找乳酪的問題簡化為一個圖，一個二叉樹的每個結點代表在迷宮中的一個位置。然後你可以讓老鼠在任何可能的地方都左轉，而當它進入一個死衚衕時，再回溯回去，再右轉。這是一個老鼠行走的 迷宮示例[5]:
每到邊緣（線）都讓老鼠左轉或者右轉來到達一個新的位置。如果向哪邊轉都被攔住，說明相關的邊緣不存在。現在，我們來討論一下！這個過程無論你是呼叫棧還是其它資料結構，它都離不開一個遞迴的過程。而使用呼叫棧是非常容易的：
#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);
}
遞迴迷宮求解 下載[6]
當我們在 maze.c:13 中找到乳酪時，棧的情況如下圖所示。你也可以在 GDB 輸出[7] 中看到更詳細的資料，它是使用 命令[8] 採集的資料。
它展示了遞迴的良好表現，因為這是一個適合使用遞迴的問題。而且這並不奇怪：當涉及到演演算法時，遞迴是規則，而不是例外。它出現在如下情景中——進行搜尋時、進行遍歷樹和其它資料結構時、進行解析時、需要排序時——它無處不在。正如眾所周知的 pi 或者 e，它們在數學中像“神”一樣的存在，因為它們是宇宙萬物的基礎，而遞迴也和它們一樣：只是它存在於計算結構中。
Steven Skienna 的優秀著作 演演算法設計指南[9] 的精彩之處在於，他透過 “戰爭故事” 作為手段來詮釋工作，以此來展示解決現實世界中的問題背後的演演算法。這是我所知道的拓展你的演演算法知識的最佳資源。另一個讀物是 McCarthy 的 關於 LISP 實現的的原創論文[10]。遞迴在語言中既是它的名字也是它的基本原理。這篇論文既可讀又有趣，在工作中能看到大師的作品是件讓人興奮的事情。
回到迷宮問題上。雖然它在這裡很難離開遞迴，但是並不意味著必須透過呼叫棧的方式來實現。你可以使用像 RRLL 這樣的字串去跟蹤轉向，然後，依據這個字串去決定老鼠下一步的動作。或者你可以分配一些其它的東西來記錄追尋乳酪的整個狀態。你仍然是實現了一個遞迴的過程，只是需要你實現一個自己的資料結構。
那樣似乎更複雜一些，因為棧呼叫更合適。每個棧幀記錄的不僅是當前節點，也記錄那個節點上的計算狀態（在這個案例中，我們是否只讓它走左邊，或者已經嘗試向右）。因此，程式碼已經變得不重要了。然而，有時候我們因為害怕上限溢位和期望中的效能而放棄這種優秀的演演算法。那是很愚蠢的！
正如我們所見，棧空間是非常大的，在耗盡棧空間之前往往會遇到其它的限制。一方面可以透過檢查問題大小來確保它能夠被安全地處理。而對 CPU 的擔心是由兩個廣為流傳的有問題的示例所導致的：啞階乘和可怕的無記憶的 O( 2n ) Fibonacci 遞迴[11]。它們並不是棧遞迴演演算法的正確代表。
事實上棧操作是非常快的。通常，棧對資料的偏移是非常準確的，它在 快取[12] 中是熱資料，並且是由專門的指令來操作它的。同時，使用你自己定義的在堆上分配的資料結構的相關開銷是很大的。經常能看到人們寫的一些比棧呼叫遞迴更複雜、效能更差的實現方法。最後，現代的 CPU 的效能都是 非常好的[13] ，並且一般 CPU 不會是效能瓶頸所在。在考慮犧牲程式的簡單性時要特別註意，就像經常考慮程式的效能及效能的測量[14]那樣。
下一篇文章將是探秘棧系列的最後一篇了，我們將瞭解尾呼叫、閉包、以及其它相關概念。然後，我們就該深入我們的老朋友—— Linux 核心了。感謝你的閱讀！
via:https://manybutfinite.com/post/recursion/
作者：Gustavo Duarte[16] 譯者：qhwdw 校對：FSSlc
本文由 LCTT 原創編譯，Linux中國 榮譽推出
