python - 装饰器可以装饰递归函数吗？

Question

我想看看两种计算斐波那契数列的方法之间的时间成本差异: 首先，我创建了一个装饰器，将“输出时间成本”函数添加到函数中:

def time_cost(func):
    def wed(n):
        start = time.time()
        func(n)
        stop = time.time()
        print(stop-start)
    return wed

然后我写了第一个函数:

@time_cost
def DP_F(n):
    f = [1,1]
    while len(f)<n:
    f.append(f[len(f)-1]+f[len(f)-2])
    return f

效果很好

>>> DP_F(10)
0.0
>>> DP_F(100)
0.0
>>> DP_F(10000)
0.007944107055664062

但是当我用装饰器创建第二个函数时发生了一些错误:

@time_cost
def R_F(n):
    if n<=2:
        return 1
    else:
        return R_F(n-1)+R_F(n-2)

引发错误，表示某些输出可能会丢失

>>> R_F(10)
0.0
0.0
Traceback (most recent call last):
  File "<pyshell#44>", line 1, in <module>
    R_F(10)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
  File "<pyshell#28>", line 4, in wed
    func(n)
  File "<pyshell#43>", line 8, in R_F
    return R_F(n-1)+R_F(n-2)
TypeError: unsupported operand type(s) for +: 'NoneType' and 'NoneType'

所以Python装饰器不能装饰递归函数？

Answer 1

眼前的问题是 wed 不返回 func 的返回值。这很容易修复。

def time_cost(func):
    def wed(n):
        start = time.time()
        n = func(n)
        stop = time.time()
        print(stop-start)
        return n
    return wed

However, now look what happens when you call R_F(3).

>>> R_F(3)
9.5367431640625e-07
1.1920928955078125e-06
0.0001671314239501953
2

您会得到3次:每次递归调用一次。这是因为原始函数调用 R_F 绑定(bind)的任何内容，现在是函数 wed，而不是实际的 Fibonacci 函数。

使用上下文管理器可以更好地处理类似的事情。

from contextlib import contextmanager

@contextmanager
def time_cost():
    start = time.time()
    yield
    stop = time.time()
    print(stop - start)

with time_cost():
    R_F(3)

<小时/>

题外话

从某种意义上说，Python 没有递归函数。函数不能调用自身，而只有绑定(bind)到您期望的名称的某个函数才会引用您的函数。称之为“合作递归”。

例如，考虑递归函数的标准示例:阶乘。

def fact(x):
     return 1 if x == 0 else x * fact(x-1)

我们可以通过重新绑定(bind)名称fact来轻松打破这个问题。

g = fact  # save a reference to the original function
def fact(x):
   print("Broken")
   return 0

Now g(3) 打印 Broken 并返回 0，因为它将尝试调用绑定(bind)到 now 的任何 fact ，而不是重新定义之前所绑定(bind)的fact。

如果您想要一个“安全”的递归函数，则必须根据私有(private)递归助手来定义它。

def fact(x):
    def helper(x):
        return 1 if x == 0 else x * helper(x - 1)
    return helper(x)

现在您可以安全地装饰 fact，因为无论 fact 绑定(bind)到什么(无论是原始函数还是装饰后的函数)，helper永不反弹。