企业官网建设流程全解析

• 教程
• 文档

导读：递归代码虽然直观优雅，却往往因重复计算和函数调用开销而成为性能瓶颈。本文以计算斐波那契数列第 n 项为贯穿案例，系统讲解 30 seconds of code 项目中总结的两大优化技巧——计算结果记忆化（Memoization）与改用迭代实现，并结合仓库源码剖析两者的执行过程、资源开销与适用场景。读完本文，你将能对递归函数进行性能分析，并针对不同调用模式选择最优优化策略。

递归函数：问题拆解与重复计算的开销

递归是一种编程技术，其核心思路是将最终问题分解为同一问题的更小实例，逐个求解后再组合出完整答案。最常见的实现方式是一个不断调用自身的函数：每次调用都把问题规模缩小一档，直到抵达一个解平凡易得或已知的实例（即基线条件 base case）。

在 30 seconds of code 仓库中，递归入门文档对基线条件做了清晰界定：当函数不再满足递归条件时即命中基线条件并返回结果，从而打断递归循环；若不存在这样的条件，函数将无限自调用，最终导致栈溢出（stack overflow）。

计算斐波那契数列第 n 项是递归的经典示例。使用递归在 JavaScript 中实现如下：

const fibonacciNumber = n => n < 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n;

这个实现简洁、易读，但隐藏着明显的性能问题：每个n对应的子问题会被反复计算多次。为了更好地理解执行过程，可以在每次return前加入console.log()调用，追踪真实的调用与返回顺序：

const fibonacciNumber = n => { console.log(`[CALLED] fibonacciNumber(${n})`); const r = n >= 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n; console.log(`[RETURN] ${r} for n=${n}`); return r; } fibonacciNumber(4); // [CALLED] fibonacciNumber(4) // [CALLED] fibonacciNumber(3) // [CALLED] fibonacciNumber(2) // [CALLED] fibonacciNumber(1) // [RETURN] 1 for n=1 // [CALLED] fibonacciNumber(0) // [RETURN] 0 for n=0 // [RETURN] 1 for n=2 // [CALLED] fibonacciNumber(1) // [RETURN] 1 for n=1 // [RETURN] 2 for n=3 // [CALLED] fibonacciNumber(2) // [CALLED] fibonacciNumber(1) // [RETURN] 1 for n=1 // [CALLED] fibonacciNumber(0) // [RETURN] 0 for n=0 // [RETURN] 1 for n=2 // [RETURN] 3 for n=4

从输出可以看到：对每一个n，fibonacciNumber都会被调用两次（一次传入n - 1，一次传入n - 2），并持续到以1或0为参数调用为止。这种实现虽然容易编写和理解，但同一个值会被重复计算，效率低下。随着n增大，调用次数呈指数级增长，性能问题会急剧放大。这一点在仓库的斐波那契文档中也有印证：递归方案更优雅简洁，但会因函数调用的额外开销而可能更低效。

优化技巧一：计算结果记忆化（Memoization）

针对重复计算问题，第一种优化技巧是记忆化。其思想是：把每次计算的结果缓存起来，下次遇到相同输入时直接读取缓存，而不再重复计算。仓库中的记忆化专题文章对记忆化的定义和适用标准做了系统阐述，可总结为：

• 记忆化依赖缓存存储已完成工作的结果，目的是避免同一份工作被重复执行；
• 它适合耗时长、计算代价高的函数；
• 它加速的是后续调用，因此最适合"相同条件下被多次调用"的函数；
• 结果存储在内存中，若同一函数在差异很大的参数下被反复调用，缓存命中率低，反而不宜使用记忆化。

下面是经过记忆化改造的fibonacciNumber函数。缓存使用Map实现——Map以键值对存储数据且记住键的插入顺序，非常适合用函数入参做键、计算结果做值：

const fibonacciCache = new Map(); const fibonacciNumber = n => { console.log(`[CALL] fibonacciNumber(${n})`); const cacheKey = `${n}`; let r; if(fibonacciCache.has(cacheKey)) { r = fibonacciCache.get(cacheKey); console.log(`[MEMO] Cache hit for ${n}: ${r}`); } else { r = n >= 2 ? fibonacciNumber(n - 1) + fibonacciNumber(n - 2) : n; fibonacciCache.set(cacheKey, r); console.log(`[CALC] Computed and stored value for ${n}: ${r}`); } return r; } fibonacciNumber(4); // [CALL] fibonacciNumber(4) // [CALL] fibonacciNumber(3) // [CALL] fibonacciNumber(2) // [CALL] fibonacciNumber(1) // [CALC] Computed and stored value for 1: 1 // [CALL] fibonacciNumber(0) // [CALC] Computed and stored value for 0: 0 // [CALC] Computed and stored value for 2: 1 // [CALL] fibonacciNumber(1) // [MEMO] Cache hit for 1: 1 // [CALC] Computed and stored value for 3: 2 // [CALL] fibonacciNumber(2) // [MEMO] Cache hit for 2: 1 // [CALC] Computed and stored value for 4: 3

