企业官网建设流程全解析

• 教程

本文源自 jstips 开源仓库（GitHub 加速计划 / js / jstips）第 29 期 JavaScript 技巧：Speed up recursive functions with memoization。文章以斐波那契数列为切入点，剖析朴素递归的重复计算问题，并给出"闭包缓存"与"通用 memoize 高阶函数"两种优化方案，覆盖 ES5 与 ES6 两套写法，最后推广到最大公约数（GCD）与阶乘等典型递归场景。读完本文，你将掌握 memoization 的核心原理、通用封装方法与适用边界，能够直接为项目中的递归计算函数提速。

问题引入：20 秒就能写出的低效递归

斐波那契（Fibonacci）数列对开发者而言再熟悉不过。原文档给出了一个 20 秒内就能写出的朴素实现（见 _posts/en/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md）：

var fibonacci = function(n) { return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2); }

这段代码能正确运行，但效率极低。原因在于它做了大量重复计算：以fibonacci(5)为例，fibonacci(3)会被重复调用多次——左侧分支算一遍、右侧分支又算一遍，且这种重复随n增大呈指数级扩散。整个调用过程会形成一个巨大的递归调用树，同一子问题被反复求解，计算量呈O(2^n)量级膨胀。

关于递归调用过程的形态，仓库第 67 期 Recursion, iteration and tail calls in JS 有更深入的剖析：每次函数调用都会保存返回位置与当前栈帧信息，随后不断压栈、再逐层出栈展开。朴素递归正是这种"递归过程"的典型代表——它在计算完成后仍需回溯栈帧做乘法组合，既慢又容易触碰栈深度上限。

方案一：闭包 + 缓存数组，用空间换时间

既然重复计算是瓶颈，最直接的思路就是把算过的结果缓存起来，下次直接取用。原文档给出了基于 IIFE（立即调用函数表达式）与闭包的实现：

