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

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'

CodePudding user response：

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

CodePudding user response：

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.

CodePudding user response：

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]