Python递归与分治算法：从原理到实战

1. 递归：编程中的自我调用艺术

递归（Recursion）是函数直接或间接调用自身的一种编程技巧。它将一个复杂问题分解为规模更小的同类子问题，直到子问题简单到可以直接求解。

1.1 递归的核心要素

一个有效的递归函数通常包含两个关键部分：

• 基线条件（Base Case）：递归终止的条件，防止无限递归。
• 递归条件（Recursive Case）：将问题分解为更小的同类问题，并调用自身。

1.2 经典递归示例：阶乘计算

def factorial(n):
"""计算n的阶乘"""
# 基线条件
if n == 0 or n == 1:
return 1
# 递归条件
return n * factorial(n – 1)
测试
print(factorial(5)) # 输出: 120
print(factorial(0)) # 输出: 1

2. 分治：化繁为简的算法策略

分治（Divide and Conquer）是一种重要的算法设计范式，其核心思想是：

2.1 分治算法的经典应用

• 归并排序（Merge Sort）
• 快速排序（Quick Sort）
• 二分查找（Binary Search）
• 最近点对问题
• 大整数乘法

3. 递归与分治的结合：归并排序实战

归并排序完美体现了递归与分治的结合：

def merge_sort(arr):
"""归并排序实现"""
# 基线条件：数组长度为0或1时已有序
if len(arr) <= 1:
return arr
# 分：将数组平分为两半
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
治：递归排序左右两半
left_sorted = merge_sort(left_half)
right_sorted = merge_sort(right_half)
合：合并两个有序数组
return merge(left_sorted, right_sorted)
def merge(left, right):
"""合并两个有序数组"""
result = []
i = j = 0
while i &lt; len(left) and j &lt; len(right):
if left[i] &lt; right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
添加剩余元素
result.extend(left[i:])
result.extend(right[j:])
return result
测试归并排序
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(f"原始数组: {arr}")
print(f"排序后: {sorted_arr}")

4. 递归的陷阱与优化

4.1 递归深度限制

Python默认递归深度限制为1000层，超过会引发RecursionError。

import sys
print(f"当前递归深度限制: {sys.getrecursionlimit()}")

4.2 尾递归优化

Python不支持尾递归优化，但可以通过循环或迭代器模拟：

def factorial_iterative(n):
"""阶乘的迭代实现"""
result = 1
for i in range(2, n + 1):
result *= i
return result
def factorial_tail_recursive(n, accumulator=1):
"""阶乘的尾递归形式（Python不会优化）"""
if n == 0:
return accumulator
return factorial_tail_recursive(n – 1, n * accumulator)

4.3 记忆化（Memoization）优化

from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n):
"""使用记忆化优化的斐波那契数列"""
if n <= 1:
return n
return fibonacci(n – 1) + fibonacci(n – 2)
测试
print(f"fibonacci(10) = {fibonacci(10)}")
print(f"fibonacci(30) = {fibonacci(30)}") # 无记忆化时会非常慢

5. 分治算法的时间复杂度分析

分治算法的时间复杂度通常可以用主定理（Master Theorem）分析：

6. 实战应用：快速排序实现

def quick_sort(arr):
"""快速排序实现"""
if len(arr) <= 1:
return arr
# 选择基准元素
pivot = arr[len(arr) // 2]
分：将数组分为三部分
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
治和合：递归排序并合并
return quick_sort(left) + middle + quick_sort(right)
测试快速排序
arr = [64, 34, 25, 12, 22, 11, 90]
print(f"排序前: {arr}")
print(f"排序后: {quick_sort(arr)}")

7. 总结与最佳实践

7.1 何时使用递归/分治？

• 使用递归：问题具有自相似性，可以分解为相同结构的子问题。
• 使用分治：问题可以分解为独立的子问题，且子问题的解可以合并。

7.2 注意事项

7.3 扩展学习

掌握了递归和分治的基础后，可以进一步学习：

• 动态规划（Dynamic Programming）
• 回溯算法（Backtracking）
• 树的遍历算法（前序、中序、后序）
• 图算法中的深度优先搜索（DFS）