Python中如何在DFS递归函数内部统计执行次数（无需全局变量）

嘿，这两个递归统计的问题我很熟悉，尤其是把全局变量整合到函数内部的需求，刚好可以用几种优雅的方式解决，我一步步给你讲～

你之前用全局变量ind的方式虽然能实现，但容易引发副作用（比如多次调用会累加计数），而且不够封装。下面是几种把计数器整合到函数内部的方案：

1. 闭包（嵌套函数）—— 最推荐的方式 #

把计数器放在外层函数里，内层递归函数通过闭包访问它，完全不需要全局变量，封装性拉满。

针对你的BST DFS场景，代码示例如下：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 构建包含[1,2,...,15]的二叉搜索树（这里是完全二叉树结构）
def build_bst():
    nodes = [TreeNode(i) for i in range(1, 16)]
    for i in range(7):
        nodes[i].left = nodes[2*i+1]
        nodes[i].right = nodes[2*i+2]
    return nodes[0]  # 根节点为8

def count_dfs_executions(root):
    count = [0]  # 用列表是因为它是可变对象，闭包内能直接修改元素值
    
    def dfs(node):
        count[0] += 1  # 每次进入DFS函数就计数+1（包括空节点的调用）
        if not node:
            return
        dfs(node.left)
        dfs(node.right)
    
    dfs(root)
    return count[0]

# 测试
root = build_bst()
print(count_dfs_executions(root))  # 输出31，和你说的一致

解释：外层函数初始化计数器，内层dfs函数每次被调用（不管节点是否为空）都会让计数器加1，最后返回统计结果。用列表而不是普通整数，是因为整数是不可变对象，闭包内无法直接修改外层的整数变量，而列表是可变的，修改元素没有问题。

2. 可变默认参数—— 简洁但需注意副作用 #

这种方式更简单，直接把计数器作为函数的默认参数（必须用可变对象，比如列表）：

def dfs(node, count=[0]):
    count[0] += 1
    if not node:
        return
    dfs(node.left)
    dfs(node.right)
    return count[0]

# 测试
root = build_bst()
print(dfs(root))  # 第一次调用输出31

# 注意：如果要多次调用，必须手动重置计数器，因为默认参数只在函数定义时初始化一次
dfs(None, count=[0])  # 重置计数

这种方式的缺点是如果多次调用不重置计数器，会导致结果累加，所以适合单次调用场景，或者每次调用前手动重置。

3. 类封装—— 适合复杂场景扩展 #

如果你的递归逻辑比较复杂，或者需要扩展其他功能，用类封装计数器是个不错的选择：

class DFSCounter:
    def __init__(self):
        self.count = 0
    
    def dfs(self, node):
        self.count += 1
        if not node:
            return
        self.dfs(node.left)
        self.dfs(node.right)

# 使用
counter = DFSCounter()
root = build_bst()
counter.dfs(root)
print(counter.count)  # 输出31

类的方式把计数器作为实例属性，每次创建新实例就会自动重置计数，不会有多次调用的副作用，而且扩展性强，后续可以轻松添加其他统计功能。

你提到的包含1-15的二叉搜索树，DFS执行次数为31次是完全正确的：15个非空节点各被调用1次，加上16个空指针（比如叶子节点的左右子树）的调用，15+16=31次，上面的代码刚好统计了所有函数调用次数，所以输出符合预期。

相比全局变量，上面的几种方法都实现了计数器的内部化，避免了全局变量的副作用。其中**闭包（嵌套函数）**是最简洁且安全的方式，推荐优先使用；如果需要更复杂的逻辑，类封装会更合适。

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