很多初学者觉得递归难,是因为试图"一步步跟踪"它的执行过程。正确姿势恰恰相反:递归要求你信任函数本身。本文帮你建立递归的心智模型,并顺势理解它最强大的应用——分治。
1. 什么是递归
递归就是"函数调用自己"。一个递归问题必须包含两部分:
- 基线条件:问题小到可以直接给出答案,不再调用自己。
- 递归步骤:把问题缩小,调用自己解决,再组合结果。
没有基线条件就是无限递归,程序直接栈溢出。
2. 第一个例子:阶乘
def factorial(n):
if n <= 1: # 基线条件
return 1
return n * factorial(n - 1) # 缩小规模,信任递归结果
print(factorial(5)) # 120写递归只问三件事:基线条件对吗?规模缩小了吗?组合逻辑对吗?不要纠结内部执行细节,相信递归已经算好了。
3. 递归三要素
- 明确职责:函数接收什么、返回什么,一句话说清。
- 找出基线:问题最小时怎么处理。
- 递推关系:大问题如何由小问题组合而成。
以二叉树遍历为例:遍历一棵树 = 访问根 + 遍历左子树 + 遍历右子树,天然适合递归。
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def inorder(root): # 中序遍历:左 → 根 → 右
if root is None:
return []
return inorder(root.left) + [root.val] + inorder(root.right)
root = TreeNode(1) # 根为 1,左右孩子 2、3
root.left = TreeNode(2)
root.right = TreeNode(3)
print(inorder(root)) # [2, 1, 3]4. 递归的代价
递归并非免费:每次调用都要压栈,占用 O(深度) 的栈空间;重复子问题还会导致指数级浪费。朴素斐波那契就是经典反例:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
# fib(45) 要跑几十秒:同一个子问题被反复计算
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_fast(n):
if n <= 1:
return n
return fib_fast(n - 1) + fib_fast(n - 2)
print(fib_fast(100)) # 瞬间完成lru_cache 即记忆化:缓存已算结果,把指数级降到 O(n),也是通往动态规划的桥梁。
5. 分治:递归的杀手级应用
分治三步:分解成互不重叠的子问题 → 递归解决 → 合并结果。快排、归并、二分都是分治,以归并排序为例:
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(a, b):
i = j = 0
res = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
res.append(a[i]); i += 1
else:
res.append(b[j]); j += 1
return res + a[i:] + b[j:]
print(merge_sort([5, 1, 4, 2, 8])) # [1, 2, 4, 5, 8]💡 学习建议:遇到递归题,先大声说出"职责 + 基线 + 递推"三要素再写代码;平时用"递归转迭代"练习加深理解,面试常考。