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

Answer 2

There is a decorator for caching the function values so you can use your function with no modification:

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)

from python 3.9 onwards:

from functools import cache
@cache

Then you can run:

T(1000)

And will finish the execution extremely fast without any modification.

Answer 3

It would be better to use dynamic programming.

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]