在超过最大递归深度时编写非递归函数

Question

我想知道是否有人可以帮助我将这段代码重写为非递归的，以便它可以计算更大的数字，我当前的代码如下所示：

def T(n):
    if n < 3:
        return n
    return T(n - 1) + 2 * T(n - 2) - T(n - 3)

该函数是为算术目的而设计的，其中 T(0) = 0、T(1) = 1、T(2) = 2、T(3) = 4、T(5) = 7 等...

例如，我希望能够计算高达 T(1000) 的值，我不知道是否有一种简单的方法来重写代码，或者是否只是计算值的情况？任何帮助将不胜感激，我目前收到错误 'maximum recursion depth exceeded'

Answer 1

使用“滚动”方法跟踪最后三个结果，并在添加新结果时同时踢掉最旧的结果：

def T(n):
    if n < 3:
        return n
    a, b, c = 0, 1, 2
    for i in range(2, n):
        a, b, c = b, c, c + 2*b - a
    return c

Answer 2

有一个用于缓存函数值的装饰器，因此您无需修改即可使用您的函数：

from functools import lru_cache
@lru_cache(maxsize=None)
def T(n):
    if n < 3:
        return n
    return T(n - 1) + 2 * T(n - 2) - T(n - 3)

从 python 3.9 开始：

from functools import cache
@cache

那么你可以运行:

T(1000)

并且会非常快速地完成执行无需任何修改。

Answer 3

最好用动态规划

def t(n):
    if n <3:
        return n
    temp = [0] * (n +1)
    temp[1], temp [2] = 1,2
    for i in range(3,n+1,1):
        temp[i] = temp[i - 1] + 2 * temp[i - 2] - temp[i - 3]
    return temp[n]

在超过最大递归深度时编写非递归函数

Writing a non-recursive function as maximum recursion depth has been exceeded

python

recursion

non-recursive