JS求解欧拉计划14题记忆化优化反耗时更长问题排查

你的记忆化实现存在根本性逻辑错误，完全没有发挥缓存复用的作用，反而新增了大量无意义的对象读写开销，这就是加入记忆化后耗时反而更长的直接原因。

原记忆化代码的核心bug #

// 你写的记忆化版本核心逻辑
function recurseWrapper(n) {
    let count = 0;
    let memo = {} // Bug1: 缓存定义位置错误

    function recurseCollatzSequence(n) {
        if (n in memo) {
            return memo[n];
        } else {
            if (n === 1) {
                return; // Bug2: 终止条件返回undefined，无有效长度值
            } else if (n % 2 === 0) {
                count++; // Bug3: 用闭包全局变量计数，和子问题返回值不匹配
                memo[n / 2] = recurseCollatzSequence((n / 2)) // Bug4: 缓存key存的是下一跳节点，不是当前入参n
            } else {
                count++;
                memo[(3 * n) + 1] = recurseCollatzSequence(((3 * n) + 1))
            }
            return count
        }

    }
    return recurseCollatzSequence(n);
}

具体问题拆解：

• 缓存作用域完全失效：memo定义在recurseWrapper内部，而主循环每遍历一个起始数就会调用一次recurseWrapper，每次调用都会新建一个空的memo对象，不同起始数的计算结果完全无法跨调用共享，记忆化最核心的复用价值为0。
• 缓存键值存储逻辑完全错误：你在递归中存储的key是下一个跳转节点（偶数存n/2、奇数存3n+1），从来没有存储当前入参n对应的序列长度；同时查询缓存时查的是当前入参n，就算缓存里有值也永远命中不了。
• 缓存值完全无效：你用闭包内的全局变量count做计数，递归返回的count是从当前入口到终点的总步数，根本不是key对应子节点的序列长度，加上n=1的终止条件返回undefined，存进memo的值全是错误数据。
• 额外开销无任何收益：每次递归都要执行对象属性查询、写入操作，这些操作本身有固定性能成本，但因为缓存完全没起到复用作用，所有成本都是净支出，自然比无记忆化版本更慢。

正确的记忆化实现 #

要让记忆化真正提速，只需要修正三个逻辑点：

1. 将缓存对象放到全局/主函数作用域下，保证所有起始数的计算复用同一个缓存，预先写入终止条件memo[1] = 1
2. 去掉闭包全局计数器，递归函数直接返回当前入参n对应的序列长度：n的长度 = 1 + 下一跳节点的长度
3. 每次计算出n对应的长度后，先存入memo[n]再返回，命中缓存时直接返回存储值

修正后的核心代码：

// 全局共享缓存
const memo = { 1: 1 };
function getCollatzLength(n) {
    if (memo[n]) return memo[n];
    const next = n % 2 === 0 ? n / 2 : 3 * n + 1;
    const length = 1 + getCollatzLength(next);
    memo[n] = length;
    return length;
}

function longestCollatzSequence(limit) {
    let maxLength = 0;
    let result = 1;
    for (let i = limit; i > 1; i--) {
        const currentLen = getCollatzLength(i);
        if (currentLen > maxLength) {
            maxLength = currentLen;
            result = i;
        }
    }
    return result;
}

这个版本计算1000000规模的输入时，速度会比你当前的无记忆化版本快5~10倍，所有重复经过的Collatz节点都只需要计算一次。

内容的提问来源于stack exchange，提问作者sadat-saim