Python如何统计递归函数迭代次数？附数独递归求解代码示例

问题根因 #

当前写法中counter是函数内部的局部变量，每次递归调用solver()时都会重新初始化为0，且不同递归栈的局部变量互不共享，自然无法累计总迭代次数。

方案1：外层封装+nonlocal声明（推荐，无全局污染） #

把递归逻辑封装在外层函数内，计数器定义在外层作用域，内层递归函数用nonlocal关键字声明即可共享计数变量，最后可以同时返回求解结果和总次数。

def solve_sudoku():
    counter = 0
    def solver():
        nonlocal counter
        empty_cell = empty_square()
        if not empty_cell:
            return True
        i,j = empty_cell[0],empty_cell[1]
        for num in range(1,10):
            counter += 1
            if constraint_check(num,i,j):
                sudoku[i][j] = num
                if solver():
                    return True
                else:
                    sudoku[i][j] = 0
        return False
    solve_result = solver()
    return solve_result, counter

# 调用示例
result, total_count = solve_sudoku()
print(f"求解结果：{result}，总迭代次数：{total_count}")

方案2：修改返回值传递计数（纯函数无共享变量） #

每次递归调用都返回「求解状态 + 当前层累计的迭代次数」，不需要额外的共享变量，副作用最低。

def solver():
    empty_cell = empty_square()
    counter = 0
    if not empty_cell:
        return True, counter
    i,j = empty_cell[0],empty_cell[1]
    for num in range(1,10):
        counter += 1
        if constraint_check(num,i,j):
            sudoku[i][j] = num
            sub_result, sub_counter = solver()
            counter += sub_counter
            if sub_result:
                return True, counter
            else:
                sudoku[i][j] = 0
    return False, counter

# 调用示例
result, total_count = solver()
print(f"求解结果：{result}，总迭代次数：{total_count}")

方案3：用可变对象作为计数器（写法简单） #

利用列表、字典这类可变对象的引用传递特性，不需要修改函数结构即可实现计数，也可以用全局变量，但全局变量容易和其他逻辑冲突，不推荐使用。

# 定义单元素列表作为计数器，利用可变对象引用传递的特性
counter = [0]
def solver():
    empty_cell = empty_square()
    if not empty_cell:
        return True
    i,j = empty_cell[0],empty_cell[1]
    for num in range(1,10):
        counter[0] += 1
        if constraint_check(num,i,j):
            sudoku[i][j] = num
            if solver():
                return True
            else:
                sudoku[i][j] = 0
    return False

# 调用示例
result = solver()
print(f"求解结果：{result}，总迭代次数：{counter[0]}")

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