仅用递归统计1到n中数字1出现次数的代码处理大于100数值异常求解

问题根因排查 #

• 仅判断了数字的个位和十位，未处理百位及以上的高位，所以n≥100时会遗漏高位的1，比如数字101的百位1不会被统计
• n // 10 == 1的判断逻辑错误，当数字的十位是1但更高位还有值时（比如112，n//10是11，不等于1），会遗漏十位的1
• 递归终止逻辑仅处理了n=1的场景，没有覆盖所有边界情况

修复方案 #

拆分两个纯递归逻辑（全程无循环），分别负责单数字的1计数和范围累加：

1. 递归统计单个数字中1的出现次数
2. 递归遍历1到n的所有数字，累加每个数字的1的计数

修复后代码如下：

# 递归统计单个数字num中1的出现次数
def count_one_in_single_num(num: int) -> int:
    if num == 0:
        return 0
    current_bit_count = 1 if num % 10 == 1 else 0
    return current_bit_count + count_one_in_single_num(num // 10)

# 递归统计1到n所有数字的1的总出现次数
def number_of_ones(n: int) -> int:
    if n == 0:
        return 0
    return count_one_in_single_num(n) + number_of_ones(n - 1)

效果验证 #

• 输入n=13：输出6，和原有正确结果一致
• 输入n=100：输出21（1-99共20个1，100的百位有1个1，合计21），结果正确
• 输入n=101：输出23，结果正确

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