Python用递归实现N层嵌套for循环统计合法走法总数 无库依赖

实现思路 #

直接用递归模拟嵌套循环即可，递归的每一层对应一层for循环，严格按照要求的push、递归进入下一层、undo的顺序执行即可。

实现代码 #

# 假设all_legal_moves、push、undo为你环境中已实现的可用函数
def calculate_number(N):
    count = 0
    
    def recurse(level):
        nonlocal count
        # 到达最内层循环，直接累加计数
        if level == N:
            for _ in all_legal_moves():
                count += 1
            return
        # 非最内层循环，按规则执行push、递归下一层、undo
        for move in all_legal_moves():
            push(move)
            recurse(level + 1)
            undo()
    
    recurse(1)
    return count

代码说明 #

• 递归函数recurse的入参level代表当前处理的是第几层循环
• 当level等于输入的嵌套深度N时，触发最内层逻辑：遍历所有合法走法，计数直接+1，不需要执行push和undo
• 非最内层的逻辑完全和示例中的手动嵌套循环一致：每选中一个合法走法先执行push，再进入下一层递归，等下一层所有循环执行完毕后再执行undo回退操作
• 不需要导入任何第三方库，直接调用即可，比如对应N=5的场景，直接调用calculate_number(5)就能得到和示例代码完全一致的结果。

如果你的Python版本不支持nonlocal关键字，可以把计数改成可变对象实现，兼容版本如下：

def calculate_number(N):
    count = [0]
    
    def recurse(level):
        if level == N:
            for _ in all_legal_moves():
                count[0] += 1
            return
        for move in all_legal_moves():
            push(move)
            recurse(level + 1)
            undo()
    
    recurse(1)
    return count[0]

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