python遞歸_如何用Python遞歸地思考問題？

這是 Python資料科學的第 54 篇原創文章

【作者】：xiaoyu

【介紹】：一個半路轉行的資料挖掘工程師

【知乎專欄】：https://zhuanlan.zhihu.com/pypcfx

全文3345字 | 閱讀需要5分鐘

遞歸是一個很經典的算法，在實際中應用廣泛，也是面試中常常會提到的問題。本文就遞歸算法介紹如何在Python中實作遞歸的思想，以及遞歸在Python中使用時的一些注意事項，希望能夠對使用Python的朋友提供一些幫助。

1通俗地認識遞歸

為了更通俗的解釋遞歸，我們通過一個簡單的例子來說明。聖誕節到了，聖誕老人要給4個小朋友發禮物。每年過節，聖誕老人都會将禮物一家接一家的送，直到送完。這個過程我們可以通過一個簡單的循環來實作，如下：houses = ["Eric's house", "Kenny's house", "Kyle's house", "Stan's house"]

def deliver_presents_iteratively():

for house in houses:

print("Delivering presents to", house)

循環執行結果如下：>>> deliver_presents_iteratively()

Delivering presents to Eric's house

Delivering presents to Kenny's house

Delivering presents to Kyle's house

Delivering presents to Stan's house

但是今天聖誕老人覺得太累了，想偷個懶，不想自己一個個的送了。突然間腦袋靈光一閃，他想出了一個辦法，可以讓孩子們幫他來送禮物，并通過孩子們傳遞下去。這樣不但可以讓孩子們感受過節的氣氛，自己也可以省一部分力氣，簡直是兩全其美啊。于是乎，聖誕老人開始執行這個政策。1. 先指定一名小朋友，然後将所有的工作交給他。

2. 根據小朋友所負責的房子數量，來配置設定他們各自的職位和工作内容。如果房子數量>1，那麼他就是一個管理者，并可以再指定兩名小朋友來幫他完成他負責的工作。

如果房子數量=1，那麼他就是一個從業人員，他必須将禮物送到指定的房子。

這就是一個典型的遞歸算法結構。核心的思想就是：如果眼下的問題是一個最簡單的問題，那麼解決它。如果不是最簡單的，那就将問題劃分，直到成為最簡單問題，再運用同樣的政策進行解決。

用Python語言來實作以上遞歸思想可以這樣做：houses = ["Eric's house", "Kenny's house", "Kyle's house", "Stan's house"]

# 每次函數調用都代表一個小朋友負責的工作

def deliver_presents_recursively(houses):

# 從業人員通過送禮物，來執行工作

if len(houses) == 1:

house = houses[0]

print("Delivering presents to", house)

# 管理者通過配置設定工作，來執行所負責的工作

else:

mid = len(houses) // 2

first_half = houses[:mid]

second_half = houses[mid:]

# 将工作劃分給另外兩個小朋友

deliver_presents_recursively(first_half)

deliver_presents_recursively(second_half)

執行結果如下：>>> deliver_presents_recursively(houses)

Delivering presents to Eric's house

Delivering presents to Kenny's house

Delivering presents to Kyle's house

Delivering presents to Stan's house

2Python中的遞歸函數

相信通過以上的舉例，大家對遞歸已經有了一個初步的認識。現在來正式地介紹一下遞歸函數的定義。如果一個函數直接或者間接地調用函數本身，那麼就是遞歸函數。

這意味着，函數将不斷的調用本身并重複函數的内容，直到達到某個條件才傳回一個結果。所有的遞歸函數都有着同樣的結構，這個結構由兩部分組成：基礎部分，遞歸部分。

為了更好地說明這個結構，我們舉一個例子說明，來寫一個遞歸函數計算n的階層（n！）：

1. 遞歸部分：将原始問題（n！）分解為最簡單并且相同的小問題。通過将n！分解我們看到這個更小且相同的問題就是每次與比自己小于1的數字相乘（n*(n-1)!）：n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1

n! = n x (n−1)!

