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）是一种重要的算法设计范式，其核心思想是：

1. 分（Divide）：将原问题分解为若干个规模较小的子问题。
2. 治（Conquer）：递归地解决各个子问题。
3. 合（Combine）：将子问题的解合并为原问题的解。

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 注意事项

1. 确保递归有明确的终止条件
2. 注意递归深度和栈溢出风险
3. 对于重叠子问题，考虑使用记忆化优化
4. 分治算法中，子问题应尽可能独立
5. 合理选择基准元素（如快速排序中的pivot）

7.3 扩展学习

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

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