
本文介绍一种基于 indexOf 的高效递归字符计数方案,避免逐字符切片导致的深度递归,显著降低调用栈规模,尤其适用于长字符串场景。
本文介绍一种基于 `indexof` 的高效递归字符计数方案,避免逐字符切片导致的深度递归,显著降低调用栈规模,尤其适用于长字符串场景。
在纯递归约束下(禁用循环、正则表达式及内置高阶方法如 filter/reduce),原始实现采用 str.slice(0, -1) 逐层缩短字符串,虽逻辑直观,但存在严重性能隐患:无论目标字符出现频率高低,递归深度始终等于字符串长度。例如对 "lkjkBBSlkl"(长度 10)调用,即使仅含 2 个 'B',仍需 10 层递归,极易触发栈溢出(Stack Overflow)。
更优解是利用 String.prototype.indexOf(searchValue, fromIndex) —— 它原生支持从指定位置开始查找,且完全符合题目限制(非“高级语言工具”,属基础字符串 API)。改进后的递归逻辑如下:
function countSymbolRec(str, symbol, index = 0) {
const pos = str.indexOf(symbol, index);
if (pos === -1) return 0; // 未找到,终止递归
return 1 + countSymbolRec(str, symbol, pos + 1); // 找到则计数+1,从下一位置继续
}
console.log(countSymbolRec("lkjkBBSlkl", "B")); // 2
console.log(countSymbolRec("AAAA", "A")); // 4
console.log(countSymbolRec("xyz", "a")); // 0该方案的核心优势在于:递归深度 = 目标字符实际出现次数。对比分析如下:
- ✅ 最佳情况(无匹配):原方案递归
L层,新方案仅1层; - ✅ 平均情况(约
L/2次匹配):原方案L层,新方案约L/2层; - ⚠️ 最坏情况(全为匹配字符):两者均为
L层,但新方案避免了slice创建新字符串的内存开销。
注意事项:
- 必须显式传递起始索引
index(默认0),确保每次查找不重复扫描已处理区域; -
indexOf区分大小写,若需忽略大小写,可先统一转为小写(如str.toLowerCase().indexOf(symbol.toLowerCase(), index)),但需注意这会创建新字符串——权衡后仍优于slice的频繁拷贝; - 尾递归优化(TCO)在 JavaScript 中尚未广泛支持,因此深度仍需谨慎控制;对于超长字符串(如 >10⁴ 字符),建议结合迭代或分治策略。
综上,在题设约束下,以 indexOf 驱动的跳跃式递归,是兼顾简洁性、效率与可读性的最优实践。

















