为何三段逻辑一致的Python递归代码Runtime差异巨大？

我在解决LeetCode的「可见K根木棍的排列方式」问题时，写出了三段逻辑完全一致但代码结构不同的递归实现（均使用@cache装饰器），但它们的运行时间差异极大：分别为3700ms、1700ms、200ms。以下是三段代码及性能差异的原因分析。

三段代码对比 #

Runtime: 3700ms #

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        self.m = 10**9 + 7
        out = self.rs(n, k)
        return out
    @cache
    def rs(self,n, k):
        if k <= 0 :
            return 0
        if n < k:
            return 0
        if n == k:
            return 1
        out1 = self.rs(n-1, k-1)
        out2 = self.rs(n-1, k)

        out = (out1+out2*(n-1))%(self.m)
        return out

Runtime: 1700ms #

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        m = 10**9 + 7
        @cache
        def rs(n, k):
            if k <= 0 :
                return 0
            if n < k:
                return 0
            if n == k:
                return 1
            out1 = rs(n-1, k-1)
            out2 = rs(n-1, k)

            out = (out1+out2*(n-1))%(m)
            return out
        out = rs(n, k)
        return out

Runtime: 200ms #

class Solution:
    def rearrangeSticks(self, n: int, k: int) -> int:
        out = rs(n, k)
        return out
m = 10**9 + 7
@cache
def rs(n, k):
    if k <= 0 :
        return 0
    if n < k:
        return 0
    if n == k:
        return 1
    out1 = rs(n-1, k-1)
    out2 = rs(n-1, k)
    out = (out1+out2*(n-1))%(m)
    return out

性能差异核心原因 #

三段代码逻辑完全一致，性能差距全来自函数调用开销、缓存效率以及变量访问速度的差异：

1. 第一段：实例方法的额外开销
   rs是类的实例方法，每次调用都要传递self参数，@cache会把self也纳入缓存键的计算——这不仅增大了缓存键的体积，还增加了哈希计算的开销。另外，访问self.m属于属性查找，比直接访问变量慢；而且实例方法的调用本身就比普通函数多了一层实例绑定的逻辑，这些额外操作累积起来，直接拖慢了整体运行速度。

2. 第二段：嵌套函数的局部优化
   把rs改成rearrangeSticks内部的嵌套函数后，不再需要传递self，缓存键仅包含n和k，哈希计算和缓存查找的效率都有所提升。同时，直接访问外部作用域的m变量，避免了属性查找的开销。不过嵌套函数每次进入外部函数时都会重新创建（LeetCode单测场景下只会创建一次），而且作用域查找的速度还是不如全局变量，所以运行速度比第一段快，但仍不如第三段。

3. 第三段：全局函数的最优表现
   rs作为全局函数，调用开销是三者中最小的——既不需要处理实例绑定逻辑，也不需要嵌套函数的作用域链查找。m是全局变量，访问速度最快；而且@cache的缓存是全局共享的，如果有多个测试用例，还能复用之前的计算结果。哪怕是单个测试用例，全局函数的调用效率和缓存命中率都是最高的，因此运行时间大幅缩短。

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