2. 基礎部分：上面的遞歸部分将大的問題分解為一個個相同的小問題，但是肯定不會無限制的遞歸下去。我們需要找到一個不能繼續往下遞歸的停止條件，也就是基礎部分。通過不斷分解n！我們發現最後到達1的時候不能再繼續遞歸了，是以，1！就是我們最後的基礎部分。n! = n x (n−1)!

n! = n x (n−1) x (n−2)!

n! = n x (n−1) x (n−2) x (n−3)!

⋅

⋅

n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3!

n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2!

n! = n x (n−1) x (n−2) x (n−3) ⋅⋅⋅⋅ x 3 x 2 x 1!

知道了遞歸結構中的這兩個部分，我們在Python中來實作n！的遞歸算法：def factorial_recursive(n):

# 基礎部分: 1! = 1

if n == 1:

return 1

# 遞歸部分: n! = n * (n-1)!

else:

return n * factorial_recursive(n-1)

執行結構如下：>>> factorial_recursive(5)

120

雖然知道如何寫出一個遞歸算法了，但是對于程式背後的原理我們也是要了解的。程式背後的底層場景是：每次遞歸調用會添加一個桟幀（包含它的執行内容）到棧，不斷添加直到達到了基礎部分的停止條件，然後棧再依次解開每個調用并傳回它的結果，可以參考下圖。

3狀态維持

當處理遞歸函數時，每次遞歸調用都有自己的執行上下文，即每次遞歸調用之間的狀态都是獨立的。當我們想每次遞歸的時候都更新一個狀态，并得到最後的更新結果，那該怎麼辦呢？為了維持遞歸中想要維持的狀态，我們有兩種方法可以使用：将狀态嵌入到每一次的遞歸調用中作為參數。

将狀态設定為全局變量。

我們使用一個例子來說明上面提到的兩種方法。比如，我們要使用遞歸計算1+2+3...+10，這裡我們必須要維持的狀态就是累積和。

将狀态作為參數遞歸調用

下面我們使用第一種方法，即将狀态嵌入每次遞歸中維持狀态，來實作上面例子。def sum_recursive(current_number, accumulated_sum):

# 基礎部分

# 傳回最後狀态

if current_number == 11:

return accumulated_sum

# 遞歸部分

# 将狀态嵌入到每次遞歸調用中

else:

return sum_recursive(current_number + 1, accumulated_sum + current_number)

執行結果如下：# 傳遞初始狀态

>>> sum_recursive(1, 0)

55

設定狀态為全局變量

下面我們使用第二種方法，即設定全局變量，來實作上面例子。# 全局變量

current_number = 1

accumulated_sum = 0

def sum_recursive():

global current_number

global accumulated_sum

# 基礎部分

if current_number == 11:

return accumulated_sum

# 遞歸部分

else:

accumulated_sum = accumulated_sum + current_number

current_number = current_number + 1

return sum_recursive()

執行結果如下：>>> sum_recursive()

55

通常我更喜歡使用将狀态作為函數參數的方法實作遞歸，因為全局變量是有一些弊端的。

4Python中的遞歸資料結構

如果一個資料結構可以分解成一個個和自己一樣的更小的版本，那麼這個資料結構也可以是遞歸的。清單就是一個遞歸資料結構的典型例子。下面，讓我們就來驗證一下。現在有一個空的清單，并且可以在清單上使用的唯一操作規定如下：# 傳回一個新的清單，傳回結果為在input_list表頭添加一個新元素

def attach_head(element, input_list):

return [element] + input_list

通過使用空清單和attach_head操作，我們就可以生成任何清單了。例如，我們想生成 [1，46，-31，"hello"]：attach_head(1, # Will return [1, 46, -31, "hello"]

attach_head(46, # Will return [46, -31, "hello"]

attach_head(-31, # Will return [-31, "hello"]

attach_head("hello", [])))) # Will return ["hello"]

上面實作過程如下：

