Python 遞歸的十個技巧
作者：huaan9527
遞歸是編程中一種強大的技術，但在使用時需要注意避免一些常見的陷阱。以下是 Python 遞歸的技巧，幫助你更高效、更安全地使用遞歸。
遞歸是編程中一種強大的技術，但在使用時需要注意避免一些常見的陷阱。以下是 Python 遞歸的技巧，幫助你更高效、更安全地使用遞歸。
1. 確定基本情況
每個遞歸函數都必須有一個或多個基本情況，這些情況不需要進一步遞歸即可解決。
示例：
def factorial(n):
if n == 0: # 基本情況
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # 輸出結果: 1202. 確保遞歸調用逐步逼近基本情況
遞歸調用必須逐步接近基本情況，否則會導致無限遞歸。
示例：
def countdown(n):
if n == 0: # 基本情況
print("結束")
else:
print(n)
countdown(n - 1) # 逐步逼近基本情況
countdown(5)
# 輸出結果: 5 4 3 2 1 結束3. 使用尾遞歸優化
尾遞歸是指遞歸調用是函數的最后一個操作，這樣編譯器可以優化遞歸，避免棧溢出。
示例：
def tail_factorial(n, accumulator=1):
if n == 0: # 基本情況
return accumulator
else:
return tail_factorial(n - 1, n * accumulator) # 尾遞歸
print(tail_factorial(5)) # 輸出結果: 1204. 使用緩存（Memoization）減少重復計算
緩存已經計算過的結果，可以顯著提高遞歸函數的性能。
示例：
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(30)) # 輸出結果: 8320405. 避免深度過大的遞歸
Python 默認的遞歸深度限制是 1000，可以通過 sys.setrecursionlimit 增加限制，但不推薦這樣做。更好的做法是改用迭代或其他算法。
示例：
import sys
sys.setrecursionlimit(2000) # 增加遞歸深度限制
def deep_recursion(n):
if n == 0:
return 0
else:
return deep_recursion(n - 1)
deep_recursion(1500) # 不推薦這樣做6. 使用生成器替代遞歸
對于某些問題，使用生成器可以避免遞歸帶來的棧溢出問題。
示例：
def fibonacci_generator(n):
a, b = 0, 1
for _ in range(n):
yield a
a, b = b, a + b
for num in fibonacci_generator(10):
print(num)
# 輸出結果: 0 1 1 2 3 5 8 13 21 347. 使用迭代替代遞歸
對于某些問題，使用迭代可以更高效地解決問題。
示例：
def iterative_factorial(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
print(iterative_factorial(5)) # 輸出結果: 1208. 遞歸樹的可視化
使用遞歸樹幫助理解遞歸過程，特別是對于復雜的遞歸問題。
示例：
def recursive_tree(n, indent=""):
if n == 0:
print(indent + "End")
else:
print(indent + f"Level {n}")
recursive_tree(n - 1, indent + " ")
recursive_tree(n - 1, indent + " ")
recursive_tree(3)
# 輸出結果:
# Level 3
# Level 2
# Level 1
# End
# Level 1
# End
# Level 2
# Level 1
# End
# Level 1
# End9. 遞歸和非遞歸的結合
對于某些問題，可以結合遞歸和非遞歸的方法來提高效率。
示例：
def hybrid_factorial(n):
if n < 10: # 使用遞歸
return n * hybrid_factorial(n - 1) if n > 1 else 1
else: # 使用迭代
result = 1
for i in range(2, n + 1):
result *= i
return result
print(hybrid_factorial(15)) # 輸出結果: 130767436800010. 使用遞歸解決分治問題
遞歸特別適用于分治問題，即將大問題分解成小問題來解決。
示例：
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
result.extend(left or right)
return result
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_arr = merge_sort(arr)
print(sorted_arr) # 輸出結果: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]總結
以上Python 遞歸的技巧，這些技巧可以幫助你更高效、更安全地使用遞歸。遞歸是一種強大的工具，但使用不當可能會導致性能問題和棧溢出。通過這些技巧，你可以更好地理解和應用遞歸，提高你的編程技能。
責任編輯：華軒
來源：
測試開發學習交流
