遞歸的概念很簡單，如果函數包含了對其自身的調用，該函數就是遞歸的。

遞歸（Recursion），在數學與計算機科學中，是指在函數的定義中使用函數自身的方法。

在使用遞歸時，需要注意以下幾點：

遞歸就是在過程或函數里調用自身

必須有一個明確的遞歸結束條件，稱為遞歸出口。

注意： 切勿忘記遞歸出口，避免函數無限調用。

遞歸基本步驟

每一個遞歸程序都遵循相同的基本步驟：

1.初始化算法。遞歸程序通常需要一個開始時使用的種子值（seed value）。要完成此任務，可以向函數傳遞參數，或者提供一個入口函數，這個函數是非遞歸的，但可以為遞歸計算設置種子值。

2.檢查要處理的當前值是否已經與基線條件相匹配（base case）。如果匹配，則進行處理并返回值。

3.使用更小的或更簡單的子問題（或多個子問題）來重新定義答案。

4.對子問題運行算法。

5.將結果合并入答案的表達式。

6.返回結果。

基線條件（base case）。基線條件是遞歸程序的最底層位置，在此位置時沒有必要再進行操作，可以直接返回一個結果。所有遞歸程序都必須至少擁有一個基線條件，而且必須確保它們最終會達到某個基線條件；否則，程序將永遠運行下去，直到程序缺少內存或者棧空間。

主要應用范圍

遞歸算法一般用于解決三類問題：

（1）數據的定義是按遞歸定義的。（比如Fibonacci函數）

（2）問題解法按遞歸算法實現。（回溯）

（3）數據的結構形式是按遞歸定義的。（比如樹的遍歷，圖的搜索）

典型的算法

大多數學過數學、計算機科學或者讀過編程相關書籍的人，想必都會遇到階乘：

n! = 1 × 2 × 3 × … × n

也可以用遞歸方式定義：

n! = (n-1)! × n

其中，n >= 1，并且 0! = 1。

由于簡單、清晰，因此其常被用作遞歸的示例。

PS： 除了階乘以外，還有很多算法可以使用遞歸來處理，例如：斐波那契數列、漢諾塔等。

非遞歸實現def factorial(n):

result = 1

for i in range(2, n+1):

result *= i

return result

階乘函數的遞歸實現def factorial(n):

if n == 0 or n == 1: return 1

else: return (n * factorial(n - 1))

遞歸過程

為了明確遞歸步驟，對 5! 進行過程分解：factorial(5) # 第 1 次調用使用 5

5 * factorial(4) # 第 2 次調用使用 4

5 * (4 * factorial(3)) # 第 3 次調用使用 3

5 * (4 * (3 * factorial(2))) # 第 4 次調用使用 2

5 * (4 * (3 * (2 * factorial(1)))) # 第 5 次調用使用 1

5 * (4 * (3 * (2 * 1))) # 從第 5 次調用返回

5 * (4 * (3 * 2)) # 從第 4 次調用返回

5 * (4 * 6) # 從第 3次調用返回

5 * 24 # 從第 2 次調用返回

120 # 從第 1 次調用返回

還是這個函數factorial(N)，讓我們試試N = 999和N = 1000，問題來了，N = 999時能輸出正確答案，但當N = 1000時，就出現下面的錯誤了：

RuntimeError: maximum recursion depth exceeded

于是，請記住，默認的Python有一個可用的遞歸深度的限制，以避免耗盡計算機中的內存。默認是1000。

遞歸優缺點

優點：

遞歸使代碼看起來更加整潔、優雅

可以用遞歸將復雜任務分解成更簡單的子問題

使用遞歸比使用一些嵌套迭代更容易

缺點:

遞歸的邏輯很難調試、跟進

遞歸算法解題的運行效率較低。在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。

總結

以上是生活随笔為你收集整理的python递归算法经典实例-Python递归算法详解的全部內容，希望文章能夠幫你解決所遇到的問題。

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