Python高阶函数中非局部变量引用的空间复杂度及底层机制咨询

变量定位规则 #

不管内部函数g递归1层还是100层（Python默认递归深度阈值约为1000，100层属于正常运行范围），g对lst的定位完全不受递归深度影响，不存在“每递归一层重新向外层查找一次变量”的逻辑。

Python在代码编译阶段就会完成作用域静态分析：识别到g内部引用了外层函数f作用域下的lst，会直接将lst标记为g的闭包变量，既不会把它当做g的局部变量，也不会当做全局变量处理。

注：你给出的示例代码没有设置递归终止条件，实际运行会触发递归深度超限错误，测试时可补充终止逻辑：

def f():
    lst = list(range(1, 101))
    depth = 0
    def g():
        nonlocal depth
        if depth >= 100:
            return
        depth += 1
        print(lst[0])  # 触发对非局部变量lst的引用
        g()
    g()
f()

底层实现机制（CPython） #

CPython通过cell对象实现闭包变量的跨作用域访问，核心逻辑如下：

• 编译阶段，但凡发现内部函数引用了外层函数的局部变量，就会为这些被引用的变量生成独立的cell存储单元，外层函数和内部函数会共享这组cell。
• 外层函数f运行时，创建的lst列表对象的内存指针，会被存入对应lst的cell中；而内部函数g被创建时，它的函数对象会自带一个指向这组cell的引用，直接和lst的存储位置绑定。
• 递归调用g时，每一层递归生成的栈帧只存储g自身的局部变量、返回地址、运行时状态，不会额外保存外层变量的引用。所有递归层级的g访问lst时，都是直接通过自身函数对象绑定的cell指针直接取值，不需要逐层向外遍历调用栈查找变量。

额外内存开销计算 #

这部分开销为固定常数级，和递归深度完全无关，具体构成如下：

• 固有开销（不属于闭包额外成本）：lst列表本身的内存、f栈帧中存储lst指针的空间，是f创建局部变量本来就要占用的资源——哪怕g完全不引用lst，这部分内存也会被占用，和闭包逻辑无关。
• 闭包带来的一次性额外开销：仅为被引用变量对应的cell对象，64位CPython环境下单个cell对象占约24字节（仅存储一个对象指针），加上g函数对象上存储cell引用的指针（8字节），总额外开销仅几十字节，在创建g函数对象时一次性分配，和后续g的调用次数、递归深度没有任何关系。
• 无递归叠加开销：递归100层的场景下，不会为每一层递归重复存储lst的指针，也不会复制lst列表的内容，所有递归层共用同一个cell、同一个lst引用，不会产生和递归深度正相关的增量内存开销。

简单说：这个场景下非局部变量引用带来的额外内存可以忽略不计，空间复杂度上这部分是常数级O(1)，不会随递归深度增长。

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