递归与回溯：从递归树到剪枝

0. 元信息

• 主题路径：docs/topics/algo-design/subtopics/recursion-and-backtracking/README.md
• 父主题：algo-design
• 主分类：数据结构与算法
• 辅助分类：编程语言
• 适合对象：掌握 Python 控制流与列表字典、会写简单函数；想搞懂递归底层并独立完成回溯题的学习者
• 建议周期：1.5～2 周（每周 8～12 小时）
• 前置知识：Python 基础（lang-python）、高中数学（排列组合）、基本数据结构（栈）
• 最终目标：能在 25 分钟内独立写出排列 / 组合 / 子集类回溯题，能估算分支因子并加上剪枝，能解释调用栈每一步发生什么

1. 学习路线

递归调用栈与终止条件
  → 数学归纳与递归正确性
  → 回溯模板（选 / 不选 + 撤销）
  → 排列 / 组合 / 子集三连
  → 剪枝（行级、对角线、上界）
  → N 皇后 / 数独 / 单词搜索

每一步都跟一道题。先把递归树画出来，再写代码。

2. 阶段周数分配

每天 1.5～2 小时。1.5 周方案专注前 5 阶段；2 周方案多 2 天做复盘与错题重写。

3. 九阶段表（精简）

3.1 核心知识

• 调用栈：每次递归调用 = 压栈，return = 弹栈；栈帧保存参数、局部变量、返回地址。
• 终止条件（base case）：没有终止条件 = 无限递归 = Python RecursionError（默认 1000 层）。
• 数学归纳：递归 = 假设子问题已解 + 当前一步构造；正确性靠归纳证明。
• 回溯模板：选 → 递归 → 撤销（path.pop() / visited[i] = False）。
• 剪枝：递归前判断能不能继续；剪错会 WA，剪不够会 TLE。
• Python 性能：functools.lru_cache 是递归 memoization 的最简方式；回溯题不用 cache。

3.2 实践产出

• 8 道递归基础（阶乘、斐波那契、汉诺塔、阶乘和、递归求和、二分查找、链表的 reverse、pow(x,n)）；
• 8 道回溯模板题（46 全排列、78 子集、39 组合总和、40 组合总和 II、77 组合、47 全排列 II、22 括号生成、79 单词搜索）；
• 3 道剪枝难题（51 N 皇后、37 数独解、140 单词拆分 II）。

3.3 可观察学会标准

• 不看答案在 25 分钟内写完 46 / 78 / 77 三连；
• 能在 5 分钟内画出一道题的递归树并标出分支因子；
• N 皇后能写出”行级 + 列级 + 主对角线 + 副对角线”四种剪枝。

4. 第一周（每天 1.5~2 小时）

Day 1 约定：本计划使用 Python 3.10+。统一格式：python -X dev -W error -m py_compile foo.py 做静态检查；运行用 python foo.py < input.txt；测试用 pytest。所有代码放进 algo-design/recursion/week<N>/ 目录；每个题目单独 .py 文件，配套 notes/<problem>.md 含递归树图与复杂度推导。

Day 7 执行次序

步骤 A —— N 皇后完整版（60~90 分钟）

1. 写 solve_n_queens(n) 返回所有解；
2. 画 n=4 的递归树（带剪枝后）；
3. 跑 n=8 输出 92 解；
4. 记录 n=4, 6, 8, 10 的耗时。

步骤 B —— 4 类边界用例（30~45 分钟）

Day 7 当天必完成步骤 A；步骤 B 至少完成 B1、B3。

5. 阶段通用验收（精简）

1. 不看答案重写 8 道回溯模板；
2. 用自己的话解释递归调用栈每一步发生什么；
3. 画出 N 皇后的递归树（含剪枝后）；
4. 测试 n=0、n=1、n=4、n=8、n=10 时的运行时间和分支数；
5. 至少准备 3 组自定义数据贴出实际输出；
6. 记录每题的时间空间复杂度；
7. 能给现有回溯加新剪枝条件。

6. 最终验收

• 独立实现：8 道回溯模板（46 / 47 / 78 / 90 / 77 / 39 / 40 / 22）、3 道剪枝难题（51 N 皇后、37 数独、212 单词搜索 II）；

