如何仅使用递归统计字符串中子串的出现次数

你的原有代码的判断条件存在逻辑偏差：

• 同时判定str(sub) in str(s)和str(sub) == str(s)时，只有剩余字符串和子串完全相等才会计数，会漏掉子串出现在剩余字符串开头、后面还有其他字符的场景
• 仅保留str(sub) in str(s)时，同一个子串匹配会在多次递归中被重复检测到，导致计数远高于预期

正确的判断逻辑是：每次递归仅检查当前剩余字符串的前缀是否和子串完全匹配，匹配则计数加1，之后无论是否匹配，都将字符串右移1位进入下一层递归即可，同时可以优化递归终止条件，剩余字符串长度小于子串长度时直接返回0，减少无效递归：

def count_occurrences(sub, s):
    sub_len = len(sub)
    # 递归终止条件：剩余字符串长度小于子串长度，不可能完成匹配
    if len(s) < sub_len:
        return 0
    # 仅检查当前剩余字符串的前缀是否和子串匹配
    if s[:sub_len] == sub:
        return 1 + count_occurrences(sub, s[1:])
    else:
        return count_occurrences(sub, s[1:])

print(count_occurrences('ill', 'Bill will still get ill'))

运行上述代码会输出预期结果4，符合需求。

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