使用lru_cache时“超过最大递归深度”

Question

我想使用lru_cache计算递归函数。以下是它的简化版本：

from functools import lru_cache

@lru_cache(maxsize=None)
def f(n:int)->int:
    if (n==0): return 1
    return n+f(n-1)

### MAIN ###
print(f(1000))

当我运行f(100)时，它工作得很好，但是对于f(1000)，我得到：

RecursionError: maximum recursion depth exceeded in comparison

一种解决方案是自己计算f的值表。是否有不需要手动创建值表的解决方案？

Answer 1

请注意，您可以以-is方式使用您的函数，但是您需要确保每个新的调用在到达缓存值或递归基本情况之前不需要递归超过几百个级别；例如，

>>> f(400)
80201
>>> f(800)  # will stop recursing at 400
320401
>>> f(1000) # will stop recursing at 800
500501

通常，您可以编写一个包装器函数，反复尝试f(n)，捕获RecursionError，并放弃使用越来越小的n值来调用它。例如,

def superf(n, step=400):
    pending = []
    while True:
        pending.append(n)
        try:
            f(n)
            break
        except RecursionError:
            n = max(n - step, 0)
    while pending:
        x = f(pending.pop())
    return x

然后

>>> superf(100000)
5000050001