Python递归实现二进制间隙计算时出现递归错误及结果异常的问题排查

嘿，作为编程新手能尝试用递归实现需求已经超棒啦！我来帮你拆解下代码里的问题，一步步把它修好～

先说说代码里的核心问题 #

1. 除法操作引发的无限递归
   你用了n / 2，这在Python里会返回浮点数（比如3/2得到1.5），浮点数的%2运算永远没法让n最终变成0，递归就会无限循环下去——这就是输入奇数时触发递归错误的根源。得换成整数除法//，保证每次递归的n都是整数。

2. 返回值逻辑完全偏离需求
   当前的return ans and numofZeros完全不对：逻辑与and在这里只会返回布尔值或数值的“真值”，根本没法跟踪和返回最长的二进制间隙长度。我们需要在递归过程中同时记录当前找到的最大间隙和正在统计的连续0数量。

修正后的递归代码 #

我调整了递归参数，新增max_gap来跟踪最长间隙，同时修复了除法和返回值逻辑：

def binary_gap(n, found_first_one=False, current_zeros=0, max_gap=0):
    # 递归终止条件：n被整除到0时，返回记录的最长间隙
    if n == 0:
        return max_gap
    
    bit = n % 2
    # 处理当前位是1的情况
    if bit == 1:
        if found_first_one:
            # 不是第一个1，把当前统计的0和已有的最大间隙比较，更新最大值
            new_max = max(max_gap, current_zeros)
        else:
            # 第一次遇到1，还没有有效间隙，max_gap保持不变
            new_max = max_gap
        # 递归处理下一位，标记已找到第一个1，重置当前0的计数
        return binary_gap(n // 2, True, 0, new_max)
    else:
        # 处理当前位是0的情况
        if found_first_one:
            # 已经找到第一个1，继续统计连续0的数量
            return binary_gap(n // 2, True, current_zeros + 1, max_gap)
        else:
            # 还没遇到第一个1，跳过前导0，参数不变
            return binary_gap(n // 2, False, 0, max_gap)

print(binary_gap(int(input("Please enter a number: "))))

代码逻辑拆解 #

• 参数作用：
  • found_first_one：标记是否已经遇到第一个二进制位的1（用来跳过前导无效0）
  • current_zeros：当前正在统计的连续0的数量
  • max_gap：目前找到的最长二进制间隙长度
• 递归终止：当n被整除到0时，返回记录的max_gap
• 遇到1时：如果是第一个1就标记状态；如果不是，就把当前统计的0和max_gap对比更新最大值，然后重置当前0的计数
• 遇到0时：只有在已经找到第一个1的情况下，才统计0的数量，否则直接跳过

测试验证 #

• 输入10（二进制1010）：返回1 ✅
• 输入15（二进制1111）：返回0 ✅
• 输入41（二进制101001）：返回2 ✅

这样就解决了你遇到的偶数返回0和奇数递归错误的问题啦～

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