教程文档【免费下载链接】30-seconds-of-codeCoding articles to level up your development skills项目地址https://gitcode.com/gh_mirrors/30/30-seconds-of-code点击查看免费下载本篇技术指南以 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)为例循环内每一步的状态如下迭代次数i条件执行动作数组当前内容0i 1成立fib.push(0)[0]1i 1成立fib.push(1)[0, 1]2不成立fib.push(fib[1] fib[0])→1 0[0, 1, 1]3不成立fib.push(fib[2] fib[1])→1 1[0, 1, 1, 2]4不成立fib.push(fib[3] fib[2])→2 1[0, 1, 1, 2, 3]5不成立fib.push(fib[4] fib[3])→3 2[0, 1, 1, 2, 3, 5]循环结束后返回[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]基准情形开始回溯回溯阶段逐层计算fibonacci(3)拿到[0, 1]追加fib[1] fib[0] 1 0 1得到[0, 1, 1]fibonacci(4)拿到[0, 1, 1]追加fib[2] fib[1] 1 1 2得到[0, 1, 1, 2]fibonacci(5)追加fib[3] fib[2] 2 1 3得到[0, 1, 1, 2, 3]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对比可见对比维度本文递归版返回数组recursion.md 递归版返回单项返回值前 n 项数组[0, 1, 1, 2, 3, 5]第 n 项数值8基准情形n 1与n 2两个分支n 1一个分支子调用次数每层只调用自身 1 次每层调用自身 2 次组合子问题方式concat拼接已生成数组两路结果相加值得注意的是两种递归写法都存在共同的递归模型风险若基准情形缺失函数会无限自调用最终导致栈溢出stack overflow。这正是 recursion.md 中强调的基准情形用于打破递归循环、让前序调用得以返回结果的原因。方案对比迭代 vs 递归从工程角度对两种方案做全面对比维度迭代方案递归方案代码可读性直白易懂适合初学者简洁优雅贴近数学定义效率高单次循环无额外开销较低存在函数调用栈开销内存仅数组存储数组 递归调用栈边界情况天然处理 n 0、1需要显式写两个基准分支大 n 风险无深层递归可能导致栈溢出一句话总结原文档的核心结论迭代是最简单的计算方式递归更优雅简洁但因函数调用开销可能更低效。若追求稳定性能与可扩展性优先迭代若追求代码表现力与教学价值递归更合适。递归的性能瓶颈与优化仓库源码级延伸递归方案真正的问题不止是调用开销更严重的是大量重复计算。仓库 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 ]赞分享教程文档【免费下载链接】30-seconds-of-codeCoding articles to level up your development skills项目地址https://gitcode.com/gh_mirrors/30/30-seconds-of-code点击查看免费下载相关推荐30 Seconds of Interviews用 Array.reduce 生成斐波那契数列数组的 JavaScript 实现与面试拆解30 Seconds of Interviews用 Array.reduce 生成斐波那契数列数组的 JavaScript 实现与面试拆解 导读 本文围绕 3教程前端用 JavaScript 递归实战斐波那契数列与归并排序Fibonacci Merge Sort用 JavaScript 递归实战斐波那契数列与归并排序Fibonacci Merge Sort 导读 本篇实战项目来自 curriculum htt文档教程教育终极算法指南Algorithms项目中的递归与迭代实战对比——从斐波那契数列到阶乘计算终极算法指南Algorithms项目中的递归与迭代实战对比——从斐波那契数列到阶乘计算 Algorithms项目是一个专注于用Java解决常见算法问题的开源项示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考