文档教程前端【免费下载链接】zh.javascript.info现代 JavaScript 教程The Modern JavaScript Tutorial以最新的 ECMAScript 规范为基准通过简单但足够详细的内容为你讲解从基础到高阶的 JavaScript 相关知识。项目地址https://gitcode.com/gh_mirrors/zh/zh.javascript.info点击查看免费下载本篇技术指南以《现代 JavaScript 教程》zh.javascript.info中文版仓库中的递归章节练习「计算阶乘」为切入点系统讲解阶乘的递归定义、factorial(n)的标准递归实现与基础情形选择并延伸至递归底层的执行上下文与调用堆栈原理、递归与循环/公式实现的性能差异、递归深度上限以及斐波那契、链表遍历等同类实战。读者学完后将能独立完成该章节的阶乘练习并理解什么时候该用递归、什么时候该改写为循环这一核心判断力。任务背景递归章节中的阶乘练习在仓库中本练习位于 1-js/06-advanced-functions/01-recursion/02-factorial/ 目录下题目文件为 task.md标记的难度importance为 4属于递归章节 01-recursion/article.md 中紧随sumTo01-sum-to/task.md之后的第二个练习难度略低于后者sumTo 为 importance 5。递归是本章的核心主题当一个函数解决任务的过程中调用自身这就是递归。本章此前已通过pow(x, n)讲解了递归的两种思考方式迭代 vs 递归、基础base与递归步骤的概念阶乘练习正是把pow中学到的模式迁移到另一个经典数学函数上验证读者是否真正掌握了把任务简化为更简单的同类任务的递归思维方式。阶乘的数学定义与任务要求阶乘factorial定义为自然数n的阶乘等于n乘以n-1再乘以n-2依此类推直到乘以1记作n!n! n * (n - 1) * (n - 2) * ... * 1题目给出了不同n的阶乘取值用于后续验证函数输出1! 1 2! 2 * 1 2 3! 3 * 2 * 1 6 4! 4 * 3 * 2 * 1 24 5! 5 * 4 * 3 * 2 * 1 120任务要求编写函数factorial(n)使用递归调用计算n!并满足如下调用结果alert( factorial(5) ); // 120题目的 P.S. 提示点明了递归解法的关键n!可以被写成n * (n-1)!例如3! 3 * 2! 3 * 2 * 1! 6。这正是把大任务拆成一次简单乘法 一个更小的同类任务的过程是递归解法的灵魂。递归解法从数学递推式到代码官方参考答案位于 solution.md。依据递推式n! n * (n-1)!factorial(n)的结果可以表示为n乘以factorial(n-1)的结果而对n-1的调用又会继续递减直到基础值1function factorial(n) { return (n ! 1) ? n * factorial(n - 1) : 1; } alert( factorial(5) ); // 120这段代码由两个关键部分构成递归步骤当n ! 1时返回n * factorial(n - 1)。这是一次乘法 一次更简单的递归调用。基础base当n 1时直接返回1。基础是递归的出口它保证调用链能在有限步内终止——没有基础递归将无限循环直至堆栈溢出。以factorial(5)为例实际执行过程逐层展开为factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2))) 5 * (4 * (3 * (2 * factorial(1)))) 5 * (4 * (3 * (2 * 1))) 120基础情形也可以用 0答案还给出了第二种写法以0作为基础。由于0是假值falsyn ? ... : 1在n 0时返回1function factorial(n) { return n ? n * factorial(n - 1) : 1; } alert( factorial(5) ); // 120两种写法结果完全相同区别仅在于以0为基础会多一次递归步骤factorial(1)会再调用一次factorial(0)才返回。题目定义的阶乘从1!开始因此两种基础都正确实际工程中把0! 1也纳入定义数学上 0 的阶乘定义为 1反而更通用。递归原理执行上下文与调用堆栈要真正理解上面的代码为什么能工作需要了解递归调用在 JavaScript 引擎底层的运行机制。本章正文 article.md 以pow(x, n)为例做了详细剖析其原理对factorial完全一致。执行上下文execution context是引擎内部的数据结构保存函数执行时的全部细节当前控制流所在位置、当前变量值、this的值等。一个正在运行的函数有且仅有一个与之关联的执行上下文。当函数发生嵌套调用包括调用自身时引擎执行如下步骤当前函数被暂停与它关联的执行上下文被压入执行上下文堆栈execution context stack保存执行嵌套调用为新调用创建新的执行上下文嵌套调用结束后从堆栈顶部弹出之前的上下文从暂停的位置恢复外部函数继续执行。以pow(2, 3)为例调用链会依次创建{x:2, n:3}、{x:2, n:2}、{x:2, n:1}三个上下文递归深度为 3——递归深度等于堆栈中上下文的最大数量。factorial(5)同理堆栈中最多同时存在 5 个factorial的上下文。这带来两个重要结论内存开销递归需要为每一层嵌套调用保存一个执行上下文factorial(n)需要存储n个上下文而循环实现自始至终只使用一个上下文如pow的迭代版只维护result和i内存占用固定且不随n增长。深度上限最大递归深度受限于 JavaScript 引擎。仓库文档明确指出引擎在最大递归深度为 10000 及以下时是可靠的部分引擎可能允许更大但对大多数引擎来说 100000 很可能超出限制并抛出超出最大堆栈深度错误。这意味着递归解法只适合n适中的场景。性能对比递归、循环与公式同章节的练习 sumToimportance 5要求用三种方式计算12...n的和其答案 solution.md 给出了递归与迭代实现的直接性能对比可作为判断阶乘该用哪种实现的参照。三种实现// 1. 循环 function sumTo(n) { let sum 0; for (let i 1; i n; i) { sum i; } return sum; } // 2. 递归 function sumTo(n) { if (n 1) return 1; return n sumTo(n - 1); } // 3. 等差数列公式 function sumTo(n) { return n * (n 1) / 2; }答案的结论是公式解法最快对任意n只需要常数次3 次运算循环次之循环与递归对相同数字求和但递归涉及嵌套调用和执行堆栈管理占用额外资源因此更慢递归最慢递归的每一层都要创建、压栈、出栈执行上下文。关于sumTo(100000)能否用递归部分引擎支持尾调用优化tail call optimization——如果递归调用是函数中的最后一个调用外部函数无需恢复执行引擎也就不必保存其执行上下文从而大幅降低内存占用使大n递归成为可能。但尾调用优化目前尚未被所有引擎完全支持只能用于简单场景在不支持的引擎上sumTo(100000)会因超出最大堆栈深度而报错。值得注意的是factorial与sumTo的递归调用同样位于 return 语句末尾return n * factorial(n - 1)中的乘法发生在递归调用返回之后但factorial在递归返回后还需要执行一次乘法因此并不满足尾调用的严格定义真正的尾调用是return factorial(n - 1)这种形式。这解释了为什么阶乘递归更容易触碰堆栈深度限制。递归的边界斐波那契的教训递归并不总是好选择。同一章节的 斐波那契数练习importance 5要求fib(n)对fib(77)的运行时间不超过几分之一秒而最直观的递归实现恰恰做不到function fib(n) { return n 1 ? n : fib(n - 1) fib(n - 2); } // fib(77); // 超级慢会挂起引擎并耗尽 CPU原因在于该递归会产生指数级的重复子调用fib(5)和fib(4)都需要fib(3)fib(3)被独立计算两次、fib(2)被计算三次总计算量远远超过n。答案给出的优化方案是放弃递归改用自底向上的循环从fib(1)、fib(2)出发每步只用前两个值滚动求和直到目标值。这种每一步只记录前两个值的做法被称为自下而上的动态规划见 solution.mdfunction fib(n) { let a 1; let b 1; for (let i 3; i n; i) { let c a b; a b; b c; } return b; } alert( fib(77) ); // 5527939700884757阶乘与此形成鲜明对比factorial的递归调用树是一条单链每层只有一个子调用没有重复计算因此递归版本与循环版本的时间复杂度相同都是 O(n)递归的主要代价只是堆栈内存。而fib的递归树是分叉的重复计算导致指数级复杂度——判断递归是否合适关键在于递归树是否包含大量重叠子问题。递归的应用延伸遍历链表递归在递归定义的数据结构上格外自然。本章练习 输出一个单链表 要求分别用循环和递归实现printList(list)其答案solution.md展示了两种风格// 循环版使用临时变量 tmp 遍历 function printList(list) { let tmp list; while (tmp) { alert(tmp.value); tmp tmp.next; } } // 递归版输出当前元素再对 list.next 做同样的事 function printList(list) { alert(list.value); // 输出当前元素 if (list.next) { printList(list.next); // 链表中其余部分同理 } }答案对哪个更好的结论是从技术上讲循环更有效——两种解法做了同样的事但循环不会为嵌套函数调用消耗堆栈资源递归则更简洁、有时更容易理解。这与本章正文的总结一致任何递归函数都可以被重写为迭代形式……但对大多数任务来说递归方法足够快并且容易编写和维护。该练习的进阶版本 05-output-single-linked-list-reverse/ 要求逆序输出链表正是利用递归调用在返回途中继续执行的特性——先递归到链表末尾再逐层输出天然实现逆序这是循环版本难以直接做到的。总结通过factorial(n)这道练习可以沉淀以下要点递归三要素一个递归函数包含递归步骤把任务简化为更简单行为的调用自身和基础参数使任务简单到不再需要继续调用。factorial的基础是1或0递归步骤是n * factorial(n - 1)。底层机制递归依赖执行上下文堆栈保存每一层的状态递归深度等于堆栈上下文的最大数量上下文占用内存深度受引擎限制约 10000 内可靠。性能取舍循环通常比递归更省内存、更快递归的价值在于代码更短、更易理解维护且对递归定义的结构链表、树、HTML 文档表达力更强。当递归树存在大量重叠子问题时如斐波那契应改用循环或动态规划。进一步练习继续完成本章的 斐波那契数、输出单链表 与逆序输出练习可以系统巩固递归思维 何时改写迭代的能力。赞分享文档教程前端【免费下载链接】zh.javascript.info现代 JavaScript 教程The Modern JavaScript Tutorial以最新的 ECMAScript 规范为基准通过简单但足够详细的内容为你讲解从基础到高阶的 JavaScript 相关知识。项目地址https://gitcode.com/gh_mirrors/zh/zh.javascript.info点击查看免费下载相关推荐现代 JavaScript 教程递归与执行上下文堆栈深度解析现代 JavaScript 教程递归与执行上下文堆栈深度解析 递归recursion是 JavaScript 中一种核心编程模式当一个任务可以自然地拆分文档教程前端Minimal Mistakes 主题 Overlay Header 图片的 OpenGraph 覆盖配置实战og_image 详解Minimal Mistakes 主题 Overlay Header 图片的 OpenGraph 覆盖配置实战og_image 详解 导读 本篇文章聚焦 M文档教程前端Modern JavaScript Tutorial 递归实战从 factorial(n) 任务到执行上下文与调用栈原理Modern JavaScript Tutorial 递归实战从 factorial n 任务到执行上下文与调用栈原理 本文围绕 Modern JavaScr文档/教程前端上一篇Ada 嵌入式开发终极教程从微控制器到实时系统下一篇QMP 协议深度指南用 Go 与 QEMU 虚拟机直接对话创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考