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是一种求解计算方法的方式当前问题的解依赖于同一问题的更小实例的解。每一个递归函数都包含两部分缺一不可基例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时直接返回分解方式是切成左右两半分别递归后再mergefunction 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 0n 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日志数 IILeetCode 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 QuestionsDesign Gurus按题型模式组织练习、Master the Coding Interview: Data Structures AlgorithmsUdemy。它们与本文题目清单的关系是仓库给出的是题面 技巧这些课程提供的是按模式分批练习 分语言样例与可视化可按需选择不影响使用仓库本身免费完成递归专题的准备。小结递归专题的备考可以浓缩为一条自查链路写下递推关系后先按递归步长是n - k还是多维确定基例数量用n 0、n 1、空输入三类角落用例自测参考 mergeSort.js 的断言式验证方式若子问题重叠如斐波那契主动提出记忆化把指数时间降到 O(n)并正确陈述 O(n) 的空间开销主动评估调用深度链状结构 千级输入可能触发 Python 1000 层递归限制准备好显式栈的迭代改写参考 tree_traversal.py排列/子集类题目默认递归 回溯 去重三件套按仓库题目清单从必练题刷起。掌握以上五步即可覆盖 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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是一种求解计算方法的方式当前问题的解依赖于同一问题的更小实例的解。每一个递归函数都包含两部分缺一不可基例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时直接返回分解方式是切成左右两半分别递归后再mergefunction 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 0n 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日志数 IILeetCode 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 QuestionsDesign Gurus按题型模式组织练习、Master the Coding Interview: Data Structures AlgorithmsUdemy。它们与本文题目清单的关系是仓库给出的是题面 技巧这些课程提供的是按模式分批练习 分语言样例与可视化可按需选择不影响使用仓库本身免费完成递归专题的准备。小结递归专题的备考可以浓缩为一条自查链路写下递推关系后先按递归步长是n - k还是多维确定基例数量用n 0、n 1、空输入三类角落用例自测参考 mergeSort.js 的断言式验证方式若子问题重叠如斐波那契主动提出记忆化把指数时间降到 O(n)并正确陈述 O(n) 的空间开销主动评估调用深度链状结构 千级输入可能触发 Python 1000 层递归限制准备好显式栈的迭代改写参考 tree_traversal.py排列/子集类题目默认递归 回溯 去重三件套按仓库题目清单从必练题刷起。掌握以上五步即可覆盖 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考