遞歸資料結構和遞歸函數可以一起配合使用。通常我們可以将遞歸資料結構作為遞歸函數的參數來實作遞歸。因為我們知道了遞歸資料結構是遞歸的，我們就可以輕易地将遞歸資料結構拆分為一個個更小并且相同小的問題，然後通過遞歸進行解決。

下面就是一個将清單作為遞歸函數參數的例子，遞歸部分是利用了清單的切片操作，不斷切分清單為更小的部分，停止條件就是直到清單為空。def list_sum_recursive(input_list):

# 基礎部分

if input_list == []:

return 0

# 遞歸部分

else:

head = input_list[0]

smaller_list = input_list[1:]

return head + list_sum_recursive(smaller_list)

執行結構如下：>>> list_sum_recursive([1, 2, 3])

6

但清單并不是唯一的遞歸資料結構。其它的還包括集合，樹，字典等。

5遞歸的注意事項

在我們用Python實作遞歸的過程中，也有一些地方需要注意。

遞歸效率問題

我們通過舉一個例子來說明，比如我們要使用遞歸實作斐波那契數列。

遞歸部分： Fn = Fn-1 + Fn-2

基礎部分： F0 = 0 and F1 = 1

在Python中實作遞歸：def fibonacci_recursive(n):

print("Calculating F", "(", n, ")", sep="", end=", ")

# 基礎部分

if n == 0:

return 0

elif n == 1:

return 1

# 遞歸部分

else:

return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

執行結果如下：>>> fibonacci_recursive(5)

Calculating F(5),

Calculating F(4),

Calculating F(3),

Calculating F(2),

Calculating F(1),

Calculating F(0),

Calculating F(1),

Calculating F(2),

Calculating F(1),

Calculating F(0),

Calculating F(3),

Calculating F(2),

Calculating F(1),

Calculating F(0),

Calculating F(1),

5

我們發現計算過程中有很多重複計算的部分，這樣會嚴重影響我們遞歸實作的效率。那該如何優化一下呢？

Python中有一個強大的裝飾器：lru_cache，它主要是用來做緩存，能把相對耗時的函數結果進行儲存，避免傳入相同的參數重複計算。LRU全稱為Least Recently Used，相信好多朋友都知道這個算法，這裡不進行詳細講解了。

下面我們來看一下加入裝飾器lru_cache之後效果如何。from functools import lru_cache

@lru_cache(maxsize=None)

def fibonacci_recursive(n):

print("Calculating F", "(", n, ")", sep="", end=", ")

# 基礎部分

if n == 0:

return 0

elif n == 1:

return 1

# 遞歸部分

else:

return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

執行結果如下：>>> fibonacci_recursive(5)

Calculating F(5),

Calculating F(4),

Calculating F(3),

Calculating F(2),

Calculating F(1),

Calculating F(0),

5

從結果發現一些重複的計算過程已經消失，這樣就節省了很多時間，提升了遞歸的運作效率。但要注意的是：lru_cache是通過使用一個字典來緩存結果的，是以函數的位置和關鍵字參數（字典中的keys）必須是散列的。

遞歸深度問題

Python不支援tail-call elimination（尾調用消除）。是以，如果我們使用了更多的桟幀，并且超過了預設的調用棧的深度，那麼你将會引起棧溢出的問題。

我們通過getrecursionlimit觀察預設的遞歸深度限制，預設為3000。是以，這個我們需要注意一下。>>> import sys

>>> sys.getrecursionlimit()

3000

同樣還有，Python的可變資料結構不支援結構化共享，如果把它們當成了不可變資料結構，那麼這将會對我們的空間和GC（垃圾回收）效率造成很不好的影響。因為這樣做會不必要地複制很多可變對象作為結尾，下面舉了一個簡單的例子說明。>>> input_list = [1, 2, 3]

>>> head = input_list[0]

>>> tail = input_list[1:]

>>> print("head --", head)

head -- 1

>>> print("tail --", tail)

tail -- [2, 3]

tail是通過複制建立的，是以，如果我們在很大的清單上遞歸地重複用這個複制操作，那麼就會對我們的空間和GC效率産生壞的影響。https://realpython.com/python-thinking-recursively/