30 Seconds of Interviews 面试题精讲:JavaScript 递归(Recursion)原理与实战

原创2026-09-22 09:03:531,728 阅读
文章标签:教程前端

30 Seconds of Interviews 面试题精讲:JavaScript 递归(Recursion)原理与实战

导读

本文围绕 30 Seconds of Interviews 开源面试题库中的 递归(Recursion)面试题 展开,系统讲解递归的定义、必备的基准条件(base condition)机制,并给出把扁平数组嵌套成树形结构的完整可运行示例。读完本文,你将掌握递归的判定标准、手写递归函数的正确姿势、递归与迭代的取舍,以及如何在真实的"无限层级评论树"场景中落地递归方案,为 JavaScript 面试与日常开发打下扎实基础。

什么是递归?什么时候该用它?

在 questions/recursion.md 中,该题将递归定义为:

Recursion is the repeated application of a process. In JavaScript, recursion involves functions that call themselves repeatedly until they reach a base condition.

翻译过来即:递归是对同一过程的反复应用。在 JavaScript 中,递归表现为"函数不断调用自身,直到命中基准条件"。基准条件用于跳出递归循环,否则函数会无限调用自身,最终导致调用栈溢出(RangeError: Maximum call stack size exceeded)。

该题明确给出了递归的适用场景:当数据结构包含嵌套、且嵌套层数未知时,递归非常有用。与之形成对比的是,当嵌套层数固定、循环次数已知时,普通的迭代(for / while)往往更直观。判断"该不该用递归"的关键在于:问题的子问题是否与父问题结构相同,且规模不断缩小。

递归的三大要件

从该题的实现中可以提炼出任何递归函数都必须具备的三要素:

  1. 基准条件(Base Condition):递归的出口,决定何时停止自我调用;
  2. 递归步骤(Recursive Step):函数调用自身,并逐步逼近基准条件;
  3. 状态推进(Progress):每次调用都让输入向基准条件靠拢,否则永远无法终止。
// 递归函数的标准骨架
function recursiveFn(input) {
  if (baseCondition(input)) {
    return result // 基准条件:跳出循环
  }
  return recursiveFn(transform(input)) // 递归步骤:缩小问题规模
}

经典实战:把扁平评论数组嵌套成树

该题给出了一个极具代表性的实战案例:数据库返回的评论是扁平数组,而 UI 需要嵌套结构展示。每条评论要么是顶级评论(没有父级),要么是对某条评论的回复;回复下面还有回复,层数不可预知——这正是递归的用武之地。

完整可运行示例(原题代码)

const nest = (items, id = null, link = "parent_id") =>
  items
    .filter(item => item[link] === id)
    .map(item => ({ ...item, children: nest(items, item.id) }))

const comments = [
  { id: 1, parent_id: null, text: "First reply to post." },
  { id: 2, parent_id: 1, text: "First reply to comment #1." },
  { id: 3, parent_id: 1, text: "Second reply to comment #1." },
  { id: 4, parent_id: 3, text: "First reply to comment #3." },
  { id: 5, parent_id: 4, text: "First reply to comment #4." },
  { id: 6, parent_id: null, text: "Second reply to post." }
]

nest(comments)
/*
[
  { id: 1, parent_id: null, text: "First reply to post.", children: [...] },
  { id: 6, parent_id: null, text: "Second reply to post.", children: [] }
]
*/

逐行拆解:递归是如何终止的

原题对终止机制做了关键说明:基准条件在 filter() 返回空数组时被满足。此时链式调用的 map() 根本不会执行回调函数,而递归调用恰好位于 map() 的回调中,于是递归循环被自然切断。

逐行分析 nest 的执行流程:

  1. 参数约定:items 是全部扁平数据;id 表示当前要找的父节点 id(默认 null,即顶级节点);link 是关联字段名(默认 "parent_id"),支持自定义外键字段名;
  2. 第一层筛选:items.filter(item => item[link] === id) 找出所有父节点为 id 的直接子节点。id = null 时得到所有顶级评论;
  3. 第二层递归:map() 对每个筛选出的节点,用展开运算符 ...item 保留原字段,再追加 children 属性,其值为 nest(items, item.id) —— 即递归查找"当前节点的子节点";
  4. 终止条件:当某个节点没有任何子节点时,filter() 返回空数组,map() 不执行回调,children 即为 [],递归到此结束。
// 等价展开:顶层调用
nest(comments)
// = comments
//     .filter(item => item.parent_id === null)   // => [{id:1},{id:6}]
//     .map(item => ({ ...item, children: nest(comments, item.id) }))
// 对 id:1 再执行 nest(comments, 1)
//   => filter(parent_id === 1) 得到 id:2、id:3,再分别递归……
// 对 id:5(最深一层)执行 nest(comments, 5)
//   => filter(parent_id === 5) 返回 [],map 不执行,children = []

