I have this recursive function:

def My_recu_fun(i):
    if i < 4:
        return i 1
    return 55692*My_recu_fun(i-4) - 9549*My_recu_fun(i-3)   301*My_recu_fun(i-2)   21*My_recu_fun(i-1)

If I call it like:

My_recu_fun(int(2e5))

I get this error:

RecursionError: maximum recursion depth exceeded in comparison

Now I hope to solve this by using NumPy. But I don't understand how can I do it.

CodePudding user response：

The problem is that the function will get executed an exponentially number of times, in terms of the initial argument i. There is an immense number of times that the function needs to recalculate a result it already had calculated earlier in the process.

Using NumPy can be a good idea when you need to do intensive array/matrix operations, but in itself it will not solve this particular recursion problem.

You could use memoization to avoid such recalculations. But it is even better to take a bottom up, iterative approach, only keeping track of the last 4 results:

def My_fun(i):
    if i < 4: 
        return i 1
    a, b, c, d = 1, 2, 3, 4
    for j in range(3, i):
        a, b, c, d = b, c, d, 55692*a - 9549*b   301*c   21*d
    return d

Be aware the the numbers that are generated by this function quickly grow very large.

Here are some statistics:

Calculating with such large integers, takes lots of memory and time. You cannot use NumPy even with the iterative algorithm, because its native ctypes cannot save numbers that large.

CodePudding user response：

My_recu_fun(int(2e5)) runs the My_recu_fun more than 2*10^5 (so 200.000) times. Python assumes it is a bug (because it's more than 10^4 times) and wants to prevent it. You can turn that behaviour off using:

import sys
sys.setrecursionlimit(n)

Where n is the required amount of recursion. I cannot estimate how many times My_recu_fun does recursion, so you will have to estimate that.

In addition to that, I recommend using functool's cache decorator to speed things up:

import sys
from functools import cache

n = 500000
sys.setrecursionlimit(n)

@cache
def My_recu_fun(i):
    if i < 4: return i 1

    return 55692*My_recu_fun(i-4) - 9549*My_recu_fun(i-3)   301*My_recu_fun(i-2)   21*My_recu_fun(i-1)