• 教程
• 文档

本篇技术指南以 30-seconds-of-code 仓库中的 fibonacci.md 为核心，讲解如何用 JavaScript 生成包含前 n 项的斐波那契数列数组，并对比迭代与递归两种实现方案的原理、性能差异与适用场景。读完本文，你将能够写出两种可复用的fibonacci(n)实现，理解递归基准情形（base case）的设定技巧，并掌握针对递归性能问题（重复计算、栈溢出）的备忘录（memoization）与迭代优化思路——这些内容与仓库中 recursion、recursion-performance-optimization 等文章构成完整的学习链路。

斐波那契数列：定义与本次实现目标

斐波那契数列是一串特殊的数字序列，其核心规则是：从0和1开始，之后的每一个数字都是前两个数字之和。序列前几项为：

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

用递推公式可以写成：

F(0) = 0 F(1) = 1 F(n) = F(n - 1) + F(n - 2) （n ≥ 2）

需要特别注意的是，本文目标与仓库中 recursion.md 的经典示例不同：

• recursion.md 中的fibonacci(6)返回第 n 项的值8（即F(6)）；
• 而本篇文章的fibonacci(6)返回包含前 6 项的完整数组[0, 1, 1, 2, 3, 5]。

因此，实现时不仅要计算递推关系，还要把每一项按顺序收集进数组并返回。接下来分别用迭代和递归两种思路实现。

方案一：迭代实现（for 循环 + 数组）

迭代是最直观的实现方式。用for循环从0递增到n - 1，用数组fib保存每一项的值，每次迭代基于前两项计算当前项：

const fibonacci = n => { let fib = []; for (let i = 0; i < n; i++) { if (i <= 1) fib.push(i); else fib.push(fib[i - 1] + fib[i - 2]); } return fib; }; fibonacci(6); // [0, 1, 1, 2, 3, 5]

逐步拆解执行过程

以fibonacci(6)为例，循环内每一步的状态如下：

循环结束后返回[0, 1, 1, 2, 3, 5]。

边界情况与参数约定

• fibonacci(0)：循环一次也不执行，返回[]（空数组）；
• fibonacci(1)：只执行i = 0一次，返回[0]；
• fibonacci(2)：返回[0, 1]。

因此迭代版本天然正确处理 n = 0、1、2 等小输入，无需额外分支。n在这里表示"数列的项数"（生成前 n 项），而非"第 n 项"，这是阅读与调用时最容易混淆的点。

方案二：递归实现（函数自调用 + concat）

递归方案更简洁优雅，但会引入函数调用的开销。它不再使用循环，而是让函数以更小的输入调用自身，直到命中基准情形（base case）：

• 基准情形一：n === 1，直接返回[0]；
• 基准情形二：n === 2，直接返回[0, 1]；
• 一般情形：先递归求出前n - 1项的数组fib，再通过concat追加"最后两项之和"作为第 n 项。

const fibonacci = n => { if (n === 1) return [0]; if (n === 2) return [0, 1]; const fib = fibonacci(n - 1); return fib.concat(fib[fib.length - 1] + fib[fib.length - 2]); }; fibonacci(6); // [0, 1, 1, 2, 3, 5]

递归调用链拆解

以fibonacci(6)为例，其递归展开过程（仅列出主要层级）如下：

fibonacci(6) └─ fibonacci(5) └─ fibonacci(4) └─ fibonacci(3) └─ fibonacci(2) → [0, 1]（基准情形，开始回溯）

回溯阶段逐层计算：

1. fibonacci(3)：拿到[0, 1]，追加fib[1] + fib[0] = 1 + 0 = 1，得到[0, 1, 1]；
2. fibonacci(4)：拿到[0, 1, 1]，追加fib[2] + fib[1] = 1 + 1 = 2，得到[0, 1, 1, 2]；
3. fibonacci(5)：追加fib[3] + fib[2] = 2 + 1 = 3，得到[0, 1, 1, 2, 3]；
4. fibonacci(6)：追加fib[4] + fib[3] = 3 + 2 = 5，得到最终结果[0, 1, 1, 2, 3, 5]。

这里的关键技巧是：用fib[fib.length - 1] + fib[fib.length - 2]取已生成数组的最后两个元素，它们恰好就是递推式中的F(n - 1)与F(n - 2)。

与"求第 n 项"递归版的区别

仓库 recursion.md 中的经典递归示例是求单项值：

const fibonacci = n => { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); }; fibonacci(6); // 8

对比可见：

值得注意的是，两种递归写法都存在共同的递归模型风险：若基准情形缺失，函数会无限自调用，最终导致栈溢出（stack overflow）。这正是 recursion.md 中强调的"基准情形用于打破递归循环、让前序调用得以返回结果"的原因。

方案对比：迭代 vs 递归

从工程角度对两种方案做全面对比：

一句话总结原文档的核心结论：迭代是"最简单"的计算方式，递归"更优雅简洁，但因函数调用开销可能更低效"。若追求稳定性能与可扩展性，优先迭代；若追求代码表现力与教学价值，递归更合适。

递归的性能瓶颈与优化（仓库源码级延伸）