亲手验证:在 Node.js 中运行

可以创建一个临时脚本 test-nest.js 粘贴上述代码并在 Node.js 中运行:

node test-nest.js

输出结果可以直观看到树形结构:顶级评论 id: 1 的 children 中包含 id: 2 与 id: 3,而 id: 3 的 children 中又包含 id: 4,id: 4 的 children 再包含 id: 5;id: 6 没有子节点,children 为空数组。递归深度与数据嵌套深度自动对齐,无需预知层级。

从函数式视角理解递归:为何用 filter + map?

在 30 Seconds of Interviews 的题库中,递归与函数式编程是两条密切交织的主线。本题的 nest 用 filter + map 实现,而不是 for 循环 + 手动 push,这并非偶然:

  • 纯函数:nest 不修改入参 items,每次通过 filter/map 产生新数组,符合 纯函数(Pure Function) 的定义——同样的输入必然得到同样的输出,且无副作用;
  • 声明式:递归结构直接描述了"子节点 = 所有以我为父的节点的递归结果",可读性远高于手写栈与循环;
  • 不可变性:{ ...item, children: ... } 使用展开运算符创建新对象,避免对原数据造成污染。

容易出错的三个陷阱

陷阱一:缺少基准条件导致栈溢出

// 危险写法:没有基准条件
const infinite = n => infinite(n + 1)
infinite(0) // RangeError: Maximum call stack size exceeded

任何递归函数都必须先想清楚"何时停止",否则调用栈会被无限撑爆。

陷阱二:基准条件永远无法到达

// 危险写法:n 不减反增,基准条件形同虚设
const boom = n => (n === 0 ? "done" : boom(n + 1))
boom(5) // RangeError

基准条件不仅要有,还必须可达——每次递归调用都要让参数向基准条件收敛。

陷阱三:忽视函数声明提升与执行上下文

递归依赖"函数在自身内部可见"。在 JavaScript 中,函数声明会被提升(hoisting),因此 nest 内部可以安全地引用 nest 自身;但如果用函数表达式赋值,则在赋值完成前调用会报错。这与题库中 Hoisting(提升) 一题提到的行为一致:

// 函数声明:提升后内部可自引用
function nest(items, id = null) { return nest(items, id) } // 合法

// 函数表达式:赋值前不可用
const nest2 = (items, id = null) => nest2(items, id) // 合法(赋值后)

递归 vs 迭代:如何回答面试官

面试中常被追问"递归和循环(迭代)怎么选"。结合本题的评论树案例,可以给出如下对比要点:

维度 递归 迭代(循环)
适用场景 嵌套层数未知、子问题结构与父问题同构 层级固定、遍历次数已知
代码可读性 高,直接表达结构 需手动管理栈或状态变量
风险 深层数据可能栈溢出 一般无栈溢出风险
性能 每次调用产生新执行上下文,开销较大 开销相对更小

面试回答要点:当遇到"层级未知的嵌套结构"(如评论树、目录树、JSON 嵌套遍历)时优先考虑递归;当数据量极大、深度可能达到数万层时,应评估改用显式栈的迭代方案,或用尾递归(若目标运行时支持尾调用优化)来规避栈溢出。

本仓库中的递归相关延伸

  • 同题库中的 fibonacci.md 用 Array.prototype.reduce() 迭代生成长度为 n 的斐波那契数列,是与递归互补的"迭代"答案,适合对比理解;
  • 题库按"问题 / 答案 / Good to hear / Additional links"的模板组织,详见 question-template.md,其中 expertise 字段标注了题目难度(0 简单 / 1 中等 / 2 困难),本题标记为 expertise: (2),属于较难的一档;
  • 全部题目会由 scripts/extract.js 解析成结构化数据 data/questions.json,并支持按 tag(如 javascript)与 expertise 过滤,适合批量检索复习。

小结

  • 递归是函数不断调用自身、直到命中基准条件的编程技巧;
  • 它特别适合处理嵌套层数未知的数据结构,如评论树、目录树;
  • 基准条件必须存在且可达,否则函数会无限调用直至栈溢出;
  • 本题的 nest 通过 filter 空数组天然触发基准条件、map 中递归构建 children,是"纯函数 + 递归"的经典组合;
  • 面试时建议同时说明递归的适用边界与栈溢出风险,并掌握用迭代方案兜底的能力。
登录后查看全文
30-seconds-of-interviews