Python 中15個遞歸函數經典案例解析
作者：手把手PythonAI編程
在本文中，我們將探索15個遞歸函數的經典案例，從基礎到進階，幫助你理解和掌握遞歸編程。
遞歸是Python編程中一個強大的工具，它允許函數調用自身以解決復雜問題。在本文中，我們將探索15個遞歸函數的經典案例，從基礎到進階，幫助你理解和掌握遞歸編程。
1. 階乘計算
階乘是一個常見的遞歸應用，定義為n! = n * (n-1) * ... * 1。
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # 輸出: 1202. 斐波那契數列
斐波那契數列的每一項都是前兩項的和。
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(10)) # 輸出: 553. 漢諾塔問題
漢諾塔是一個經典的遞歸問題，涉及將多個盤子從一個柱子移動到另一個柱子。
def hanoi(n, source, target, auxiliary):
if n > 0:
hanoi(n - 1, source, auxiliary, target)
print(f"Move disk {n} from {source} to {target}")
hanoi(n - 1, auxiliary, target, source)
hanoi(3, 'A', 'C', 'B')4. 冪運算
計算a的n次方。
def power(a, n):
if n == 0:
return 1
elif n % 2 == 0:
return power(a * a, n // 2)
else:
return a * power(a, n - 1)
print(power(2, 10)) # 輸出: 10245. 數組求和
遞歸地計算數組元素的總和。
def array_sum(arr):
if not arr:
return 0
else:
return arr[0] + array_sum(arr[1:])
print(array_sum([1, 2, 3, 4])) # 輸出: 106. 字符串反轉
使用遞歸來反轉字符串。
def reverse_string(s):
if len(s) <= 1:
return s
else:
return reverse_string(s[1:]) + s[0]
print(reverse_string("hello")) # 輸出: "olleh"7. 找出數組中的最大值
遞歸地找出數組中的最大值。
def find_max(arr):
if len(arr) == 1:
return arr[0]
else:
sub_max = find_max(arr[1:])
return arr[0] if arr[0] > sub_max else sub_max
print(find_max([3, 1, 4, 1, 5, 9])) # 輸出: 98. 二叉樹遍歷
遞歸地遍歷二叉樹。
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_traversal(node):
if node is not None:
inorder_traversal(node.left)
print(node.val, end=" ")
inorder_traversal(node.right)
root = Node(1, Node(2), Node(3))
inorder_traversal(root) # 輸出: 2 1 39. 平衡括號檢查
檢查字符串中的括號是否平衡。
def balanced_parentheses(s):
if not s:
return True
if s[0] == '(' and s[-1] == ')':
return balanced_parentheses(s[1:-1])
else:
return False
print(balanced_parentheses("(())")) # 輸出: True10. 帕斯卡三角形
生成帕斯卡三角形。
def pascals_triangle(n):
if n == 1:
return [1]
else:
row = [1]
prev_row = pascals_triangle(n - 1)
for i in range(len(prev_row) - 1):
row.append(prev_row[i] + prev_row[i + 1])
row.append(1)
return row
for i in range(1, 6):
print(pascals_triangle(i))11. 迷宮路徑
尋找迷宮的解決方案。
def maze_path(x, y, m, n):
if x == m or y == n:
return []
elif x == m - 1 and y == n - 1:
return [(x, y)]
else:
paths1 = maze_path(x + 1, y, m, n)
paths2 = maze_path(x, y + 1, m, n)
for path in paths1 + paths2:
path.insert(0, (x, y))
return paths1 + paths2
m, n = 3, 3
paths = maze_path(0, 0, m, n)
for path in paths:
print(path)12. 字符串排列
生成字符串的所有可能排列。
def string_permutations(s):
if len(s) == 1:
return [s]
else:
permutations = []
for i in range(len(s)):
char = s[i]
remaining_chars = s[:i] + s[i+1:]
for permutation in string_permutations(remaining_chars):
permutations.append(char + permutation)
return permutations
print(string_permutations('abc'))13. 八皇后問題
解決八皇后問題。
def solve_n_queens(n):
solutions = []
def place_queen(row, cols):
if row == n:
solutions.append(cols)
return
for col in range(n):
if all(abs(c - col) not in (0, row - i) for i, c in enumerate(cols[:row])):
place_queen(row + 1, cols + [col])
place_queen(0, [])
return solutions
for solution in solve_n_queens(8):
print(solution)14. 斗地主發牌
模擬斗地主游戲發牌過程。
import random
def deal_cards():
cards = ['3', '4', '5', '6', '7', '8', '9', '10', 'J', 'Q', 'K', 'A', '2'] * 4 + ['小王', '大王']
random.shuffle(cards)
hands = {'player1': [], 'player2': [], 'player3': []}
for i in range(17):
for player in hands:
hands[player].append(cards.pop())
return hands
print(deal_cards())15. 字符串匹配
檢查一個字符串是否包含另一個字符串。
def string_match(s, pattern):
if not pattern:
return True
if not s:
return False
if s[0] == pattern[0]:
return string_match(s[1:], pattern[1:])
else:
return string_match(s[1:], pattern)
print(string_match("hello", "he")) # 輸出: True實戰案例分析：漢諾塔問題
漢諾塔問題是一個典型的遞歸案例，涉及到將多個圓盤從一個柱子移動到另一個柱子上，但每次只能移動一個圓盤，且大盤不能放在小盤之上。
def hanoi(n, source, target, auxiliary):
if n > 0:
# 將n-1個圓盤從source移動到auxiliary
hanoi(n - 1, source, auxiliary, target)
# 移動最大的圓盤從source到target
print(f"Move disk {n} from {source} to {target}")
# 將n-1個圓盤從auxiliary移動到target
hanoi(n - 1, auxiliary, target, source)
# 示例調用
hanoi(3, 'A', 'C', 'B')這個例子展示了如何通過遞歸解決復雜問題，同時也體現了遞歸的分治策略。
使用技巧：
- 在面對問題時，思考是否可以通過分解為子問題來解決，這是遞歸的一個良好起點。
- 在設計遞歸函數時，始終定義清晰的基線情況和遞歸情況。
遞歸是編程中一個強大的概念，但使用得當才能發揮其真正的潛力。希望這篇文章能幫助你更好地掌握和應用遞歸技術！
責任編輯：趙寧寧
來源：
手把手PythonAI編程
