在 LeetCode 279“完全平方数”里，很多人会先写出带 for 的递归枚举，再尝试把循环改造成“取 / 不取”两条递归分支。难点不在于语法替换，而在于状态是否还能覆盖所有合法组合、边界是否会提前截断，以及缓存有没有真正参与计算。下面就按这三个问题拆开讲，并给出一份可以安全移除内层循环的记忆化递归实现。
题目目标与改写递归的难点
LeetCode 279. Perfect Squares 要求求出组成正整数 n 所需的最少完全平方数个数。比如 12 = 4 + 4 + 4，结果就是 3。
常规递归解法通常会写一个循环，枚举所有满足 i * i <= n 的平方数，再递归求剩余部分的最优解。有人会进一步想：既然循环本质上也是在做选择，那能不能用额外状态 ind 表示当前考虑的平方根，把枚举过程改写成两条分支？
这个方向本身没有问题，但一旦把显式循环展开成递归，就必须重新确认三件事：
- 当前状态能不能表达“同一个平方数可重复使用”；
- 基础情况的判断顺序会不会把正确答案挡掉；
- 记忆化是否和新的状态定义保持一致。
如果这三点里有一处处理错了，程序即使能跑，也很容易得到错误结果，或者直接因为指数级递归超时。
移除内层循环时最常见的三个错误
1. 状态设计错了，导致平方数不能重复使用
最关键的问题，往往出在“取当前平方数”这一步。
错误写法类似这样：
dfs(num - ind*ind, ind+1)这表示一旦选了 ind²，下一步就强制去看更大的平方数。问题是题目允许同一个平方数重复使用，比如 12 = 4 + 4 + 4 是合法解。如果第一次取了 4 之后就把 ind 推到下一个位置，那么后面就再也不能继续选 4 了，状态空间会被错误压缩，直接漏解。
正确思路是：当你选择当前平方数后，下一层仍然要保留当前索引，也就是继续允许重复拿同一个平方数。
dfs(num - ind*ind, ind)这里的含义不是“卡在当前位置不动”，而是“当前值还能继续被选”。这是把循环改写成分支递归时最容易忽略、但影响最大的地方。
2. 边界判断顺序不当，可能把 num === 0 判丢
第二个常见错误，是把边界写成先判断索引是否越界，再判断 num === 0。
例如先写：
if (ind > sqrt(num)) return Infinity;
if (num === 0) return 0;这种顺序会带来一个问题：当递归已经刚好把 num 减到 0 时，本应立刻返回 0，表示已经完成组合；但如果你先做了依赖 num 的范围判断，就可能提前命中“无解”分支，返回 Infinity，把本来成立的答案覆盖掉。
因此，num === 0 必须作为最高优先级基础情况，优先返回。
此外，用：
ind * ind > num来代替：
ind > Math.sqrt(num)会更稳妥。一方面不需要浮点运算，另一方面也少了一次函数调用，逻辑上更直接。
3. 声明了缓存，却没有真正记忆化
第三类问题是形式上有缓存对象，比如：
const hash = {}但递归过程中既不读，也不写。这种写法实际上和没有记忆化没有区别，搜索树会反复计算同一个子问题，复杂度迅速退化到指数级，LeetCode 上基本必然超时。
真正的记忆化至少要做到两件事：
- 递归开头优先读缓存；
- 求出最优值后及时写回缓存。
这一点看起来基础，但在“重写递归结构”的场景里很容易漏掉，因为开发者往往把精力都放在分支转移上，忘了让缓存和新的状态定义同步生效。
修正后的记忆化递归实现
把上面三个问题都修正后，可以得到下面这份实现：
var numSquares = function(n) {
const cache = {};
const dfs = (num, ind) => {
if (num < 0) return Infinity;
if (num === 0) return 0; // 必须最先检查！
if (cache[num] !== undefined) return cache[num];
// 避免 Math.sqrt：直接比较平方
if (ind * ind > num) return Infinity;
// 分支1：跳过 ind²，尝试更大的平方数
const n_take = dfs(num, ind + 1);
// 分支2：选用 ind²（可重复），num 减去该值，ind 不变
const take = 1 + dfs(num - ind * ind, ind);
const min = Math.min(n_take, take);
cache[num] = min; // 写入缓存
return min;
};
return dfs(n, 1);
};这段代码的结构可以直接理解为：
dfs(num, ind + 1)：跳过当前平方数，去尝试更大的平方数；1 + dfs(num - ind * ind, ind)：选择当前平方数一次，并允许之后继续选择它。
两条分支共同覆盖了“用或不用当前平方数”的完整搜索过程。由于有缓存，同一个 num 对应的最优解不会被反复计算。
为什么这里的缓存通常只需要用 num
这部分最容易引发疑问：既然递归函数有两个参数 (num, ind)，为什么缓存却只用 num 做键？
文中的核心判断是：在这个问题设定下，我们从 ind = 1 开始搜索，并且允许重复使用平方数，目标始终是求某个 num 的最少拆分个数。也就是说，真正决定最优解的是“剩余值是多少”，而不是“当前从第几个平方数开始看”。
换句话说，只要搜索过程能够覆盖全部合法平方数组合，那么 dfs(num) 的最优值就应当稳定存在。ind 更像是控制遍历顺序的辅助变量，而不是最终答案的决定性状态。
因此，缓存写成：
cache[num]通常就够了。这样做的直接收益是：
- 缓存键更简单；
- 空间开销更小；
- 不会因为把遍历控制变量也塞进键里，导致命中率下降。
当然，这个结论成立的前提，是你的递归转移本身已经保证了组合覆盖完整，尤其是“取当前平方数后不推进 ind”这一点必须正确。否则即使缓存键只用 num，也只是把错误结果更快地复用出去。
复杂度、适用场景与一个判断标准
需要说明的是，去掉显式 for 循环，并不代表问题本质变了。它仍然是在完全平方数集合上做搜索，只是把枚举动作改写成了递归分支。
从复杂度角度看，这类记忆化递归通常仍可视为 O(n√n) 量级。相比完全暴力搜索已经好很多，但如果你追求更稳定的性能和更小的常数，标准动态规划往往更直接：
dp[i] = min(dp[i - j*j] + 1)再进一步，还可以使用数学方法，例如四平方定理和三平方判定。不过对于很多面试和题解场景来说，这份递归版实现依然有价值，因为它能帮助你真正看清“状态设计”和“转移完备性”之间的关系。
判断这种“去循环改递归”写法是否靠谱，可以抓一个很实用的标准：
- 是否还能重复使用合法元素；
- 是否先处理成功到达终点的基础情况；
- 缓存键是否只包含真正影响最优解的状态。
这三项都能答清楚，代码一般就不会偏得太远。
结语
把内层循环移除，并不是单纯把枚举改写成两个递归调用，而是一次完整的状态重建。对于完全平方数问题，真正要守住的点只有几个：选择当前平方数后必须允许重复使用、num === 0 必须优先返回、记忆化必须和状态定义一致。
理解了这几点，再看这类“取 / 不取”递归题，重点就不再是有没有 for 循环，而是搜索空间是否被完整、准确地表达出来。