• 至少完成 19 道题（LeetCode / Codeforces），分布建议：

  子阶段	题目数量	难度分布	平台建议
  递归基础	4 道	4 Easy	LeetCode 509 / 70 / 50 / Pow(x,n)
  回溯模板	6 道	4 Easy + 2 Medium	LeetCode 46 / 78 / 77 / 39 / 40 / 22
  去重回溯	3 道	1 Easy + 2 Medium	LeetCode 47 / 90 / 491
  字符串 / 网格	3 道	1 Medium + 2 Hard	LeetCode 79 / 212 / 140
  剪枝难题	3 道	1 Hard + 2 Medium	LeetCode 51 / 37 / 52

  约束：至少 6 道达到 Medium，至少 3 道达到 Hard；N 皇后必须能在 25 分钟内重写 4 种剪枝。

• 完成 1 个综合 Python 项目（自带 README，能被他人按文档复现）；

• 能用 15 分钟讲清递归调用栈、回溯模板三连、剪枝四件套（行 / 列 / 主对角 / 副对角）、去重条件写法。

7. 综合项目

首选：回溯算法可视化工具（必做：CLI 输入题目 + 输出回放 + 可选 GUI）。
备选：N 皇后求解器 + 递归树导出（输入 n → 输出所有解 + 递归树 DOT 文件 + Graphviz 渲染）。
备选：回溯题模板生成器（给定题型关键词 → 输出 Python 模板：选 / 不选 + 撤销 + 剪枝条件）。

回溯算法可视化工具必做要求：

• 输入：stdin 接收算法名（n_queens / combination_sum / permutations / sudoku / word_search）+ 数据集（n 或网格）；
• 输出：必输出（1）算法过程的文字回放（每一步状态、当前下标、做了什么操作）；（2）时间 / 空间复杂度 + 实际耗时；（3）解的总数 / 解集；（4）递归调用栈每一步快照（栈帧表）；
• 算法：必须用至少 2 种范式（递归 + 回溯）；支持剪枝开关（开 / 关对比耗时）；
• 进阶可选：ASCII 动画（终端 curses 逐步展开）、matplotlib 画递归树 GUI、可对比两种剪枝策略的可视化。

任何综合项目都必须包含：

1. 需求说明（含输入输出约定）；
2. 数据结构与算法选择理由（为何用递归 + 回溯、为何选这种剪枝）；
3. 核心模块说明（Solver / Recorder / Renderer 三层）；
4. 模块化源码（每题单独文件 + 公共 base class）；
5. 边界测试（n=0, 1, 2, 8, 10 + 网格空 + 网格满）；
6. 运行说明（Makefile 或清晰的 python -m 命令）；
7. README（项目介绍、运行步骤、目录结构、复盘）；
8. notes/ 规范：

本主题贡献

3 职责

1. 把”问题可分解性”显式化为递归栈帧表 —— 每层栈帧保存什么（参数 + 局部变量 + 返回地址）、什么时候压栈 / 弹栈、RecursionError 的触发边界（默认 1000 层，setrecursionlimit(200000) 后才能稳定跑 N=10 的 N 皇后）。
2. 给出可移植的”选 → 递归 → 撤销”回溯模板 —— path + used + start 三件套；并能针对子集树（if i > start and nums[i] == nums[i-1]: continue 去重）和排列树（used[i] 标记已访问）切换不同的去重条件与剪枝触发点。
3. 用可视化验证递归树与剪枝收益 —— 行级 / 列级 / 主对角线 col - row / 副对角线 col + row 四种剪枝在 N 皇后上对比”加 / 不加”耗时差异（n=20 时应 ≥ 10x），并把递归栈快照存到 notes/stack-traces/。

4 交付物