对比追踪输出可以发现：每个n的值只被真正计算一次，后续同参数的调用全部命中缓存（输出中的[MEMO] Cache hit）。斐波那契数列本身的单个数值计算并不昂贵，但如果换成计算代价更高的问题，或把n调大（此时需要计算的数值个数显著增加），记忆化带来的收益会非常可观。

通用化的记忆化实现：memoize与 Proxy 方案

在实际项目中，逐函数手写缓存既繁琐又易错。仓库的记忆化专题文档提供了两种可复用的通用实现。第一种是手写高阶函数memoize，用Map缓存每次调用的返回值，并支持通过cached.cache访问缓存本身：

const memoize = fn => { const cache = new Map(); const cached = function (val) { return cache.has(val) ? cache.get(val) : cache.set(val, fn.call(this, val)) && cache.get(val); }; cached.cache = cache; return cached; }; // 该函数很慢，适合做记忆化 const anagrams = str => { if (str.length <= 2) return str.length === 2 ? [str, str[1] + str[0]] : [str]; return str .split('') .reduce( (acc, letter, i) => acc.concat( anagrams(str.slice(0, i) + str.slice(i + 1)).map(val => letter + val) ), [] ); }; const anagramsCached = memoize(anagrams); anagramsCached('javascript'); // 首次调用耗时很长 anagramsCached('javascript'); // 由于已缓存，第二次调用几乎瞬间返回

第二种是借助 JavaScript 的Proxy 对象，通过handler.apply()陷阱拦截函数调用：命中缓存则直接返回缓存结果，否则调用原函数并缓存结果后再返回：

const memoize = fn => new Proxy(fn, { cache: new Map(), apply (target, thisArg, argsList) { let cacheKey = argsList.toString(); if(!this.cache.has(cacheKey)) this.cache.set(cacheKey, target.apply(thisArg, argsList)); return this.cache.get(cacheKey); } }); const fibonacci = n => (n <= 1 ? 1 : fibonacci(n - 1) + fibonacci(n - 2)); const memoizedFibonacci = memoize(fibonacci); for (let i = 0; i < 100; i ++) fibonacci(30); // ~5000ms for (let i = 0; i < 100; i ++) memoizedFibonacci(30); // ~50ms

两种通用实现都可直接用于替换本文案例中的手写缓存版本，从而在保留递归代码可读性的同时获得性能提升。

优化技巧二：改用迭代实现（Iteration）

第二种优化技巧源于对递归定义本身的"反向思考"：既然我们可以先求解较小规模的问题、再用其结果推导更大规模问题的解，那么从小问题向大问题逐步推进同样可行——只不过这次不是递归调用，而是迭代。对于fibonacciNumber，该思路的实现如下：

const fibonacciNumber = n => { let r = 0, l = 1, s = 0; for(let i = 0; i < n; i++) { r = l; l = s; s = r + l; console.log(`[CALC] i = ${i}: r = ${r}, l = ${l}, s = ${s}`); } return s; } fibonacciNumber(4); // [CALC] i = 0: r = 1, l = 0, s = 1 // [CALC] i = 1: r = 0, l = 1, s = 1 // [CALC] i = 2: r = 1, l = 1, s = 2 // [CALC] i = 3: r = 1, l = 2, s = 3

迭代版本的执行轨迹与记忆化版本的计算量相同，但表现更优，原因主要有两点：

1. 没有缓存占用内存。迭代方案仅用三个局部变量r、l、s滚动推进，而记忆化方案需要Map缓存所有中间结果，占用更多内存资源；
2. 没有递归调用与缓存命中检查的开销。迭代省去了每次子问题求解时的函数调用、栈帧分配与cache.has()/cache.get()等检查，代码执行所需资源更少。

仓库的斐波那契文档还给出了另一种迭代风格——用数组存储序列，逐项生成到第 n 项：

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]

如果需要返回整个序列（而非单个第 n 项），上述基于数组的迭代实现更贴合需求；若只需单个数值，滚动变量的版本则最节省空间。

如何选择：记忆化还是迭代？

两种优化方案并非孰优孰劣，而是取决于递归代码的真实使用场景。优化时必须非常谨慎，针对自己已知或预期更常见的调用模式来权衡：

• 记忆化更强大的场景：递归函数需要以不同参数被多次调用。此时缓存可以在多次调用之间持续保留，后续调用直接复用历史结果，累计收益远超单次计算。例如上述anagrams示例中，同一字符串的变位词只计算一次，后续调用近乎瞬时返回；
• 迭代更快的场景：递归计算使用频率较低。此时缓存无法被复用，反而白白占用内存，迭代方案以更少的资源开销胜出；
• 若同一次计算中参数差异很大、缓存命中率很低，则记忆化几乎无收益，应优先考虑迭代或调整缓存策略。

综合来看，本文介绍的两种技巧可以组合运用：先通过递归快速验证正确性，再按实际调用模式选择记忆化或迭代落地优化。无论选择哪种方案，都应像文中示例一样通过日志或基准测试（如仓库记忆化文档中100次调用fibonacci(30)对比毫秒级差异的做法）验证真实收益，避免盲目优化。更多相关实现可继续阅读仓库中的记忆化专题、递归入门与斐波那契序列生成文档。

• 教程
• 文档