tech-interview-handbook 递归（Recursion）面试学习指南：从斐波那契到排列生成，吃透基例、记忆化与栈安全

tech-interview-handbook 递归（Recursion）面试学习指南：从斐波那契到排列生成，吃透基例、记忆化与栈安全

【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook

递归是面试算法题中最基础也最容易被忽视细节的解题范式：本文以 tech-interview-handbook 仓库中的递归专题文档（recursion.md）为主线，系统梳理递归函数的两大组成部分、基例数量的判定规则、记忆化（Memoization）优化原理，并结合仓库内真实的递归源码（排序、树遍历、图 DFS）说明"递归 ↔ 显式栈"的等价改写，读完后可直接套用到面试中递归题的书写、复杂度分析与防栈溢出检查。

递归的定义与两个不可缺少的组成部分

按照文档的定义，递归（Recursion）是一种求解计算方法的方式：当前问题的解依赖于同一问题的更小实例的解。每一个递归函数都包含两部分，缺一不可：

1. 基例（base case）：定义递归何时停止——没有基例，递归会无限进行下去；
2. 问题分解与递归调用：把问题拆成更小的子问题，并对子问题发起递归调用。

文档以最经典的斐波那契序列为例给出了完整的"基例 + 递推关系"结构：

• 基例：fib(0) = 0和fib(1) = 1
• 递推关系：fib(i) = fib(i - 1) + fib(i - 2)

def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)

面试中大量算法都重度依赖递归：二分查找、归并排序、树的遍历、深度优先搜索（DFS）等。文档明确指出，专题聚焦的是使用递归但不属于其他已知经典算法的那类题目（例如排列/组合/子集生成、数独求解等），因为二分、排序、树遍历等在其他专题中已有覆盖。

仓库源码印证：真实的递归实现

仓库apps/website/experimental/utilities目录下保留了若干可直接运行的递归实现，是检验上面两大组成部分的极好样本：

归并排序（mergeSort.js）：基例是"长度小于 2 的数组天然有序"（arr.length < 2时直接返回），分解方式是切成左右两半分别递归后再merge：