1. 19 道题解（8 入门递归 + 8 回溯模板 + 3 剪枝难题）+ 4 类边界用例日志（n=0 返回 [[]] / n=1 单解 / n=2 / n=3 无解 / n=10 全解）。
2. 回溯算法可视化工具（CLI → 算法名 + 数据集 → 输出文字回放 + 递归栈每一步快照 + 解集总数）+ 至少 3 题的子集树 / 排列树 DOT 文件。
3. 4 个回溯模板的 Python 代码（46 全排列 / 78 子集 / 77 组合 / 39 组合总和）落到 notes/algorithm-templates/，每个模板独立标注”撤销时机”与”去重条件”。
4. 剪枝收益对比表 notes/pruning-comparison.md（行级、列级、主对角线、副对角线、上界剪枝五类的耗时 ×10 差距证据）。

3 指标

1. 不看答案 25 分钟内独立完成 46 / 78 / 77 三连（覆盖”选 / 不选 + 撤销”模板的全部变体与去重边界）。
2. N 皇后 n=10 在 < 5s 内跑完 724 解（验证四种剪枝叠加后的实际收益，证明 Word Search / 数独 / N 皇后剪枝套路已可迁移）。
3. 任意一道回溯题 5 分钟内画完递归树 + 标出分支因子（说明递归树的”形状分析”已固化为肌肉记忆，能在编码前估时间复杂度）。

许可证提示：Manber 自学合理引用；CP-Algorithms 是 CC BY-SA；LeetCode 题面版权见 LeetCode Terms of Service——代码自己写，思路可以分享；AtCoder / USACO Guide 题面公开。默认做法是读思路后自己写代码，而不是复制 Editorial 代码。

默认使用顺序：先用 labuladong 回溯框架建立模板感 → 自己写 46 / 78 / 77 三连 → 对照 CP-Algorithms 看反例与去重 → 用 LeetCode 刷 12 道（按 tag） → 跑 51 N 皇后 4 种剪枝 → 用 Algorithm Visualizer / VisuAlgo 验证递归树 → 选 Manber 第 1~2 章做归纳思维训练 → 写复盘到 notes/retrospective.md。

8. 推荐开源资料

许可证提示：Manber 自学合理引用；CP-Algorithms 是 CC BY-SA；LeetCode 题面版权见 LeetCode Terms of Service——代码自己写，思路可以分享；AtCoder / USACO Guide 题面公开。默认做法是读思路后自己写代码，而不是复制 Editorial 代码。

默认使用顺序：先用 labuladong 回溯框架建立模板感 → 自己写 46 / 78 / 77 三连 → 对照 CP-Algorithms 看反例与去重 → 用 LeetCode 刷 12 道（按 tag） → 跑 51 N 皇后 4 种剪枝 → 用 Algorithm Visualizer / VisuAlgo 验证递归树 → 选 Manber 第 1~2 章做归纳思维训练 → 写复盘到 notes/retrospective.md。

9. 学习资料汇聚（v0.3）

9.1 背景与动机

递归诞生于 1930 年代 lambda 演算与可计算性研究。McCarthy 在 1958 年的 LISP 中把递归作为核心控制结构。1970 年代 Knuth 在 TAOCP 把回溯作为组合搜索的标准方法。N 皇后是 1848 年由 Max Bezzel 提出、1970 年代成为回溯教学题。

行业位置：回溯是中等难度面试常考题（LeetCode 22 / 39 / 46 / 47 / 78 / 79）；竞赛里是 DFS 搜状态空间的核心。不会递归与回溯，后续 DP / 分治都没法谈。一句话总结：递归是算法的递归，DP 是带记忆的递归，分治是互不重叠的递归。

9.2 概念地图

flowchart LR
  CallStack[调用栈]
  BaseCase[终止条件]
  Induction[数学归纳]
  Backtrack[回溯模板]
  Permutation[排列]
  Combination[组合]
  Subset[子集]
  Pruning[剪枝]
  NQueens[N 皇后]
  Sudoku[数独]
  WordSearch[单词搜索]
  CallStack --> BaseCase
  BaseCase --> Induction
  Induction --> Backtrack
  Backtrack --> Permutation
  Backtrack --> Combination
  Backtrack --> Subset
  Backtrack --> Pruning
  Pruning --> NQueens
  Pruning --> Sudoku
  Backtrack --> WordSearch

核心关系：调用栈是底座 → 终止条件防爆栈 → 数学归纳证明正确性 → 回溯模板三连 → 剪枝去掉不可能分支。

