Python递归字典查找函数无法检测循环返回False问题排查

问题背景 #

实现字典键值的递归查找逻辑（俗称“兔子洞”）：从指定key出发，用其对应的value作为下一个key继续查找；若出现重复key（避免无限循环）则返回False，若遇到无对应value的key则返回该key。

当前实现的函数rabbit_hole在测试输入"rat"时，返回结果为"ram"，但预期应为False。测试输入输出对比：

• 实际输出：ant、hen、doe、yak、ram
• 预期输出：ant、hen、doe、yak、False

原代码：

d = {'bat': 'pig', 'pig': 'cat', 'cat': 'dog', 'dog': 'ant', 'cow': 'bee', 'bee': 'elk', 'elk': 'fly', 'ewe': 'cod', 'cod': 'hen', 'hog': 'fox', 'fox': 'jay', 'jay': 'doe', 'rat': 'ram', 'ram': 'rat'}
def rabbit_hole(dictionry,key,MEMORY={}):
    if key in MEMORY:
        MEMORY[key] += 1
    else:
        MEMORY[key] = 1
    for val in MEMORY.values():
        if val == 2:
            return False
    for k,v in dictionry.items():
        if k == key:
            rabbit_hole(dictionry,v,MEMORY)
    return list(MEMORY)[-1]

问题分析 #

1. 可变默认参数的副作用：MEMORY={}作为函数默认参数，Python会在函数定义时仅初始化一次，多次调用函数会共享同一个字典实例，导致之前调用的残留数据干扰后续执行。
2. 递归返回值未传递：递归调用rabbit_hole(dictionry,v,MEMORY)时，没有接收并处理返回结果，即使递归分支已经返回False，上层函数仍会继续执行并返回MEMORY的最后一个key。
3. 重复key判断逻辑冗余：遍历MEMORY.values()查找值为2的项，效率低下；且判断时机晚于key的添加，无法及时阻断循环。
4. 下一个key查找低效：通过遍历字典所有items匹配key，不如直接用字典的get方法快速获取对应value。

修正方案 #

针对上述问题，修改后的代码如下：

d = {'bat': 'pig', 'pig': 'cat', 'cat': 'dog', 'dog': 'ant', 'cow': 'bee', 'bee': 'elk', 'elk': 'fly', 'ewe': 'cod', 'cod': 'hen', 'hog': 'fox', 'fox': 'jay', 'jay': 'doe', 'rat': 'ram', 'ram': 'rat'}
def rabbit_hole(dictionry, key, MEMORY=None):
    # 初始化MEMORY，避免可变默认参数的共享问题
    if MEMORY is None:
        MEMORY = set()  # 用集合存储已访问key，比字典更高效
    # 检查当前key是否已访问过，是则返回False
    if key in MEMORY:
        return False
    MEMORY.add(key)
    # 获取下一个key
    next_key = dictionry.get(key)
    if not next_key:
        # 无下一个key，返回当前key
        return key
    # 递归调用并传递返回值
    result = rabbit_hole(dictionry, next_key, MEMORY)
    return result

修改说明 #

• 替换可变默认参数：将MEMORY默认值设为None，在函数内部初始化空集合，确保每次调用都有独立的访问记录容器。
• 用集合优化访问记录：集合的成员查询效率比字典更高，只需记录已访问的key即可，无需统计次数。
• 及时阻断循环：先检查当前key是否在已访问集合中，是则直接返回False，避免无效递归。
• 传递递归返回值：接收递归调用的结果并直接返回，确保False能正确向上传递到顶层调用。
• 高效获取下一个key：使用dict.get()方法直接获取对应value，无需遍历所有键值对。

测试验证 #

执行测试代码：

print(rabbit_hole(d, "bat"))  # 输出: ant
print(rabbit_hole(d, "cod"))  # 输出: hen
print(rabbit_hole(d, "jay"))  # 输出: doe
print(rabbit_hole(d, "yak"))  # 输出: yak（字典中无yak的键，直接返回）
print(rabbit_hole(d, "rat"))  # 输出: False

输出结果与预期完全一致。

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