使用时达到最大递归深度更快functools.lru垌cach

Question

我一直在python3.3中使用记忆和递归

忽略了python是错误的语言这一事实，我发现在使用functools.lru_cache进行记忆和不使用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)或更高版本将引发异常。在

但是，如果我尝试用@functools.lru_cache()装饰这个函数，那么在运行sumtil(333)时，递归限制异常会在之前抛出3次

^{pr2}$

由于332*3=996，而333*3=999，在我看来，lru峎cache decorator使函数中的每一级递归都变成了三级递归。在

为什么在使用functools.lru_cache来记忆一个函数时，我得到的递归级别是原来的三倍？

Answer 1

因为decorator是一个额外的函数，所以它“使用”堆栈中的一个级别。示例：

>>> 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
>>>

此外，如果decorator使用argument packing/unpacking，那么将使用一个额外的级别（尽管我对Python运行时的了解还不够，无法解释为什么会发生这种情况）。在

^{pr2}$

超过最大递归深度：

• 未装饰：1000
• 无包装：500
• 有包装：334