第七章：递归与回溯

本章目标

本章学习递归和回溯。递归把问题交给更小规模的自己，回溯在搜索树中枚举所有选择。

你会理解 base case、递归关系，以及 choose/search/undo 的回溯结构。

核心概念

递归必须有终止条件，否则会无限调用。树递归常把一个问题拆成多个子问题，再合并结果。

回溯适合排列、组合、子集、棋盘搜索。剪枝是在确定某条路径不可能产生答案时提前返回。

Python 示例

阶乘展示了最简单的递归结构。

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

排列问题体现 choose/search/undo：选择一个未使用元素，递归搜索，再撤销选择。

def permutations(nums):
    ans, path, used = [], [], [False] * len(nums)

    def dfs():
        if len(path) == len(nums):
            ans.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return ans

复杂度与常见误区

递归复杂度取决于递归树。全排列有 n! 个结果，时间复杂度至少是 O(n!)，保存结果也需要大量空间。

常见误区是忘记复制 path。把同一个列表直接加入答案，后续 undo 会修改已经保存的结果。

本章要点

递归先写终止条件，再写子问题关系；回溯先定义状态，再定义每层有哪些选择。

剪枝可以显著减少搜索，但不能改变问题最坏情况下的指数级本质。