Python递归求解bears问题未遍历所有路径返回错误结果如何修复

• 分支逻辑提前终止：原代码只要命中任意一个条件分支就直接return递归结果，不会尝试其他并行的合法路径。例如输入250同时满足「被2整除」和「被5整除」两个条件，原代码直接走了除以2的分支，该分支走不通后直接返回False，不会再尝试减42的正确路径。
• 索引语法错误：代码中str(n[-2])写法错误，int类型的n不能直接用下标索引，需要先转为字符串再取最后两位，正确写法为str(n)[-2]。
• 潜在无限递归风险：当n最后一位为0时，最后两位的乘积为0，执行n - 0会导致n值不变，陷入无限递归，需要额外判断乘积非0再走该分支。

def bears(n: int) -> bool:
    if n == 42:
        return True
    if n < 42:
        return False
    # 只要任意一条路径返回True，整体结果就为True
    flag = False
    if n % 2 == 0:
        flag = flag or bears(n // 2)
    if (n % 3 == 0) or (n % 4 == 0):
        last_two_str = str(n)[-2:]
        product = int(last_two_str[0]) * int(last_two_str[1])
        # 乘积为0时跳过该分支，避免无限递归
        if product != 0:
            flag = flag or bears(n - product)
    if n % 5 == 0:
        flag = flag or bears(n - 42)
    return flag

print(bears(250))

运行上述代码输出为True，符合预期结果。

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