如果将大小大于 1995 的数组传递给数组 a，Python 程序将停止工作

Question

我正在尝试设置一个大小为 10000 的整数数组。

但是，如果数组 a 的长度小于 1995，则代码可以正常工作。 如果我将其更改为 2000 或更多，程序将停止工作。

如果我设置大小为 10000 的数组 a，我希望这段代码能够工作。 这是Python代码:

    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))

Answer 1

问题不在于数组长度，而在于 solveDP 的递归调用。我试了一下你的代码，在大约 5980 时，我收到以下错误消息:

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

粗体线让我搜索了一下，发现 this source 。根据答案，

It is a guard against a stack overflow, yes.

在我看来，你递归地调用一个函数太多次，以至于填满了机器的堆栈。