Python - 递归：初學者指南
你好，未來的Python巫師們！今天，我們將開啟一段令人興奮的旅程，進入递歸的世界。如果這聽起來有點兒令人生畏，別擔心——我保證我們會讓它變得有趣且容易理解。所以，拿起你喜歡的飲料，舒服地坐下，讓我們一起深入探討！
什麼是递歸？
想象一下，你站在兩面彼此對著的鏡子之間。你看到無窮無盡的反射，對吧？這有點像编程中的递歸！簡單來說，递歸就是函數為了解決問題而調用自己。
讓我們從一個簡單的例子開始：
def countdown(n):
if n <= 0:
print("發射！")
else:
print(n)
countdown(n - 1)
countdown(5)如果你運行這段代碼，你將會看到：
5
4
3
2
1
發射！現在，讓我們來解析一下：
- 我們定義了一個名為
countdown的函數，它接受一個數字n。 - 如果
n等於0或更小，我們打印"發射！"。 - 否則，我們打印
n，然後再次調用countdown，並將n - 1作為參數。
這就是递歸的實現！函數不斷地以一個較小的數字調用自己，直到達到0。
递歸的組件
每個遞歸函數都有兩個主要組件：
- 基礎情況：這是停止遞歸的條件。
- 遞歸情況：這裡函數調用自己。
在我們的倒數例子中：
- 基礎情況是
if n <= 0 - 遞歸情況是
countdown(n - 1)
讓我們再看一個經典的例子：計算階乘。
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # 輸出：120這裡發生了什麼：
- 如果
n是0或1，我們返回1（這是我們的基礎情況）。 - 否則，我們將
n乘以n - 1的階乘（這是我們的遞歸情況）。
所以，factorial(5)變成：
5 factorial(4)
5 (4 factorial(3))
5 (4 (3 factorial(2)))
5 (4 (3 (2 factorial(1))))
5 (4 (3 (2 1)))
5 4 3 2 1 = 120
递歸的力量
遞歸可以讓一些複雜的問題變得容易解決。讓我們看一個稍微進階一點的例子：費波那契數列。
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
for i in range(10):
print(fibonacci(i), end=" ")
# 輸出：0 1 1 2 3 5 8 13 21 34這個函數計算第n個費波那契數。費波那契數列從0和1開始，每個後續數字都是前兩個數字的和。
使用遞歸的二分搜索
現在，讓我們來解決一個更實際的例子：二分搜索。這是一種在排序數組中查找項目的有效方法。
def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2
if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1
arr = [2, 3, 4, 10, 40]
x = 10
result = binary_search(arr, 0, len(arr)-1, x)
if result != -1:
print(f"元素存在於索引 {result}")
else:
print("元素不存在於數組中")這個函數通過反覆將搜索區間除以二來工作。如果搜索鍵的值小於區間中間的項目，則將區間縮小到下半部分。否則，縮小到上半部分。反覆檢查，直到找到值或區間為空。
何時使用遞歸
遞歸特別適用於：
- 可以分解為類似子問題的問題
- 樹狀數據結構（例如，文件系統，HTML DOM）
- 如快速排序、合並排序等算法
然而，遞歸並不總是最好的解決方案。對於非常深的遞歸，它可能會消耗大量內存，有時一個簡單的循環可能會更有效且更容易理解。
遞歸方法表格
| 方法 | 描述 | 示例 |
|---|---|---|
| 直接遞歸 | 函數直接調用自己 | 我們的countdown和factorial例子 |
| 間接遞歸 | 函數A調用函數B，然後函數B調用函數A | 見以下示例 |
| 尾遞歸 | 遞歸調用是函數執行的最後一件事 | 我們的countdown例子 |
| 非尾遞歸 | 遞歸調用不是函數執行的最後一件事 | 我們的factorial例子 |
以下是一個間接遞歸的示例：
def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)
def is_odd(n):
return not is_even(n)
print(is_even(4)) # 輸出：True
print(is_odd(4)) # 輸出：False在這個例子中，is_even調用is_odd，然後is_odd調用is_even。
結論
恭喜你！你剛剛走出了令人著迷的遞歸世界的第一步。記住，像任何強大的工具一樣，遞歸應該被明智地使用。它可以使你的代碼更為優雅，並輕鬆解決複雜的問題，但也可能會使簡單的問題變得不必要的複雜。
當你繼續你的Python旅程時，你將會遇到許多可以應用遞歸的情況。繼續練習，你很快就會像專家一樣使用遞歸！
Credits: Image by storyset