使用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来记忆化一个函数时，我会得到三倍的递归层数？

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