Python program stops working if array of size greater than 1995 is passed to Array a

Question

I am trying to set an array of integer whose size is 10000.

However, Code works great if the length of the array a is less than 1995. If I changed it to 2000 or more program stops working.

I want this code to work if I set array a of size 10000. Here is the Python code:

    import random
    random.seed()

    a = [random.randint(-1000, 1000) for i in range(10000)]
    DP = [[] for i in a]
    seq = []
    def solveDP(i):
        global DP
        if i >= len(a):
            return []
        if len(DP[i]) > 0:
            return DP[i]
        arr1 = [a[i]] + solveDP(i + 2)
        arr2 = solveDP(i + 1)
        if sum(arr1) > sum(arr2):
            DP[i] = arr1[:]    # Copy arr1 into DP[i]
        else:
            DP[i] = arr2[:]    # Copy arr2 into DP[i]
        return DP[i]

    print(solveDP(0))

what exactly do you mean by stops working, does it throw an error? or do you no longer get the output that you desire? — Imtinan Azhar, May 07 '19 at 06:34

Bogdan Doicin · Accepted Answer · 2019-05-07T06:49:45.140

The problem is not with the array length is with the recursive call of solveDP. I played around with your code and, at about 5980, I get the following error message:

Traceback (most recent call last): File "C:\Users\alexz\OneDrive\Programe\Python\PythonApplication1\PythonApplication1\PythonApplication1.py", line 13, in solveDP arr1 = [a[i]] + solveDP(i + 2) File "C:\Users\alexz\OneDrive\Programe\Python\PythonApplication1\PythonApplication1\PythonApplication1.py", line 13, in solveDP arr1 = [a[i]] + solveDP(i + 2) File "C:\Users\alexz\OneDrive\Programe\Python\PythonApplication1\PythonApplication1\PythonApplication1.py", line 13, in solveDP arr1 = [a[i]] + solveDP(i + 2) [Previous line repeated 995 more times] File "C:\Users\alexz\OneDrive\Programe\Python\PythonApplication1\PythonApplication1\PythonApplication1.py", line 7, in solveDP def solveDP(i): File "e:\microsoft visual studio 2019\community\common7\ide\extensions\microsoft\python\core\Packages\ptvsd_vendored\pydevd_pydevd_bundle\pydevd_trace_dispatch_regular.py", line 343, in call is_stepping = pydev_step_cmd != -1 RecursionError: maximum recursion depth exceeded in comparison

The bold line made me search for a bit and I found this source. According to the answer,

It is a guard against a stack overflow, yes.

It looks to me that you call a function recursively so many times, that you filled the machine's stack.

Haven't tried it myself but this looks right. Python unfortunately doesn't support tail call optimisation so you'll have to find another implementation. — CoffeeTableEspresso, May 07 '19 at 06:52
Thanks for replying. It will be very helpful if you provide me one sample code related to my code. — Sakshi, May 07 '19 at 07:08
If all you want is to generate an array of 10000 random elements, I think recursion is an overkill — Bogdan Doicin, May 07 '19 at 07:12

Python program stops working if array of size greater than 1995 is passed to Array a

1 Answers1