30 Seconds of Interviews：用 Array.reduce 生成斐波那契数列数组的 JavaScript 实现与面试拆解-平芜编程栈

30 Seconds of Interviews：用 Array.reduce 生成斐波那契数列数组的 JavaScript 实现与面试拆解

【免费下载链接】30-seconds-of-interviewsA curated collection of common interview questions to help you prepare for your next interview.项目地址: https://gitcode.com/gh_mirrors/30/30-seconds-of-interviews

导读

本文围绕 30 Seconds of Interviews 面试题库中的经典 JavaScript 算法题——「生成包含斐波那契数列、截至第 n 项的数组」展开，逐行拆解其基于Array.prototype.reduce()的声明式实现，并对比递归、记忆化等常见解法。读完你将掌握reduce()的累加器模型、稀疏数组与concat的配合技巧，以及如何在大 O 视角下向面试官论证该算法的时空复杂度，为算法类面试题提供一套可复用的分析话术。

一、题目本身：要求与考点

原题出自本仓库的 questions/fibonacci.md：

Generate an array, containing the Fibonacci sequence, up until the nth term.（生成一个数组，包含截至第 n 项的斐波那契数列。）

这是典型的「用高阶函数实现经典序列」类问题，expertise标记为 1（intermediate 难度），归属javascript标签。它的考察重点不在「是否知道斐波那契定义」，而在于：

能否用声明式（函数式）风格替代常见的for循环；
是否真正理解Array.prototype.reduce()的累加器机制；
能否正确处理前两项的特殊性（数列中第 0、1 项没有「前两项之和」可加）。

二、官方参考答案：一行 reduce 的声明式实现

原文档给出的答案如下：

const fibonacci = n => [...Array(n)].reduce( (acc, val, i) => acc.concat(i > 1 ? acc[i - 1] + acc[i - 2] : i), [] )

思路概括（原文档原话）：初始化一个长度为n的空数组，用Array.prototype.reduce()向数组中追加值——从第三项开始，取累加数组中最后两个值的和；前两项则直接使用索引i本身。

逐行拆解执行过程

Array(n)创建稀疏数组，长度为n、没有任何元素（所有槽位为empty）；
[...Array(n)]借助数组展开语法，把稀疏数组「摊开」为[undefined, undefined, ..., undefined]，共n个元素。这一步是reduce()能够逐槽遍历的前提——reduce会跳过空槽位，若不展开，回调根本不会执行；
reduce((acc, val, i) => ..., [])以空数组[]为初始累加器，遍历n个槽位，回调的第三个参数i恰好就是当前项在序列中的位置（0 ~ n-1）；
acc.concat(i > 1 ? acc[i - 1] + acc[i - 2] : i)是核心逻辑：
- 当i > 1时，取累加数组中倒数第一、第二项求和后追加（concat返回新数组，不修改原累加器）；
- 当i === 0时追加0，i === 1时追加1——这两项是斐波那契序列的种子，无法由前两项推导；
最终reduce返回的数组即[0, 1, 1, 2, 3, 5, 8, ...]。

验证各 n 值下的输出

fibonacci(1) // [0] fibonacci(2) // [0, 1] fibonacci(5) // [0, 1, 1, 2, 3] fibonacci(10) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

注意：题目要求「up until the nth term」，因此fibonacci(n)返回的是前 n 项（索引 0 到 n-1），而非斐波那契定义中的「第 n 个斐波那契数」F(n)。两者在面试沟通中务必先说清楚约定，否则容易产生歧义。

三、为什么选`concat`而不是`push`？

这道题最容易被追问的细节就是：累加器追加元素为什么用concat，而不用push？

原因在于reduce回调的返回值会成为下一次回调的累加器：

// push 会原地修改并返回新长度，破坏累加器语义 const bad = n => [...Array(n)].reduce((acc, val, i) => { acc.push(i > 1 ? acc[i - 1] + acc[i - 2] : i) return acc // 必须手动返回 acc，否则下一次拿到 undefined }, []) // concat 返回新数组，天然符合「返回新累加器」的约定 const good = n => [...Array(n)].reduce( (acc, val, i) => acc.concat(i > 1 ? acc[i - 1] + acc[i - 2] : i), [] )

concat的不可变（immutable）风格也与本仓库其他题目强调的函数式理念一致：例如 questions/for-each-map.md 指出map()将每个元素映射到新数组、保持数据不可变，是常见的函数式编程手法；questions/pure-functions.md 对纯函数的定义也要求「同样的输入必然得到同样的输出，且不产生副作用」。concat版本天然满足纯函数要求，而push版本则引入了外部可变状态。

四、面试进阶：与其他解法的对比

4.1 经典 for 循环版本

