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

2026-09-04 14:46:28作者：仰钰奇

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

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

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

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

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

基例：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 的情况。

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

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

务必定义基例。没有基例的递归会永远执行下去（在有限内存下表现为栈溢出崩溃）。这是面试白板代码最常见的低级错误。
递归是排列/组合与树形问题的利器。递归天生适合"生成所有组合"，因此你应当会：生成一个序列的所有排列（permutation），以及处理重复元素的去重技巧。仓库中的 QuestionGroups.json 也把 Permutations 归类到 recursion 主题下并标注了 backtracking（回溯）惯例，印证了"递归 + 回溯"是排列/子集类题目的标准组合。
递归隐式使用栈，且永远不是 O(1) 空间。三个要点：
- 所有递归解法都可以用显式栈改写为迭代解法；
- 警惕递归层数过深导致的栈溢出——文档特别指出 Python 的默认递归限制是 1000 层；
- 递归涉及调用栈，因此空间复杂度不可能是 O(1)，除非语言支持尾调用优化（TCO, tail-call optimization）。文档建议提前搞清楚你所选语言是否支持 TCO（提示：主流面试语言 Python、Java、C++ 均无 TCO 保证，JavaScript 引擎部分支持但不建议依赖）。主动向上面试官指出潜在栈溢出风险是文档给出的"加分项"。
基例数量由递归步长决定。观察斐波那契例子：递归调用中出现了 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）——学习该专题时应当优先练习：

题目	递归角色
Generate Parentheses（生成括号）	用"当前合法左/右括号数"作为递归状态，回溯生成所有合法串
Combinations（组合）	从起始下标递归选取，枚举所有 k 个元素的组合
Subsets（子集）	每到一个元素做"选/不选"的二叉递归树

进阶练习题（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）。它们与本文题目清单的关系是：仓库给出的是"题面 + 技巧"，这些课程提供的是"按模式分批练习 + 分语言样例与可视化"，可按需选择，不影响使用仓库本身免费完成递归专题的准备。