在超过最大递归深度的情况下编写非递归函数

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(的值，我不知道是否有一种简单的方法来重写代码，或者这只是计算值的一种情况？任何帮助都将不胜感激，我目前收到错误"超过最大递归深度">

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]