function fibonacci(n) { const arr = [0, 1] for (let i = 2; i < n; i++) { arr[i] = arr[i - 1] + arr[i - 2] } return arr.slice(0, n) }

命令式版本胜在直观，但面试官往往会要求你用高阶函数改写，考察你对reduce的熟练度。

4.2 递归版本与性能陷阱

const fib = n => (n < 2 ? n : fib(n - 1) + fib(n - 2))

本仓库的 questions/recursion.md 指出：递归是函数反复调用自身、直到命中 base condition 的过程。斐波那契天然适合递归表述，但朴素递归存在严重的重复计算：fib(5)会反复计算fib(3)、fib(2)多次，指数级膨胀。

若面试官追问「如何优化递归版斐波那契」，可顺势引出记忆化（memoization）——这正是仓库中另一道独立考题 questions/memoize.md 的主题：缓存函数调用结果，使相同输入的后续调用直接命中缓存：

const memoize = fn => { const cache = new Map() return value => { const cachedResult = cache.get(value) if (cachedResult !== undefined) return cachedResult const result = fn(value) cache.set(value, result) return result } } const fastFib = memoize(n => (n < 2 ? n : fastFib(n - 1) + fastFib(n - 2)))

不过要如实向面试官说明：memoize 版第一调用仍有额外开销（检查缓存、写入缓存），且返回的是单个斐波那契数而非整段序列；若目标是整段数组，reduce 版一次遍历即可同时产出所有项，无需缓存。

五、复杂度分析：用 Big O 语言论证

面试中回答完实现后，标准动作是给出时间/空间复杂度。可借用本仓库 questions/big-o-notation.md 的分析框架：

版本	时间复杂度	空间复杂度	说明
reduce + concat（本文主角）	O(n²)	O(n)	每次`concat`复制当前累加器（长度 0..n-1），总复制量为 1+2+...+n
for 循环 + 索引赋值	O(n)	O(n)	每次迭代常数时间写入新槽位
朴素递归 fib(n)	O(2ⁿ)	O(n)（调用栈）	大量重复子问题
记忆化递归	O(n)	O(n)	每个子问题只算一次

由此可以给出一个诚实的结论：reduce+concat 版胜在声明式与不可变，但它不是性能最优解；在 n 较大时应改用索引赋值或push版本，这也呼应了 big-o 文档中「警惕嵌套循环导致执行时间指数/平方级上升」的告诫。能在面试中主动指出这一点，往往比只会背诵答案更能加分。

六、仓库视角：这份答案在项目中如何被组织与消费

作为 30 Seconds of Interviews 的一则条目，questions/fibonacci.md遵循仓库统一的题面模板（参见 question-template.md）：### 题目→ 可选示例代码 →#### Answer→#### Good to hear→##### Additional links→ 元数据注释（tags、expertise）。

这套结构化格式并非摆设。仓库通过 scripts/util.js 中的readQuestions()读取questions/目录下全部.md文件，再以getSection("#### Answer", contents)等函数按标题切片提取题面、答案、要点与链接；随后 scripts/extract.js 将这些片段组装为 JSON 条目（含name、question、answer、goodToHear、links、tags、expertise、questionCodeBlocks、answerCodeBlocks），最终写入 data/questions.json 供前端站点渲染。这意味着「答案代码块能否被正则正确识别」直接决定展示质量——本文主角fibonacci的答案代码块正是被getCodeBlocks()以```围栏正则提取的典型样例。

七、附：原文档的 Good to hear 与扩展阅读指引

原文档在#### Good to hear之后、##### Additional links中给出了一条外部链接（指向 30-seconds-of-code 归档中的fibonacciUntilNum.md）。根据本任务对仓库链接的规范，此处不再展开外部链接内容；建议继续研读仓库内同主题的相邻文档以构建知识网络：

questions/recursion.md——递归的适用场景与基准条件（base condition）；
questions/memoize.md——记忆化缓存的完整实现与权衡；
questions/big-o-notation.md——O(1)/O(N)/O(N²)/O(N!) 的直观量级对照；
questions/pipe.md——同样基于reduce的函数组合题，可与本题互相印证 reduce 的多种用法。

小结

[...Array(n)].reduce((acc, _, i) => acc.concat(i > 1 ? acc[i-1] + acc[i-2] : i), [])以一行代码完成了斐波那契前 n 项的声明式生成。它同时考察了三层能力：对稀疏数组与展开语法的理解、对reduce累加器契约的把握、对前两项种子条件的处理。面试时建议按「实现 → 逐行解释 → 复杂度 → 与其他解法对比」的顺序作答，并坦诚指出 concat 的 O(n²) 代价与替代方案，这样的回答既有深度又不失严谨。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

30 Seconds of Interviews：用 Array.reduce 生成斐波那契数列数组的 JavaScript 实现与面试拆解