递归方案真正的问题不止是调用开销，更严重的是大量重复计算。仓库 recursion-performance-optimization.md 通过加console.log观察证明：对于单项递归版，每个n值都会被调用两次（一次n - 1、一次n - 2），同一结果被反复计算，计算量随n指数级增长。

优化一：备忘录（memoization）缓存中间结果

该文给出的第一个优化手段是备忘录：用Map缓存每个n的计算结果，命中缓存直接返回，避免重复递归：

const fibonacciCache = new Map(); const fibonacciNumber = n => { const cacheKey = `${n}`; let r; if (fibonacciCache.has(cacheKey)) { r = fibonacciCache.get(cacheKey); } else { r = n >= 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n; fibonacciCache.set(cacheKey, r); } return r; };

备忘录化后，每个n的值只被计算一次。更完整的通用memoize高阶函数（支持Map缓存与Proxy的apply陷阱两种实现）可参考 memoization.md——其中用斐波那契做了压测示例：普通版循环调用 100 次fibonacci(30)耗时约5000ms，而备忘录化版本仅约50ms，足以说明优化效果的数量级差异。

优化二：把递归"倒过来"变成迭代

recursion-performance-optimization.md 提出的第二个思路是从小规模问题出发、自底向上迭代求解，彻底消除递归调用与缓存查找：

const fibonacciNumber = n => { let r = 0, l = 1, s = 0; for (let i = 0; i < n; i++) { r = l; l = s; s = r + l; } return s; };

该文对比后给出的结论是：迭代方案与备忘录方案计算量相同，但迭代不占缓存内存、没有递归调用与缓存命中检查，资源占用更少、执行更快；而备忘录的优势在于缓存可跨多次调用复用——如果同一函数会被用不同参数反复调用，备忘录价值更大；如果调用频次低，迭代更划算。优化手段要与实际使用场景匹配，这是两篇文章共同强调的工程判断原则。

优化三：对"返回数组"版迭代做内存优化

回到本文的核心迭代实现，它用数组保存了全部 n 项。如果只需要最终序列用于展示或进一步处理，这种写法完全没问题；但如果 n 极大且仅需最近两项，可用滚动变量代替数组将空间复杂度从O(n)降到O(1)。这也是从"迭代 + 数组"向"迭代 + 滚动变量"演进的自然思路，读者可根据业务需求取舍。

在 30-seconds-of-code 项目中的组织方式

理解该文档在仓库中的"生态位"，有助于举一反三地学习其他同类文章。

Frontmatter 元数据

fibonacci.md 的 YAML 头部包含：

--- title: Generate the Fibonacci sequence in JavaScript shortTitle: Fibonacci sequence language: javascript tags: [math,algorithm,recursion] cover: matrix-flow excerpt: Generate an array, containing the Fibonacci sequence, up until the nth term, using two different approaches. listed: true dateModified: 2024-08-17 ---

这些字段在 src/models/snippet.js 中被逐一解析：title/shortTitle用于展示标题，tags以分号分隔后作为分类标签（primaryTag取首个标签），dateModified用于按新旧排序与"近 30 天更新"筛选，cover关联封面图，listed控制是否对外展示。

所属集合（Collection）

通过 content/collections/js/recursion.yaml 可以看到，该文章与 recursion、recursion-performance-optimization、factorial、gcd-lcm 等一起被编排进JavaScript Recursion集合，形成"递归入门 → 性能优化 → 斐波那契 → 阶乘 → 最大公约数/最小公倍数"的学习路径；同时因带algorithm标签，也隶属于 content/collections/js/algorithm.yaml 声明的JavaScript Algorithms集合。该集合的说明中明确提示："算法实现主要作为学习资源，生产环境可能已被原生实现或需要优化"——这与本文中"迭代优先、递归需谨慎优化"的建议一脉相承。

相关文章的互相引用

• recursion.md 在介绍递归概念后，通过"进一步阅读"直接指向本文的迭代方案章节，说明"斐波那契用迭代往往更高效"；
• recursion-performance-optimization.md 与 memoization.md 则提供斐波那契的进阶性能优化实现。

这种"基础概念 → 标准实现 → 性能优化"的递进结构，正是 30-seconds-of-code 系列文章便于被搜索引擎、Agent 与 LLM 检索引用的原因：每篇文档自洽完整，又通过元数据与交叉链接形成知识网络。

总结与实操建议

• 需要生成前 n 项序列：优先使用本文的迭代方案（for循环 + 数组），边界稳定、效率高、无栈溢出风险；
• 追求代码简洁、n 值较小：可使用本文递归方案，务必保留n === 1、n === 2两个基准分支，避免死递归；
• n 值较大或需重复调用：对递归做备忘录化缓存（参考 memoization.md），或直接改写为自底向上的迭代滚动变量版；
• 区分"第 n 项"与"前 n 项"：本篇文章返回数组，recursion.md 的示例返回单项，调用前先明确需求语义。

将以上两种实现保存为fibonacci.js即可在 Node.js 或浏览器控制台直接运行验证：

# Node.js 中执行 node -e "const fibonacci = n => { let fib = []; for (let i = 0; i < n; i++) { if (i <= 1) fib.push(i); else fib.push(fib[i - 1] + fib[i - 2]); } return fib; }; console.log(fibonacci(6));" # 输出：[ 0, 1, 1, 2, 3, 5 ]

• 教程
• 文档