var fibonacci = (function() { var cache = [0, 1]; // cache the value at the n index return function(n) { if (cache[n] === undefined) { for (var i = cache.length; i <= n; ++i) { cache[i] = cache[i - 1] + cache[i - 2]; } } return cache[n]; } })();

这段代码的精妙之处在于：

• cache = [0, 1]作为闭包内的私有状态，预先存入数列的前两个基准值（fibonacci(0) = 0、fibonacci(1) = 1），且用注释明确说明"缓存第 n 个索引位置的值"；
• 外部函数体只能通过返回的匿名函数访问cache，缓存对外部完全隔离，不会被意外污染；
• 当请求的n尚未计算（cache[n] === undefined）时，自底向上从已有缓存的末尾逐项递推补齐：cache[i] = cache[i - 1] + cache[i - 2]，直到填满n；
• 一旦cache[n]已存在，直接O(1)返回，不再递归。

这种"自底向上 + 顺序填表"的做法本质上就是动态规划的迭代形态：每次调用最多补算n - cache.length个新项，后续相同或更小的n全部命中缓存，整体时间复杂度从指数级降为线性O(n)。

仓库的多语言版本中，中文简体版（_posts/zh_CN/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md）与繁体版（_posts/zh_TW/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md）保留了完全相同的算法骨架，繁体版进一步将var升级为const/let并改用self(n-1) + self(n-2)的递归填表方式——这说明该缓存思路在不同语言变体中被一致认可，只是实现细节各有取舍。

方案二：通用 memoize 高阶函数

针对斐波那契单独写缓存虽然直观，但每个递归函数都要手写一遍闭包太繁琐。原文档随即给出了更优雅的抽象：定义一个高阶函数memoize，它接收任意函数作为参数，返回该函数的"带记忆"版本。

ES5 版本

var memoize = function(func) { var cache = {}; return function() { var key = JSON.stringify(Array.prototype.slice.call(arguments)); return key in cache ? cache[key] : (cache[key] = func.apply(this, arguments)); } } fibonacci = memoize(fibonacci);

逐行拆解其工作原理：

1. cache = {}是闭包内的键值缓存，键为"参数序列化后的字符串"，值为对应计算结果；
2. Array.prototype.slice.call(arguments)把类数组对象arguments转换为真正的数组，从而能调用数组方法；
3. JSON.stringify(...)将参数列表序列化为唯一字符串键——这是本实现的关键：不同参数组合对应不同缓存键，天然支持多参数函数；
4. key in cache ? cache[key] : (cache[key] = func.apply(this, arguments))是短路求值的经典写法：键已存在则直接返回缓存值，否则调用原函数func计算并写入缓存后返回；
5. 通过func.apply(this, arguments)保留调用时的this上下文与全部实参，使被包装函数的行为不被破坏。

最后一行fibonacci = memoize(fibonacci)用带记忆的版本覆盖原函数，对外调用方式完全不变，即插即用。

JSON.stringify在这里的作用值得单独说明——仓库第 40 期 Using JSON.Stringify 详细讲解了它的高级用法（选择性序列化属性、replacer 函数、缩进格式化）。memoize 正是利用了它"把任意 JS 值变成字符串"的能力来生成缓存键，可视为该技巧在缓存场景的实战应用。需要注意的是，当参数包含对象时，序列化结果是"按内容"生成的字符串，因此内容相同的对象会命中同一缓存键；若参数是函数、undefined或存在循环引用，JSON.stringify会失效，这是该实现的主要局限（详见后文"适用边界"）。

ES6 版本

原文档接着给出更简洁的 ES6 版本，利用剩余参数（rest parameters）与箭头函数：

var memoize = function(func) { const cache = {}; return (...args) => { const key = JSON.stringify(args); return key in cache ? cache[key] : (cache[key] = func(...args)); } } fibonacci = memoize(fibonacci);

与 ES5 版相比，变化一目了然：

ES6 版去掉了arguments与apply的样板代码，可读性显著提升。值得注意的是，仓库的中文简体版（_posts/zh_CN/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md）与西班牙语版（_posts/es_ES/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md）在键生成上采用了另一种等价写法[...args].toString()：它借助展开运算符将剩余参数转为数组再调用toString()，效果与JSON.stringify(args)类似（对数字、字符串等原始类型参数完全一致），属于同一思路的变体，读者可对比体会。

实战推广：memoize 的更多应用场景

原文档明确指出memoize()可以用于很多其他场景，并给出了两个经典示例。

最大公约数 GCD

var gcd = memoize(function(a, b) { var t; if (a < b) t = b, b = a, a = t; while (b != 0) t = b, b = a % b, a = t; return a; }); gcd(27, 183); //=> 3

这里先通过交换确保a >= b，再用辗转相除法（欧几里得算法）求最大公约数。gcd(27, 183)的正确结果是3。memoize 包装后，当程序中反复以相同参数对调用 GCD 时（例如循环内对固定组合求公约数），可直接命中缓存。多参数场景正好验证了 memoize 用"序列化参数组合"作为缓存键的设计是必要的——单个参数的缓存无法区分不同参数对。

阶乘计算

var factorial = memoize(function(n) { return (n <= 1) ? 1 : n * factorial(n - 1); }) factorial(5); //=> 120

阶乘是教科书级的递归案例。注意这里的闭包技巧：factorial已经被重新赋值成了 memoize 包装后的函数，因此递归调用factorial(n - 1)实际调用的是带缓存的版本，每一层的中间结果都会被记录下来。调用factorial(5)返回120后，再调用factorial(10)时，5!及以下的结果全部命中缓存，只需补算6!到10!。

仓库第 67 期 Recursion, iteration and tail calls in JS 对阶乘递归的两种写法（朴素递归 vs 尾递归携带累加参数）做了完整的执行过程推演，并讨论了 ES6 尾调用优化（TCO）的现状。与 memoization 相比，两者解决的是不同维度的问题：尾调用优化减少调用栈深度，memoization 消除重复子计算——对于同一参数会被反复求解的递归，memoization 的收益更为直接。

memoization 的适用边界与注意事项

结合原文档实现与仓库其他 tip，可以总结出使用 memoization 时值得注意的边界：

1. 缓存键的序列化局限：JSON.stringify无法正确处理function、undefined、Symbol以及循环引用对象，遇到这些参数时键生成会失败或产生歧义（如undefined与缺失参数可能序列化出相同键）。若函数参数包含这类值，需改用自定义键函数；
2. 对象参数的语义：JSON.stringify按对象内容生成键，两个内容相同但引用不同的对象会命中同一缓存——多数情况下符合预期，但若函数依赖对象身份（identity）或内部状态，则可能得到错误结果；
3. 内存占用：缓存随调用参数组合的增长而无限膨胀，属于典型的"空间换时间"。对参数组合数量极大或参数为大型对象的高频函数，需要引入缓存淘汰（LRU）或容量上限策略；
4. 纯函数前提：memoization 只对确定性纯函数安全。如果原函数依赖外部可变状态、当前时间、随机数或产生副作用，缓存结果将失去意义——这是使用 memoize 之前必须先确认的前提；
5. this的处理：ES5 版本通过func.apply(this, arguments)保留了this绑定，因此可用于对象方法；ES6 箭头函数版本中箭头函数不绑定自己的this，若被包装函数依赖动态this，需注意上下文差异；
6. 与函数式风格的关系：仓库中 _posts/en/javascript/2017-06-14-immutable-structures-and-cloning.md 讨论了不可变结构与克隆的话题——memoization 在函数式编程中常与"引用透明"（引用透明即相同输入永远产生相同输出）配合使用，纯函数是安全记忆化的前提，这一原则同样适用于本 tip。

小结

本 tip 以斐波那契为引子，完整覆盖了 memoization 的三层递进：朴素递归暴露重复计算问题 → 闭包缓存数组给出专用解 → 通用memoize高阶函数给出可复用抽象（ES5/ES6 双版本），并以 GCD、阶乘验证其通用性。其核心要点可浓缩为：

• 朴素递归因重复求解同一子问题而低效，时间复杂度可呈指数增长；
• 用闭包持有缓存（数组或对象）即可把已算结果"记忆"下来，将指数级降为线性；
• memoize(func)通过"参数序列化 → 键值缓存 → 短路返回"三步实现任意函数的记忆化包装，多参数支持来自JSON.stringify的键生成；
• memoization 仅适用于纯函数，使用前需权衡序列化局限与内存占用。

想深入了解相关主题的读者，可继续阅读仓库中的关联 tip：Recursion, iteration and tail calls in JS（递归过程与尾调用优化）、Using JSON.Stringify（缓存键生成依赖的序列化机制）以及 Immutable structures and cloning（纯函数与状态管理的关系）。本 tip 的完整源文件见 _posts/en/javascript/2016-01-29-speed-up-recursive-functions-with-memoization.md，仓库还提供了简体中文、繁体中文与西班牙语的对照版本，便于多语言阅读。

• 教程