Python方法执行return后未退出，引发无限递归问题咨询

问题描述 #

你在实现shortest_path函数时遇到了一个棘手的问题：当函数触发第一个return path语句后，并没有按预期退出整个方法，反而跳转到倒数第二行再次调用自身，最终引发无限递归。按逻辑return后函数应该直接终止执行，你想弄清楚这背后的原因。

代码示例 #

import sys

# 假设以下辅助函数已实现
def load_data(directory):
    pass

def person_id_for_name(name):
    pass

def neighbors_for_person(person_id):
    pass

def main():
    if len(sys.argv) > 2:
        sys.exit("Usage: python degrees.py [directory]")
    directory = sys.argv[1] if len(sys.argv) == 2 else "small"
    print("Loading data...")
    load_data(directory)
    print("Data loaded.")
    source = person_id_for_name(input("Name: "))
    if source is None:
        sys.exit("Person not found.")
    target = person_id_for_name(input("Name: "))
    if target is None:
        sys.exit("Person not found.")
    path = shortest_path(source, source, target, set(), list())
    if path is None:
        print("Not connected.")
    else:
        degrees = len(path)
        print(f"{degrees} degrees of separation.")
        path = [(None, source)] + path
        print(path)

def shortest_path(original, source, target, visitedpeople=set(), path=list()):
    """
    Returns the shortest list of person_id that connect the source to the target.
    If no possible path, returns None.
    """
    if source == target:
        return []
    while source != target:
        destinations = neighbors_for_person(source)
        visitedpeople.add(source)
        neighbors = list()
        for x in range(len(destinations)):
            neighbors.append(destinations[x])
        if neighbors.__contains__(target):
            for neighbor in destinations:
                if neighbor == target:
                    path.append(neighbor)
                    return path
        else:
            if all(x in visitedpeople for x in neighbors):
                shortest_path(original, original, target, visitedpeople, path)
            else:
                for neighbor in destinations:
                    if neighbor not in visitedpeople:
                        path.append(neighbor)
                        visitedpeople.add(neighbor)
                        shortest_path(original, neighbor, target, visitedpeople, path)
    return []

问题根源分析 #

1. 递归调用未处理返回值，上层执行未终止 #

当你在代码中调用shortest_path(...)时，只是执行了递归，但没有处理递归的返回结果，也没有终止当前函数的执行流程。举个例子：

shortest_path(original, neighbor, target, visitedpeople, path)

这行代码执行完后，即使递归分支已经return path找到了目标路径，当前函数的代码还会继续往下走——比如回到for neighbor in destinations循环处理下一个邻居，或者回到外层的while循环再次执行循环体。这就导致即使递归找到了结果，上层函数仍会触发新的递归调用，最终引发无限递归。

2. 冗余的while循环加剧问题 #

你的函数已经用递归处理路径搜索，外层的while source != target循环完全是多余的。递归本身会逐层深入搜索，而这个while会让当前函数在递归返回后再次执行循环体，进一步加重了无限递归的情况。

3. 可变默认参数的潜在陷阱（虽当前调用未触发，但需注意） #

Python的默认参数是在函数定义时初始化的，而不是每次调用时。也就是说，如果调用shortest_path时不传visitedpeople和path，所有调用会共享同一个set()和list()实例。虽然你在main里手动传了新的集合和列表，暂时避开了这个问题，但后续如果有其他调用方式，很容易出现状态混乱的问题。

修复方案 #

针对这些问题，我们可以逐步调整代码：

方案1：正确处理递归返回值，及时终止上层执行 #

在递归调用后检查返回结果，如果找到路径就立刻返回，终止当前函数的执行：

result = shortest_path(original, neighbor, target, visitedpeople, path)
if result is not None:
    return result

方案2：移除冗余的while循环 #

递归已经能处理路径的逐层搜索，外层while循环完全没必要，直接删除即可。

方案3：避免可变默认参数陷阱 #

把默认参数设为None，在函数内部初始化新的集合和列表，确保每次调用都有独立的状态：

def shortest_path(original, source, target, visitedpeople=None, path=None):
    if visitedpeople is None:
        visitedpeople = set()
    if path is None:
        path = []
    # 后续逻辑不变

修复后的核心代码示例 #

def shortest_path(original, source, target, visitedpeople=None, path=None):
    """
    Returns the shortest list of person_id that connect the source to the target.
    If no possible path, returns None.
    """
    if visitedpeople is None:
        visitedpeople = set()
    if path is None:
        path = []
    
    if source == target:
        return []
    
    # 标记当前节点已访问
    if source in visitedpeople:
        return None
    visitedpeople.add(source)
    
    destinations = neighbors_for_person(source)
    
    # 目标在邻居中，直接返回路径
    if target in destinations:
        return path + [target]
    
    # 递归搜索每个邻居
    for neighbor in destinations:
        if neighbor not in visitedpeople:
            result = shortest_path(original, neighbor, target, visitedpeople, path + [neighbor])
            if result is not None:
                return result
    
    # 所有邻居搜索完毕未找到路径
    return None

调整后，一旦某个递归分支找到目标路径，就会逐层返回结果，终止上层函数的执行，不会再触发多余的调用，彻底解决无限递归的问题。

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