9.3 基础知识讲解

9.3.1 经典论文

9.3.2 经典书籍

9.3.3 优秀博客

9.3.4 核心人物

9.3.5 开发方法

9.4 经典问题与经典案例

9.5 学习难点

概念难点

思维难点

工程难点

9.6 技术标准与接口

9.6.1 Entity

9.6.2 Scope

• Python 默认递归深度 1000；超过需 setrecursionlimit。
• lru_cache 仅用于纯函数；回溯题通常不需要 cache，但分支爆炸时可加。
• 回溯模板适用：组合搜索、N 皇后、数独、子集划分、字符串生成。
• 不适用：最短路（Dijkstra）、最大流（Ford-Fulkerson）、动态规划（带 memo）。

9.6.3 Structure

• 经典模板：def dfs(path, used): if len(path) == n: res.append(path[:]); return; for i in range(n): if used[i]: continue; path.append(nums[i]); used[i]=True; dfs(path, used); path.pop(); used[i]=False
• 必须掌握的字段：path、used、start、剪枝条件、终止条件。
• 必须掌握的方法：先画递归树，再编码；先写暴力，再加剪枝；测试 n=0/1/小/中/大五档。

9.6.4 Ecosystem

• 工具：itertools.permutations / combinations 用于验证；copy.deepcopy 用于需要路径拷贝的场景。
• 在线评测：LeetCode、AtCoder、Codeforces。
• 训练集：LeetCode Hot 100 中回溯题；CSES Introductory Problems 部分题。

9.6.5 Depth Tiers

本子主题目标：L3。N 皇后 / 数独 / 单词搜索做对即达到。

9.6.6 Source

• Python 文档 · sys.setrecursionlimit：递归限制设置。
• CP-Algorithms · Backtracking：模板与例题。
• labuladong 回溯框架：中文框架讲解。
• 引用版本快照日期：2026-07-30。LeetCode 题目 ID 稳定，但 Editorial 可能更新。

10. 常见误区

• 终止条件写错位置，导致漏解或多解；
• 撤销时忘了 used[i] = False 或 path.pop()；
• 排列忘了 start 参数或 used 数组；
• 组合里去重条件写反（i > start vs i > 0）；
• N 皇后用三个 set 维护对角线，忘了 col - row 是同一主对角线、col + row 是同一副对角线；
• 单词搜索时回溯时忘了把 visited[i][j] = False；
• 递归深度超 1000 直接放弃，不知道 setrecursionlimit；
• 不画递归树就硬写，靠调试看行为；
• 把回溯和动态规划混用，结果两种范式都没用上；
• 剪枝条件不充分，TLE 后直接放弃，忘了可以加排序去重；
• 字符串拼接用 path + char 导致 TLE；
• 全局变量在多组测试间污染，不重置；
• 写完不复盘，下周遇到同类型还是不会。

11. 所有知识点分类

1. 编程语言（辅）：Python 列表 / 字典、path.append + path.pop 撤销、sys.setrecursionlimit、functools.lru_cache、itertools.permutations / combinations 验证。
2. 数据结构与算法（主）：调用栈与栈帧、终止条件与数学归纳、回溯模板（选 / 不选 + 撤销）、排列 / 组合 / 子集、剪枝（行级 / 列级 / 对角线 / 上界）、N 皇后 / 数独 / 单词搜索 / 括号生成。
3. 计算机基础：栈内存模型、过程调用与返回地址、递归的数学归纳证明、排列组合计数。
4. 工程技术：复杂度分析（分支因子 × 叶子数）、画递归树、撤销与状态恢复、避免全局变量污染、剪枝验证流程。
5. Web 与后端：无直接关联。
6. 前端与客户端：无直接关联。
7. 数据与人工智能：无直接关联（回溯可作为搜索子模块，但本计划不展开）。
8. 项目与职业能力：LeetCode 22 / 39 / 46 / 47 / 51 / 78 / 79 等高频面试题的解题节奏、25 分钟独立完成模板题、5 分钟画递归树并标分支因子。

本计划归属：数据结构与算法 主 + 编程语言 辅。