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

Question

我最近在尝试使用Python 3.3中的记忆化和递归。

忽略掉Python并不适合进行这样的操作的事实，我发现在使用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次抛出递归限制异常。

#!/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_cache将函数进行记忆化时会出现三倍递归级别的情况？

- Kiirani

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

- mgibsonbr