使用递归实现二进制比特计数时如何不调用len返回数组长度？

实现方案 #

完全可以在保留原有递归逻辑的前提下实现需求，你只需要将原代码中用于存储1比特位的数组替换为数值计数器即可，无需在调用侧使用len()方法。

修改后代码 #

def count_bits(n):
    # 先统计当前数值最低位的1的数量
    count = 1 if n % 2 == 1 else 0
    base = n // 2
    if base:
        # 累加递归得到的高位部分的1的数量
        count += count_bits(base)
    return count 

print(count_bits(1234)) # 输出 5，符合预期

改动说明 #

• 原有逻辑的递归流程完全保留，仅将数组累加操作替换为数值累加
• 新增了当前输入值最低位的判断逻辑，修复了原代码遗漏统计最低位1的问题
• 递归调用直接返回子问题的1比特位计数，直接累加即可得到最终结果，全程不需要操作数组或调用len()方法

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