遞迴的方式和時間
當函式呼叫導致在原始函式呼叫終止之前再次呼叫相同的函式時，會發生遞迴。例如，考慮眾所周知的數學表示式 x!（即因子運算）。為所有非負整數定義了階乘操作，如下所示：
- 如果數字為 0，則答案為 1。
- 否則，答案是該數字乘以比該數字小 1 的階乘。
在 Python 中，可以將因子操作的簡單實現定義為如下函式：
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
遞迴函式有時很難掌握，所以讓我們一步一步地逐步完成。考慮表達 factorial(3)。此和所有函式呼叫都會建立一個新環境。環境基本上只是將識別符號（例如 n，factorial，print 等）對映到其對應值的表。在任何時間點，你都可以使用 locals() 訪問當前環境。在第一個函式呼叫中，唯一定義的區域性變數是 n = 3。因此，列印 locals() 會顯示 {'n': 3}。從 n == 3 開始，返回值變為 n * factorial(n - 1)。
在接下來的步驟中，事情可能會變得有些混亂。看看我們的新表達，我們已經知道什麼是 n。但是，我們還不知道 factorial(n - 1) 是什麼。首先，n - 1 評估為 2。然後，2 作為 n 的值傳遞給 factorial。由於這是一個新的函式呼叫，因此建立了第二個環境來儲存這個新的 n。設 A 為第一環境， B 為第二環境。 A 仍然存在且等於 {'n': 3}，然而， B （等於 {'n': 2}）是當前環境。檢視函式體，返回值又是 n * factorial(n - 1)。在不評估此表示式的情況下，讓我們將其替換為原始的返回表示式。通過這樣做，我們在精神上丟棄B，所以記得要相應地替代 n（即引用B的 n 與 n - 1 其使用取代A小號 n’）。現在，原始的返回表示式變為 n * ((n - 1) * factorial((n - 1) - 1))。花一點時間確保你明白為什麼會這樣。
現在，讓我們評估一下這個部分。從 A ’s n == 3 開始，我們將 1 傳遞給 factorial。因此，我們正在創造一個新的環境 C ，它等於 {'n': 1}。同樣，返回值是 n * factorial(n - 1)。因此，讓我們替換原始返回表示式的 factorial((n - 1) - 1))，類似於我們之前調整原始返回表示式的方式。 原始表達現在是 n * ((n - 1) * ((n - 2) * factorial((n - 2) - 1)))。
幾乎完成了。現在，我們需要評估 factorial((n - 2) - 1)。這一次，我們正在傳遞 0。因此，這評估為 1。現在，讓我們進行最後一次替換。 原始的迴歸表達現在是 n * ((n - 1) * ((n - 2) * 1))。回想一下原始返回表示式在 A 下計算，表示式變為 3 * ((3 - 1) * ((3 - 2) * 1))。當然，這評估為 6.要確認這是正確答案，請回憶一下 3! == 3 * 2 * 1 == 6。在進一步閱讀之前，請確保你完全理解環境的概念以及它們如何應用於遞迴。
宣告 if n == 0: return 1 被稱為基本案例。這是因為它沒有遞迴。絕對需要一個基本案例。沒有一個，你將遇到無限遞迴。話雖如此，只要你至少有一個基本案例，你就可以擁有任意數量的案例。例如，我們可以按如下方式編寫 factorial：
def factorial(n):
if n == 0:
return 1
elif n == 1:
return 1
else:
return n * factorial(n - 1)
你可能還有多個遞迴案例，但我們不會涉及到這種情況，因為它相對不常見並且通常很難進行精神處理。
你還可以進行並行遞迴函式呼叫。例如，考慮 Fibonacci 序列 ，其定義如下：
- 如果數字為 0，則答案為 0。
- 如果數字是 1，那麼答案是 1。
- 否則，答案是前兩個斐波納契數的總和。
我們可以定義如下：
def fib(n):
if n == 0 or n == 1:
return n
else:
return fib(n - 2) + fib(n - 1)
我不會像使用 factorial(3) 那樣徹底地完成這個功能，但是 fib(5) 的最終返回值等同於以下（ 語法無效）表示式：
(
fib((n - 2) - 2)
+
(
fib(((n - 2) - 1) - 2)
+
fib(((n - 2) - 1) - 1)
)
)
+
(
(
fib(((n - 1) - 2) - 2)
+
fib(((n - 1) - 2) - 1)
)
+
(
fib(((n - 1) - 1) - 2)
+
(
fib((((n - 1) - 1) - 1) - 2)
+
fib((((n - 1) - 1) - 1) - 1)
)
)
)
這變成了 (1 + (0 + 1)) + ((0 + 1) + (1 + (0 + 1)))，當然評估為 5。
現在，我們將介紹一些詞彙術語：
- 一個尾呼叫是一個簡單的遞迴函式呼叫，它是返回值之前要執行的最後一個操作。要清楚，
return foo(n - 1)是一個尾呼叫，但return foo(n - 1) + 1不是（因為新增是最後一個操作）。 - 尾呼叫優化 （TCO）是一種自動減少遞迴函式遞迴的方法。
- 尾呼叫消除 （TCE）是對一個表示式的尾呼叫的減少，該表示式可以在沒有遞迴的情況下進行求值。TCE 是一種 TCO。
尾呼叫優化有很多原因：
由於多種原因， Python 沒有實現任何形式的 TCO。因此，需要其他技術來限制這種限制。選擇方法取決於用例。通過一些直覺，factorial 和 fib 的定義可以相對容易地轉換為迭代程式碼，如下所示：
def factorial(n):
product = 1
while n > 1:
product *= n
n -= 1
return product
def fib(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a
這通常是手動消除遞迴的最有效方法，但對於更復雜的函式來說，它可能變得相當困難。
另一個有用的工具是 Python 的 lru_cache 裝飾器，它可用於減少冗餘計算的次數。
你現在已經知道如何避免 Python 中的遞迴，但何時應該使用遞迴？答案是不經常。所有遞迴函式都可以迭代實現。這只是一個弄清楚如何做到這一點的問題。但是，極少數情況下遞迴是可以的。當預期的輸入不會導致大量的遞迴函式呼叫時，遞迴在 Python 中很常見。
如果遞迴是你感興趣的主題，我懇請你學習函式語言，如 Scheme 或 Haskell。在這種語言中，遞迴更有用。
請注意，Fibonacci 序列的上述示例雖然很好地展示瞭如何在 python 中應用定義以及稍後使用 lru 快取，但由於它為每個非基本情況進行 2 次遞迴呼叫，因此執行時間效率低。對函式的呼叫次數呈指數增長至 n。
相反，非直觀地，更有效的實現將使用線性遞迴：
def fib(n):
if n <= 1:
return (n,0)
else:
(a, b) = fib(n - 1)
return (a + b, a)
但那個問題就是返回一對數字。這強調了一些函式實際上並沒有從遞迴中獲得太多收益。