递归与回溯：从递归树到剪枝优化
递归是算法面试中最核心的思维方式之一。从树的遍历到动态规划，从回溯搜索到分治算法，递归无处不在。
一、递归的本质
递归 = 重复调用自身 + 终止条件
def recursion(参数):
if 终止条件:
return 基准结果
# 分解问题
子问题结果 = recursion(更小的参数)
# 合并结果
return 合并(子问题结果)
经典示例：阶乘
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
调用栈展开：
factorial(5)
= 5 × factorial(4)
= 5 × (4 × factorial(3))
= 5 × (4 × (3 × factorial(2)))
= 5 × (4 × (3 × (2 × factorial(1))))
= 5 × (4 × (3 × (2 × 1)))
= 120
二、递归树分析
递归树是分析递归算法复杂度的有力工具。
斐波那契的递归树
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
...
问题：大量重复计算，时间复杂度 O(2ⁿ)。
优化：记忆化
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
时间复杂度降为 O(n)，空间 O(n)。
三、尾递归优化
尾递归是递归的特殊形式：递归调用是函数的最后一个操作。
# 非尾递归：递归调用后还要做乘法
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1) # 还有 ×n 操作
# 尾递归：最后操作就是递归调用
def factorial_tail(n, acc=1):
if n <= 1:
return acc
return factorial_tail(n - 1, n * acc)
优势：部分语言（如 Scheme、Erlang）可将尾递归优化为循环，避免栈溢出。Python 不支持尾递归优化。
四、回溯法（Backtracking）
回溯法是递归的重要应用，用于搜索所有（或部分）解空间。
通用模板
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
if 剪枝条件:
continue
做选择
backtrack(路径, 新选择列表)
撤销选择 # 关键！恢复状态
回溯 = DFS + 状态恢复，「撤销选择」是核心。
经典问题 1：全排列（LeetCode 46）
def permute(nums):
result = []
def backtrack(path, used):
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
used[i] = True
path.append(nums[i])
backtrack(path, used)
path.pop()
used[i] = False
backtrack([], [False] * len(nums))
return result
经典问题 2：组合总和（LeetCode 39）
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(path[:])
return
if remaining < 0:
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, remaining - candidates[i]) # 可重复选
path.pop()
backtrack(0, [], target)
return result
经典问题 3：N 皇后（LeetCode 51）
def solve_n_queens(n):
result = []
board = [['.' for _ in range(n)] for _ in range(n)]
def is_valid(row, col):
# 检查同列
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 检查右上
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def backtrack(row):
if row == n:
result.append([''.join(r) for r in board])
return
for col in range(n):
if is_valid(row, col):
board[row][col] = 'Q'
backtrack(row + 1)
board[row][col] = '.'
backtrack(0)
return result
五、剪枝策略
1. 可行性剪枝
如果当前路径不可能到达解，提前返回。
# 组合总和中的剪枝
if remaining < 0:
return # 已经超过目标，无需继续
2. 重复剪枝
处理有重复元素时的重复解问题。
# 组合总和 II（LeetCode 40）：候选有重复，解不能重复
for i in range(start, len(candidates)):
if i > start and candidates[i] == candidates[i - 1]:
continue # 跳过同层相同元素，避免重复
# ...
3. 记忆化剪枝
缓存已计算状态，避免重复搜索。
def can_win(state):
if state in memo:
return memo[state]
# ... 计算 ...
memo[state] = result
return result
六、排列 vs 组合 vs 子集
| 问题 | 顺序重要？ | 可重复？ | 代码特征 |
|---|---|---|---|
| 全排列 | 是 | 否 | used[] 标记，for i in range(n) |
| 组合 | 否 | 否 | start 参数，for i in range(start, n) |
| 子集 | 否 | 否 | 每个节点都收集结果 |
| 组合总和 I | 否 | 是 | backtrack(i) 而非 backtrack(i+1) |
| 组合总和 II | 否 | 否 | 排序 + 去重剪枝 |
七、面试高频问题
| 题号 | 题目 | 类型 |
|---|---|---|
| LeetCode 46 | 全排列 | 排列 |
| LeetCode 47 | 全排列 II（含重复） | 排列 + 去重 |
| LeetCode 77 | 组合 | 组合 |
| LeetCode 78 | 子集 | 子集 |
| LeetCode 39 | 组合总和 | 组合 + 可重复 |
| LeetCode 40 | 组合总和 II | 组合 + 去重 |
| LeetCode 51 | N 皇后 | 棋盘类 |
| LeetCode 37 | 解数独 | 搜索 + 约束 |
| LeetCode 212 | 单词搜索 II | Trie + 回溯 |
八、常见问题
Q: 递归和迭代的区别？
- 递归：代码简洁，有栈溢出风险，天然适合树形结构
- 迭代：效率更高，需手动维护状态（栈/队列）
- 面试建议：递归写法为主，能说出如何改迭代加分
Q: 回溯的时间复杂度怎么算？
通常是指数级 O(kⁿ) 或 O(n!)，但因为剪枝，实际远小于理论上限。
Q: 什么时候用回溯不用 DP？
- 需要「所有方案」→ 回溯
- 只需要「最优解/数量」→ DP 更高效
相关文章：
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。