6

我一直在玩 python 3.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)或以上将抛出异常。

但是，如果我尝试用 装饰此函数，则在运行时会提前 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_cache为什么我在使用记忆函数时得到三倍的递归级别？

4

1 回答 1

5

因为装饰器是一个额外的功能，所以它“使用”了堆栈中的一层。例子：

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

此外，如果装饰器使用参数 packing/unpacking，则使用额外的级别（尽管我对 Python 运行时的了解不足，无法解释为什么会发生这种情况）。

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

最大限度。超出递归深度：

  • 未装饰：1000
  • 无包装：500
  • 带包装：334
于 2013-03-06T04:45:55.613 回答