“?遞歸函數就是函數內部調用自身，可以使代碼邏輯更加易懂。但是遞歸也有坑，需要避免。”

13.1 概念

• 在函數內部，可以調用其他函數。如果一個函數在內部調用自身，這個函數就是遞歸函數。

• 理論上，所有的遞歸函數都可以寫成循環的方式，但循環的邏輯不如遞歸清晰。

計算階乘n! = 1 x 2 x 3 x ... x n，用函數fact(n)表示：

def fact(n): if n==1: return 1 return n * fact(n - 1)

13.2 寫遞歸代碼的套路

寫遞歸代碼的關鍵就是找到如何將大問題分解為小問題的規律，然后按照下面套路即可實現：

• 第一步，寫出遞推公式

以計算階乘為例，遞歸公式是：fact(n)=n!=n×(n?1)×???3×2×1=n×(n?1)!=n×fact(n?1)

• 第二步，推敲終止條件

以計算階乘為例，終止條件是n=1時，fact(1)=1。

13.2.1 斐波那契數列

再來看一個斐波那契數列的例子，斐波那契數列中后一個元素是前兩個相鄰元素的和。比如：

0，1，1，2，3，5，8，13，21，34，55，…。

那么我們如何得到第n個數是多少？分兩步走：

第一步，寫出遞推公式。求第n個元素，可以先求出n-1和n-2個元素的值，然后再將這兩個求和，所以公式是：

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

第二步，推敲最終終止條件。終止條件包含三個：n=0時，f(n)=0；n=1時，f(n)=1；n=2時，f(n)=1。

if n < 1: # 遞歸終止條件 return 0if n in [1, 2]: # 遞歸終止條件 return 1

轉換成完整代碼就是：

def fibonacci(n): if n < 1: # 遞歸終止條件 return 0 if n in [1, 2]: # 遞歸終止條件 return 1 return fibonacci(n - 1) + fibonacci(n - 2) # 遞歸公式

不管是編寫遞歸還是閱讀遞歸代碼，只要遇到遞歸，我們就把它抽象成一個遞推公式，不用想一層層的調用關系，不要試圖用人腦搞清楚計算機每一步都是怎么執行的。

13.2.2 n 個臺階有多少種走法

再來看看一個例子，假如有 n 個臺階，每次可以跨 1 個臺階或者 2 個臺階，請問走這 n 個臺階有多少種走法？

我們從第一步開始想，如果第一步跨1個臺階，問題就變成了n-1個臺架有多少種走法。如果第一步跨2個臺階，問題就變成n-2個臺階有多少種走法。我們把n-1個臺階的走法和n-2個臺階的走法求和，就是n個臺階的走法。用公式表示就是f(n)=f(n-1)+f(n-2)。這就是遞歸公式了。

再來看看終止條件，最后1個臺階就不需要再繼續遞歸了，只有一種走法，就是f(1)=1。我們把這個放到遞歸公式里面看下，通過這個終止條件能否求出f(2)，發現f(2)=f(1)+f(0)，也就是僅知道f(1)是不能求出f(2)的，因此要么知道f(0)的值，或者直接將f(2)作為一個遞歸終止條件。f(0)表示0個臺階有幾種走法，f(2)表示2個臺階有幾種走法。明顯，f(2)更容易理解一些。所以定為f(2)=2也是一個終止條件，表示最后2個臺階有兩種走法，即一次跨1個臺階和一次跨2個臺階。有了f(1)和f(2)，就能求出f(3)，進而求出f(n)了。

轉化成代碼即是：

def walk(n): if n == 1: # 遞歸終止條件 return 1 if n == 2: # 遞歸終止條件 return 2 return walk(n - 1) + walk(n - 2) # 遞歸公式

13.3 遞歸可解決哪類問題

• 原始問題的解可以分解為幾個子問題的解

• 原始問題和子問題，只有數據規模的不同，求解思路完全一樣

• 存在遞歸終止條件

13.4 遞歸存在的問題

• 堆棧溢出

• 重復計算

編寫遞歸代碼時，我們會遇到很多問題，比較常見的一個就是堆棧溢出，而堆棧溢出會造成系統性崩潰，后果會非常嚴重。什么是堆棧溢出呢？

函數調用會使用棧來保存臨時變量。每調用一個函數，都會將臨時變量封裝為棧幀壓入內存棧，等函數執行完成返回時，再出棧。系統棧或者虛擬機棧空間一般都不大。如果遞歸求解的數據規模很大，調用層次很深，一直壓入棧，就會有堆棧溢出的風險。

可以通過Pycharm工具查看調用棧的情況。在遞歸公式那行代碼上添加斷點，不斷執行Step Over，可以看到Frames窗口中的棧信息會不斷增加和減少，當調用一次函數會增加一幀，當調用返回后會減少一幀。最后返回第一層棧func.py。前面說的堆棧溢出的風險，體現在Frames窗口中的棧幀太多了。

那么，如何避免出現堆棧溢出呢？

通常可以在代碼中限制遞歸調用的最大深度的方式來解決這個問題。比如Python語言，限制了遞歸深度，當遞歸深度過高，則會拋出：RecursionError: maximum recursion depth exceeded in comparison異常，防止系統性崩潰。

我們在代碼中也可以自己設置遞歸的深度，比如限制n最大不能超過100，代碼如下：

def walk(n): if n == 1: return 1 if n == 2: return 2 if n > 100: raise RecursionError("recursion depth exceede 100") return walk(n - 1) + walk(n - 2)

除此之外，使用遞歸時還會出現重復計算的問題。什么意思？拿走臺階那個例子來說明。比如計算6個臺階的走法f(6)，過程如下圖：

從圖中，我們可以直觀地看到，想要計算 f(5)，需要先計算 f(4) 和 f(3)，而計算 f(4) 還需要計算 f(3)，因此，f(3) 就被計算了很多次，這就是重復計算問題。

那么怎么解決這個問題？為了避免重復計算，我們可以通過字典保存已經求解過的 f(k)。當遞歸調用到 f(k) 時，先看下是否已經求解過了。如果是，則直接從字典中取值，不需要重復計算，這樣就能避免剛講的問題了。

修改下計算臺階走法的代碼，解決重復計算的問題：

data = dict() # 保存中間結果def walk(n): if n == 1: return 1 if n == 2: return 2 if n > 100: raise RecursionError("recursion depth exceed 100") if n in data: # 如果在中間結果中，則直接返回，不用進入遞推公式再次計算 return data[n] result = walk(n - 1) + walk(n - 2) # 在遞歸公式前面增加個查找步驟 data[n] = result # 將計算結果保存在中間結果data字典中 return resultprint(walk(6))

總結

以上是生活随笔為你收集整理的python 递归函数_连载|想用Python做自动化测试？递归函数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。