求解Codewars Square into Squares kata时递归栈溢出问题排查

嘿，我懂你碰到的麻烦了！在做这个平方分解的kata时，递归实现虽然逻辑直观，但遇到某些需要深层递归的测试用例时，很容易触发JS的最大调用栈限制，直接溢出。咱们来一步步拆解问题，找到靠谱的解决方案~

问题根源：无剪枝的暴力递归导致栈深度爆炸 #

你当前的递归逻辑是每次把num减1，尝试减去num²，但这种方式在某些场景下会产生极深的递归调用链。比如当需要分解的剩余值需要很多小平方数累加时，递归层数会一路飙升，直接超过JS引擎的调用栈上限（一般在几千层左右）。

举个例子，如果剩余值是一个很大的数，而你从接近它平方根的数开始往下试，每一步都要递归到很小的数，层数自然就上去了。

优化方案1：添加剪枝逻辑，大幅减少递归深度 #

最直接的优化是避免无效的递归调用，我们不需要从num-1一直试到1，而是只尝试那些平方不超过剩余值的数。具体来说：

• 每次计算当前能尝试的最大数：Math.min(num-1, Math.floor(Math.sqrt(whatsLeft)))
• 从这个最大数往下遍历尝试，一旦找到有效路径就返回，这样能大幅压缩递归层数

修改后的代码示例：

function sumSquares(n) {
  function decompose(num, whatsLeft, result) {
    // 计算当前可尝试的最大数，避免无效递归
    const maxCandidate = Math.min(num - 1, Math.floor(Math.sqrt(whatsLeft)));
    // 从大到小尝试，更快找到有效解
    for (let i = maxCandidate; i >= 1; i--) {
      const newRemaining = whatsLeft - i * i;
      if (newRemaining === 0) {
        // 找到解，拼接结果并返回
        return [...result, i];
      } else if (newRemaining > 0) {
        // 递归尝试更小的数，注意这里传入i作为新的num（保证递减）
        const subResult = decompose(i, newRemaining, [...result, i]);
        if (subResult) return subResult;
      }
      // newRemaining < 0的情况直接跳过，不用递归
    }
    // 所有尝试都失败，返回null
    return null;
  }
  
  const rawResult = decompose(n, n * n, []);
  // 题目要求结果按从小到大排列，所以反转一下
  return rawResult ? rawResult.reverse() : null;
}

这个优化能把递归层数降到很低，因为我们只在有意义的范围内尝试，不会做无用的递归。

优化方案2：改用迭代实现彻底避免栈溢出 #

如果某些极端测试用例还是触发栈溢出（虽然上面的剪枝已经很少出现这种情况），可以把递归改成迭代，用手动维护的栈来保存状态：

function sumSquares(n) {
  // 栈中保存每个状态：当前最大可尝试数、剩余值、当前结果数组
  const stack = [[n, n * n, []]];
  
  while (stack.length > 0) {
    const [currentNum, remaining, currentResult] = stack.pop();
    const maxCandidate = Math.min(currentNum - 1, Math.floor(Math.sqrt(remaining)));
    
    for (let i = maxCandidate; i >= 1; i--) {
      const newRemaining = remaining - i * i;
      if (newRemaining === 0) {
        return [...currentResult, i].reverse();
      } else if (newRemaining > 0) {
        // 把新状态压入栈，继续处理
        stack.push([i, newRemaining, [...currentResult, i]]);
      }
    }
  }
  
  return null;
}

迭代版本完全不会受到JS调用栈的限制，因为我们用的是自己维护的栈数据结构，而不是函数调用栈。

测试验证 #

把这两个版本替换你的原代码，再去跑之前溢出的测试用例，应该就能顺利通过啦！

内容的提问来源于stack exchange，提问作者OctaviaLo