尾遞歸 —— 寫給命令式編程程序員

Python部落(python.freelycode.com)組織翻譯，禁止轉載，歡迎轉發。

在Recurse Center期間，我通讀了《計算機程序的構造和解釋》。這是一本出版於1985年的MIT的編程入門教材，用LISP的一種方言Scheme語言來教授編程。Scheme是函數式語言，我也一直喜歡學習新的函數式編程概念。

本文目的是向沒有函數式語言經驗或概念的程序員解釋「尾遞歸」。

在解釋尾遞歸之前，我們先看看命令式語言Python中的遞歸。

遞歸的一個問題

上面這段代碼定義了一個返回數字n的階乘的函數：factorial(n) = n * n - 1 * ... * 2 * 1。如果n = 4， 可以獲得期望的結果是4 * 3 * 2 * 1 = 24。

當我們運行一個遞歸函數時，在運行背後到底發生了什麼？任一函數被調用，就會往進程堆棧中加入一個包含與該函數有關的數據的棧幀，通過Python中的inspect模塊，我們可以觀察到發生了什麼：

運行這個腳本得到：

我們可以看到，當inspect.stack()第一次被調用時，一個棧幀加到了堆棧中。再次調用，堆棧中就有兩個棧幀了。

棧幀消耗內存，而一個Python進程只能分配到有限的內存。如果堆棧包含太多的棧幀，進程會耗盡所分配的內存，或者堆棧可能擴展到沒有分配給該進程的內存空間而導致堆棧溢出。為了防止出現這樣的問題，解釋器會設置一個最大遞歸數的限制，可以通過調用sys.getrecursionlimit()來查看這個限制。在我的計算機上，這個限制是1000（注）。

每一次調用factorial()，一個新的棧幀就會加到堆棧中。如果加入了太多的棧幀，就會超過這個最大遞歸數的限制，解釋器就會拋出如下異常：

由於棧幀產生系統開銷，所以在命令式語言中，遞歸是內存密集型的操作。相比下面的使用迭代方式獲取階乘的函數：

這個函數只產生了一個棧幀，比遞歸方式能更輕易處理大於n十倍或者更大的數值。

迭代遞歸

思考當解釋器執行factorial(4)時發生了什麼：

我們能看到創建了一系列延遲的操作，直到遇到n = 1時才會計算出最終結果。這是因為解釋器為了後面的執行必須要記住並跟蹤前面的操作。

如果我們重新定義factorial函數為：

並重新思考解釋器做了什麼：

我們看到一系列扁平的factorial()調用，狀態保存在變數total中，而不是由解釋器來保存。

尾遞歸

在「尾遞歸」語言中，以factorial_new這種方式定義的遞歸過程可以被解釋器解釋為迭代，從而不會帶來遞歸的缺點。用這種優雅的遞歸過程，能使你獲得和迭代一樣的性能優勢。解釋器知道不需要在堆棧上創建更多的棧幀，從而拋棄創建棧幀的方式。

不幸的是，Python不是「尾遞歸」語言，所以factorial_new(1000, 1)仍然會拋出RuntimeError: maximum recursion depth exceeded。

更多信息，推薦參考《計算機程序的構造和解釋》中的1.2.1小節。

註：在Python中可以調用sys.setrecursionlimit()來設置最大遞歸數，但通常不建議這麼做。遞歸調用太多的函數應該使用迭代的方式來重寫。

英文原文：https://jamesroutley.co.uk/tech/2017/06/04/tail-recursion.html

譯者：scala

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！