《现代 JavaScript 教程》递归实战：用阶乘 factorial 练习吃透递归与执行堆栈

• 文档
• 教程
• 前端

本篇技术指南以《现代 JavaScript 教程》（zh.javascript.info）中文版仓库中的递归章节练习「计算阶乘」为切入点，系统讲解阶乘的递归定义、factorial(n)的标准递归实现与基础情形选择，并延伸至递归底层的执行上下文与调用堆栈原理、递归与循环/公式实现的性能差异、递归深度上限以及斐波那契、链表遍历等同类实战。读者学完后，将能独立完成该章节的阶乘练习，并理解"什么时候该用递归、什么时候该改写为循环"这一核心判断力。

任务背景：递归章节中的阶乘练习

在仓库中，本练习位于 1-js/06-advanced-functions/01-recursion/02-factorial/ 目录下，题目文件为 task.md，标记的难度（importance）为 4，属于递归章节 01-recursion/article.md 中紧随sumTo（01-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的调用又会继续递减，直到基础值1：

function 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是假值（falsy），n ? ... : 1在n == 0时返回1：

function 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的值等。一个正在运行的函数有且仅有一个与之关联的执行上下文。

当函数发生嵌套调用（包括调用自身）时，引擎执行如下步骤：

1. 当前函数被暂停；
2. 与它关联的执行上下文被压入执行上下文堆栈（execution context stack）保存；
3. 执行嵌套调用（为新调用创建新的执行上下文）；
4. 嵌套调用结束后，从堆栈顶部弹出之前的上下文，从暂停的位置恢复外部函数继续执行。

以pow(2, 3)为例，调用链会依次创建{x:2, n:3}、{x:2, n:2}、{x:2, n:1}三个上下文，递归深度为 3——递归深度等于堆栈中上下文的最大数量。factorial(5)同理，堆栈中最多同时存在 5 个factorial的上下文。

这带来两个重要结论：

1. 内存开销：递归需要为每一层嵌套调用保存一个执行上下文，factorial(n)需要存储n个上下文；而循环实现自始至终只使用一个上下文（如pow的迭代版只维护result和i），内存占用固定且不随n增长。
2. 深度上限：最大递归深度受限于 JavaScript 引擎。仓库文档明确指出，引擎在最大递归深度为 10000 及以下时是可靠的，部分引擎可能允许更大，但对大多数引擎来说 100000 很可能超出限制并抛出"超出最大堆栈深度"错误。这意味着递归解法只适合n适中的场景。

性能对比：递归、循环与公式

同章节的练习 sumTo（importance 5）要求用三种方式计算1+2+...+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.md）：

function 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 文档）表达力更强。当递归树存在大量重叠子问题时（如斐波那契），应改用循环或动态规划。
• 进一步练习：继续完成本章的 斐波那契数、输出单链表 与逆序输出练习，可以系统巩固"递归思维 + 何时改写迭代"的能力。

• 文档
• 教程
• 前端