
本文介绍一种基于 indexOf 的高效递归字符计数方法,避免逐字符切片导致的深层调用栈,在不使用循环、正则和高级语言特性前提下,显著降低时间与空间复杂度。
本文介绍一种基于 `indexof` 的高效递归字符计数方法,避免逐字符切片导致的深层调用栈,在不使用循环、正则和高级语言特性前提下,显著降低时间与空间复杂度。
原始实现通过 str.slice(0, -1) 每次截去末尾字符进行递归,虽逻辑直观,但存在明显缺陷:无论目标字符是否出现,递归深度始终等于字符串长度。例如对 "lkjkBBSlkl"(长度 10)调用,将产生 10 层递归调用,即使其中仅含 2 个 'B'。这不仅浪费栈空间,还可能在处理长字符串时触发“Maximum call stack size exceeded”错误。
更优解是利用原生 String.prototype.indexOf(searchValue, fromIndex) 方法定位下一个匹配位置,仅在发现匹配时才递归,并跳转至该位置之后继续搜索:
function countSymbolRec(str, symbol, index = 0) {
const pos = str.indexOf(symbol, index);
if (pos === -1) return 0; // 未找到,终止递归
return 1 + countSymbolRec(str, symbol, pos + 1); // 找到一个,向后偏移继续
}
console.log(countSymbolRec("lkjkBBSlkl", "B", 0)); // 输出: 2
console.log(countSymbolRec("aaaa", "a", 0)); // 输出: 4
console.log(countSymbolRec("xyz", "p", 0)); // 输出: 0✅ 核心优势:
- 递归深度 = 目标字符实际出现次数(而非字符串总长度);
-
时间复杂度仍为 O(n)(
indexOf内部线性扫描),但常数因子更小,且无字符串拷贝开销(slice会创建新字符串); - 空间复杂度由 O(n) 优化为 O(k),其中 k 是匹配数量,大幅缓解栈压力。
⚠️ 注意事项:
- 必须显式提供初始
index = 0(或设为默认参数),确保首次调用从头开始; - 不要混淆
indexOf的第二个参数——它表示起始搜索索引,而非“跳过前 N 个字符”,因此pos + 1是安全的下一轮起点; - 该方案严格遵守约束:零循环、零正则、零高阶函数(如
filter/reduce),纯递归 + 基础字符串 API。
总结:在受限技术栈下,善用 indexOf 是提升递归效率的关键技巧。它将“被动遍历”转为“主动跳跃”,使算法行为更贴近问题本质——我们关心的是“有多少个”,而非“每个位置是不是”。

















