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

Question

I was wondering if someone could help me rewrite this code as non-recursive so it can compute higher numbers, my current code looks like this:

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

The function is designed for the purpose of arithmetic where T(0) = 0, T(1) = 1, T(2) = 2, T(3) = 4, T(5) = 7 etc...

I want to be able to compute values as high as T(1000) for example, I didn't know if there was a simplistic way to rewrite the code or if it would just be a case of computing the values? Any help would be appreciated, I'm currently getting the error 'maximum recursion depth exceeded'

Answer 1

Use a "rolling" method where you keep track of the last three results and as you add the new result, you also kick the oldest:

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