教程【免费下载链接】jstipsThis is about useful JS tips!项目地址https://gitcode.com/gh_mirrors/js/jstips点击查看免费下载本文源自 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.mdvar 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);逐行拆解其工作原理cache {}是闭包内的键值缓存键为参数序列化后的字符串值为对应计算结果Array.prototype.slice.call(arguments)把类数组对象arguments转换为真正的数组从而能调用数组方法JSON.stringify(...)将参数列表序列化为唯一字符串键——这是本实现的关键不同参数组合对应不同缓存键天然支持多参数函数key in cache ? cache[key] : (cache[key] func.apply(this, arguments))是短路求值的经典写法键已存在则直接返回缓存值否则调用原函数func计算并写入缓存后返回通过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 版相比变化一目了然维度ES5 版本ES6 版本参数收集Array.prototype.slice.call(arguments)...args剩余参数直接得到真数组键生成JSON.stringify(数组)JSON.stringify(args)省去显式转换调用原函数func.apply(this, arguments)func(...args)展开参数闭包变量声明var cache {}const cache {}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()可以用于很多其他场景并给出了两个经典示例。最大公约数 GCDvar 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 时值得注意的边界缓存键的序列化局限JSON.stringify无法正确处理function、undefined、Symbol以及循环引用对象遇到这些参数时键生成会失败或产生歧义如undefined与缺失参数可能序列化出相同键。若函数参数包含这类值需改用自定义键函数对象参数的语义JSON.stringify按对象内容生成键两个内容相同但引用不同的对象会命中同一缓存——多数情况下符合预期但若函数依赖对象身份identity或内部状态则可能得到错误结果内存占用缓存随调用参数组合的增长而无限膨胀属于典型的空间换时间。对参数组合数量极大或参数为大型对象的高频函数需要引入缓存淘汰LRU或容量上限策略纯函数前提memoization 只对确定性纯函数安全。如果原函数依赖外部可变状态、当前时间、随机数或产生副作用缓存结果将失去意义——这是使用 memoize 之前必须先确认的前提this的处理ES5 版本通过func.apply(this, arguments)保留了this绑定因此可用于对象方法ES6 箭头函数版本中箭头函数不绑定自己的this若被包装函数依赖动态this需注意上下文差异与函数式风格的关系仓库中 _posts/en/javascript/2017-06-14-immutable-structures-and-cloning.md 讨论了不可变结构与克隆的话题——memoization 在函数式编程中常与引用透明引用透明即相同输入永远产生相同输出配合使用纯函数是安全记忆化的前提这一原则同样适用于本 tip。小结本 tip 以斐波那契为引子完整覆盖了 memoization 的三层递进朴素递归暴露重复计算问题 → 闭包缓存数组给出专用解 → 通用memoize高阶函数给出可复用抽象ES5/ES6 双版本并以 GCD、阶乘验证其通用性。其核心要点可浓缩为朴素递归因重复求解同一子问题而低效时间复杂度可呈指数增长用闭包持有缓存数组或对象即可把已算结果记忆下来将指数级降为线性memoize(func)通过参数序列化 → 键值缓存 → 短路返回三步实现任意函数的记忆化包装多参数支持来自JSON.stringify的键生成memoization 仅适用于纯函数使用前需权衡序列化局限与内存占用。想深入了解相关主题的读者可继续阅读仓库中的关联 tipRecursion, 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仓库还提供了简体中文、繁体中文与西班牙语的对照版本便于多语言阅读。赞分享教程【免费下载链接】jstipsThis is about useful JS tips!项目地址https://gitcode.com/gh_mirrors/js/jstips点击查看免费下载相关推荐用 JavaScript 递归实战斐波那契数列与归并排序Fibonacci Merge Sort用 JavaScript 递归实战斐波那契数列与归并排序Fibonacci Merge Sort 导读 本篇实战项目来自 curriculum htt文档教程教育Floccus跨浏览器书签同步完整操作手册打造你的私有书签云Floccus跨浏览器书签同步完整操作手册打造你的私有书签云 在当今多设备、多浏览器的数字生活中书签同步已成为现代互联网用户的核心需求。Floccus作为一前端移动开发数据同步Python递归算法优化gh_mirrors/da/data-science-interviews项目阶乘与斐波那契尾递归实现Python递归算法优化gh_mirrors/da/data science interviews项目阶乘与斐波那契尾递归实现 递归是Python编程中解决复文档知识库数据科学教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 用 Memoization 加速递归函数：jstips 第 29 期斐波那契优化实战（ES5/ES6）
教程【免费下载链接】jstipsThis is about useful JS tips!项目地址https://gitcode.com/gh_mirrors/js/jstips点击查看免费下载本文源自 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.mdvar 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);逐行拆解其工作原理cache {}是闭包内的键值缓存键为参数序列化后的字符串值为对应计算结果Array.prototype.slice.call(arguments)把类数组对象arguments转换为真正的数组从而能调用数组方法JSON.stringify(...)将参数列表序列化为唯一字符串键——这是本实现的关键不同参数组合对应不同缓存键天然支持多参数函数key in cache ? cache[key] : (cache[key] func.apply(this, arguments))是短路求值的经典写法键已存在则直接返回缓存值否则调用原函数func计算并写入缓存后返回通过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 版相比变化一目了然维度ES5 版本ES6 版本参数收集Array.prototype.slice.call(arguments)...args剩余参数直接得到真数组键生成JSON.stringify(数组)JSON.stringify(args)省去显式转换调用原函数func.apply(this, arguments)func(...args)展开参数闭包变量声明var cache {}const cache {}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()可以用于很多其他场景并给出了两个经典示例。最大公约数 GCDvar 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 时值得注意的边界缓存键的序列化局限JSON.stringify无法正确处理function、undefined、Symbol以及循环引用对象遇到这些参数时键生成会失败或产生歧义如undefined与缺失参数可能序列化出相同键。若函数参数包含这类值需改用自定义键函数对象参数的语义JSON.stringify按对象内容生成键两个内容相同但引用不同的对象会命中同一缓存——多数情况下符合预期但若函数依赖对象身份identity或内部状态则可能得到错误结果内存占用缓存随调用参数组合的增长而无限膨胀属于典型的空间换时间。对参数组合数量极大或参数为大型对象的高频函数需要引入缓存淘汰LRU或容量上限策略纯函数前提memoization 只对确定性纯函数安全。如果原函数依赖外部可变状态、当前时间、随机数或产生副作用缓存结果将失去意义——这是使用 memoize 之前必须先确认的前提this的处理ES5 版本通过func.apply(this, arguments)保留了this绑定因此可用于对象方法ES6 箭头函数版本中箭头函数不绑定自己的this若被包装函数依赖动态this需注意上下文差异与函数式风格的关系仓库中 _posts/en/javascript/2017-06-14-immutable-structures-and-cloning.md 讨论了不可变结构与克隆的话题——memoization 在函数式编程中常与引用透明引用透明即相同输入永远产生相同输出配合使用纯函数是安全记忆化的前提这一原则同样适用于本 tip。小结本 tip 以斐波那契为引子完整覆盖了 memoization 的三层递进朴素递归暴露重复计算问题 → 闭包缓存数组给出专用解 → 通用memoize高阶函数给出可复用抽象ES5/ES6 双版本并以 GCD、阶乘验证其通用性。其核心要点可浓缩为朴素递归因重复求解同一子问题而低效时间复杂度可呈指数增长用闭包持有缓存数组或对象即可把已算结果记忆下来将指数级降为线性memoize(func)通过参数序列化 → 键值缓存 → 短路返回三步实现任意函数的记忆化包装多参数支持来自JSON.stringify的键生成memoization 仅适用于纯函数使用前需权衡序列化局限与内存占用。想深入了解相关主题的读者可继续阅读仓库中的关联 tipRecursion, 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仓库还提供了简体中文、繁体中文与西班牙语的对照版本便于多语言阅读。赞分享教程【免费下载链接】jstipsThis is about useful JS tips!项目地址https://gitcode.com/gh_mirrors/js/jstips点击查看免费下载相关推荐用 JavaScript 递归实战斐波那契数列与归并排序Fibonacci Merge Sort用 JavaScript 递归实战斐波那契数列与归并排序Fibonacci Merge Sort 导读 本篇实战项目来自 curriculum htt文档教程教育Floccus跨浏览器书签同步完整操作手册打造你的私有书签云Floccus跨浏览器书签同步完整操作手册打造你的私有书签云 在当今多设备、多浏览器的数字生活中书签同步已成为现代互联网用户的核心需求。Floccus作为一前端移动开发数据同步Python递归算法优化gh_mirrors/da/data-science-interviews项目阶乘与斐波那契尾递归实现Python递归算法优化gh_mirrors/da/data science interviews项目阶乘与斐波那契尾递归实现 递归是Python编程中解决复文档知识库数据科学教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考