使用functools.lru_cache时,最大递归深度达到更快

Question

我一直在使用python 3.3中的memoization和recursion

忽略python是这样做的错误语言的事实,我发现在使用 functools.lru_cache memoize和不使用之间我得到了不一致的结果 functools.lru_cache

我没有改变递归限制 - 它保持默认值,对我来说是1000.

为了测试这个问题,我写了一个简单的递归函数来对从1到i的数字求和

#!/usr/bin/python

def sumtil(i):
"""Recursive function to sum all numbers from 1 through i"""

    # Base case, the sum of all numbers from 1 through 1 is 1... 
    if i == 1:
        return 1
    else:
        return i+sumtil(i-1)

# This will not throw an exception
sumtil(998)

# This will throw an exception
sumtil(999)

正常运行此功能,我可以sumtil(998)舒适地运行而不会达到递归限制.sumtil(999)或以上将抛出异常.

但是,如果我尝试使用此函数进行装饰,则在运行时会提前3次@functools.lru_cache()抛出递归限制异常sumtil(333)

#!/usr/bin/python

import functools 

@functools.lru_cache(maxsize=128)
def sumtil(i):
    """Recursive function to sum all numbers from 1 through i"""

    # Base case, the sum of all numbers from 1 through 1 is 1... 
    if i == 1:
        return 1
    else:
        return i+sumtil(i-1)

# This will not throw an exception
sumtil(332)

# This will throw an exception
sumtil(333)

由于332*3 = 996,但333*3 = 999,在我看来lru_cache装饰器导致我的函数中的每个级别的递归变为三级递归.

为什么在使用functools.lru_cachememoize函数时,我得到的递归级别是三倍？

Answer 1

因为装饰器是一个额外的功能,所以它"使用"堆栈中的一个级别.例:

>>> def foo(f):
...   def bar(i):
...     if i == 1:
...       raise Exception()
...     return f(i)
...   return bar
...
>>> @foo
... def sumtil(i):
...     if i == 1:
...         return 1
...     else:
...         return i+sumtil(i-1)
...
>>> sumtil(3)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 5, in bar
  File "<stdin>", line 6, in sumtil
  File "<stdin>", line 5, in bar
  File "<stdin>", line 6, in sumtil
  File "<stdin>", line 4, in bar
Exception
>>>

此外,如果装饰器使用参数打包/解包,那么使用额外的级别(尽管我对Python运行时的知识不足以解释为什么会发生这种情况).

def foo(f):
  def bar(*args,**kwargs):
    return f(*args,**kwargs)
  return bar

最大.超出递归深度:

• 未装饰: 1000
• 没有包装: 500
• 包装: 334