我最近在尝试使用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将函数进行记忆化时会出现三倍递归级别的情况?