function mergeSort(arr) { if (arr.length < 2) { // Arrays of length 0 or 1 are sorted by definition. return arr; } const left = arr.slice(0, Math.floor(arr.length / 2)); const right = arr.slice(Math.floor(arr.length / 2), Math.floor(arr.length)); return merge(mergeSort(left), mergeSort(right)); }

该文件末尾附带了 7 组断言式测试（用deepEqual比对空数组、单元素、逆序、含负数等输入），这正是"写完递归后用几组样例输入验证"的落地做法，覆盖了n = 0这类最容易漏掉的角落。

双节点同时递归（tree_equal.py）：判断两棵二叉树是否相等，一次调用同时推进两个子问题（左子树对左子树、右子树对右子树）：

def tree_equal(node1, node2): if not node1 and not node2: return True if not node1 or not node2: return False return node1.val == node2.val and \ tree_equal(node1.left, node2.left) and \ tree_equal(node1.right, node2.right)

它体现了文档强调的另一细节：基例不止一个（两者皆空、恰好一个为空），且要覆盖输入范围内所有可能的调用路径。

图搜索中的内嵌递归（graph_dfs.py）：在一个矩阵上实现递归 DFS，内部函数dfs(i, j)以visited集合防止重复访问，再按四个方向递归展开邻居：

def dfs(i, j): if (i, j) in visited: return visited.add((i, j)) for direction in directions: next_i, next_j = i + direction[0], j + direction[1] if 0 <= next_i < rows and 0 <= next_j < cols: # Check boundary. dfs(next_i, next_j)

从源码结构看，凡是递归遍历有环结构的图/矩阵，几乎都伴随一个 visited 状态集——这与 graph.md 中的提示一致："树形图也可能是允许环的图，朴素的递归解法在环上会失败，必须处理环并维护已访问节点集合"。树专题（tree.md）同样指出：每个节点都可以看作其子树的根节点，因此递归是树遍历的自然选择，且基例通常是节点为null的情况。

面试中需要注意的要点（文档核心清单）

原文档列出了四条面试注意事项，每一条都值得在考场上逐项自查：

1. 务必定义基例。没有基例的递归会永远执行下去（在有限内存下表现为栈溢出崩溃）。这是面试白板代码最常见的低级错误。

2. 递归是排列/组合与树形问题的利器。递归天生适合"生成所有组合"，因此你应当会：生成一个序列的所有排列（permutation），以及处理重复元素的去重技巧。仓库中的 QuestionGroups.json 也把 Permutations 归类到recursion主题下并标注了backtracking（回溯）惯例，印证了"递归 + 回溯"是排列/子集类题目的标准组合。

3. 递归隐式使用栈，且永远不是 O(1) 空间。三个要点：

   • 所有递归解法都可以用显式栈改写为迭代解法；
   • 警惕递归层数过深导致的栈溢出——文档特别指出Python 的默认递归限制是 1000 层；
   • 递归涉及调用栈，因此空间复杂度不可能是 O(1)，除非语言支持尾调用优化（TCO, tail-call optimization）。文档建议提前搞清楚你所选语言是否支持 TCO（提示：主流面试语言 Python、Java、C++ 均无 TCO 保证，JavaScript 引擎部分支持但不建议依赖）。主动向上面试官指出潜在栈溢出风险是文档给出的"加分项"。

4. 基例数量由递归步长决定。观察斐波那契例子：递归调用中出现了fib(n - 2)，说明递归会"跳过"n - 1，因此需要2 个基例（fib(0)与fib(1)）才能覆盖所有可能的调用；如果递归函数只调用fn(n - 1)，则只需要 1 个基例。可以推断：凡是递归中有n - k的跳转，就要准备k个（或足够的）基例。tree_equal中"同时递归两个节点"也需要同时覆盖两个子问题各自的全部终止条件，是同一原则在多维递归上的体现。

角落用例（Corner cases）

文档明确列出递归题必须覆盖的角落：

• n = 0
• n = 1
• 确保基例数量足以覆盖递归函数的所有可能调用。

对照仓库中的实现可以看到这套检查清单的实用性：mergeSort.js 的测试用例第一组就是mergeSort([])（空输入）与mergeSort([1])（单元素），即恰好对应n = 0与n = 1。写递归函数时的自查顺序建议为：先列基例 → 再列n = 0 / n = 1 / 空集合的输入 → 最后验证递推一步是否严格让问题规模变小。

技术：记忆化（Memoization）

文档指出的核心浪费来源是重复计算：fib(5)会调用fib(4)和fib(3)，而fib(4)又调用fib(3)和fib(2)——fib(3)被计算了两次。不加优化时斐波那契的时间复杂度约为指数级O(2^n)（调用树近似满二叉树）。把已算过的结果缓存（memoize）后，每个fib(i)只计算一次，时间复杂度降为O(n)。

def fib(n, memo={}): if n <= 1: return n if n in memo: return memo[n] memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n]

从复杂度视角看：朴素版本满足递推T(n) = T(n - 1) + T(n - 2) + O(1)，其解呈指数增长；记忆化后状态空间只有n个、每个状态转移 O(1)，故为O(n)时间、O(n)空间（memo 表 + 栈深度各一份 O(n)）。需要强调：记忆化只改时间复杂度，调用栈仍在，因此空间复杂度依然是 O(n) 而非 O(1)，这与上一节"递归永远不是 O(1) 空间"的论断完全一致。记忆化是"自顶向下 DP"的基本形态，也是递归与动态规划专题之间的桥梁——coding-interview-study-plan.md 中亦提到"很多动态规划题其实可以用递归/回溯求解"。

递归 ↔ 迭代：用显式栈改写

文档断言"所有递归解法都可以用栈改写为迭代"。仓库中的 tree_traversal.py 给出了三种遍历（in-order / pre-order / post-order）的纯迭代版本，直接可用以印证：

def preorder_traversal(root): if not root: return [] result = [] stack = [root] while len(stack) > 0: curr_node = stack.pop() result.append(curr_node.val) if curr_node.right: stack.append(curr_node.right) if curr_node.left: stack.append(curr_node.left) return result

注意栈操作的对称性：pre-order 中先压右子树再压左子树（保证左子树先出栈），而 in-order / post-order 的版本通过临时把节点指针置空来记录"左/右子树是否已访问"，以此在单栈上模拟递归的多段执行状态。从源码结构看，这类改写通常用于两种面试场景：一是递归深度可能超限时（例如退化为链状的"树"，深度为 O(n)）主动改用迭代；二是面试官在你快速写完递归版本后追问"能不能写成迭代"，tree.md 明确提到"面试官有时会在你太快写完递归解法后要求给出迭代版本"。

题目清单：必练题与进阶练习题

文档将练习分为两档，以下完整继承原文档的清单（题面链接请自行在 LeetCode 中检索同名题目）：

必练题（Essential questions）——学习该专题时应当优先练习：

进阶练习题（Recommended practice questions）——在掌握必练题之后继续刷：

• Letter Combinations of a Phone Number（电话号码的字母组合）
• Subsets II（子集 II，处理重复元素）
• Permutations（全排列）
• Sudoku Solver（数独求解）
• Strobogrammatic Number II（日志数 II，LeetCode Premium）

其中 Permutations 在仓库的 QuestionGroups.json 中被标记为 Medium 难度、建议用时约 30 分钟、主题recursion、惯例backtracking，是"递归 + 处理重复"要点的最直接练习。

学习路径定位与资源

• 在 study-cheatsheet.md 的专题优先级表中，Recursion 的优先级为Mid，与链表、栈、堆等并列，属于"必须准备但次于数组/字符串/树/图"的专题；
• 在 coding-interview-study-plan.md 中，Recursion 的建议学习时长约为3 小时；
• 仓库文档还引用了两份外部学习材料：University of Utah 的 Recursion 阅读材料，以及 University of Washington 关于 Tail Recursion 的视频课程（分别对应"递归基础"与"TCO 原理"两个知识缺口）。

关于课程推荐，原文档通过 AlgorithmCourses.md 组件引入了三个付费课程：AlgoMonster（按次付费终身访问）、Grokking the Coding Interview: Patterns for Coding Questions（Design Gurus，按题型模式组织练习）、Master the Coding Interview: Data Structures + Algorithms（Udemy）。它们与本文题目清单的关系是：仓库给出的是"题面 + 技巧"，这些课程提供的是"按模式分批练习 + 分语言样例与可视化"，可按需选择，不影响使用仓库本身免费完成递归专题的准备。

小结

递归专题的备考可以浓缩为一条自查链路：

1. 写下递推关系后，先按"递归步长是n - k还是多维"确定基例数量；
2. 用n = 0、n = 1、空输入三类角落用例自测（参考 mergeSort.js 的断言式验证方式）；
3. 若子问题重叠（如斐波那契），主动提出记忆化，把指数时间降到 O(n)，并正确陈述 O(n) 的空间开销；
4. 主动评估调用深度：链状结构 + 千级输入可能触发 Python 1000 层递归限制，准备好显式栈的迭代改写（参考 tree_traversal.py）；
5. 排列/子集类题目默认"递归 + 回溯 + 去重"三件套，按仓库题目清单从必练题刷起。

掌握以上五步，即可覆盖 recursion.md 文档的全部要点，并与仓库中 graph、tree、stack 等相邻专题的知识互通。

【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook