使用递归进行后缀求和：Python 中超出内存限制错误

Question

我在练习递归求和时在 CodeForces 上发现了这个和。

Problem:

Given two numbers N and M, and an array A of N numbers. Calculate the sum of the last M numbers.

Note: solve this problem using recursion.

Input
First line contains two numbers N
and M
 (1≤M≤N≤10^5)
 .

Second line contains N numbers (−10^9≤Ai≤10^9)
 .

Output
Print the sum of the last M numbers of the given array.

我尝试用Python解决这个问题，这是我的代码：

def suffix_sum(arr,m):
    if m<=0:
        return 0
    else:
        return arr[-1]+suffix_sum(arr[:-1],m-1)
n,m = map(int,input().split())
arr = list(map(int,input().split()))
print(suffix_sum(arr,m))

虽然我在编译器中获得了示例输入的预期输出，但当我提交代码时，我总是会得到“测试 2 超出内存限制”。测试用例 2 是隐藏的，所以我不确定测试用例是什么，但我的猜测是它是一个非常大的数组，数量级为 10^4 或 10^5。当我检查其他提交时，它们都是用 C++ 编写的。 那么，超出内存限制是否与我使用Python和PyPy有关，或者是我的代码有问题？ 当我使用 for 循环时，结果被接受，但由于问题是练习递归，所以我不确定哪里出错了。如果你能帮助我进步，那就太好了！

谢谢你，美好的一天！

Answer 1

理解问题

最大的问题是

arr

可能被复制 100,000 次，并且其大小可能为 100,000 (O(n^2))。当您进行切片并传递切片时，Python 将创建旧切片的副本并将其发送到新函数调用。我在具有 64 GB 内存的计算机上运行此程序，但内存不足。

解决方案

这个问题需要递归似乎很奇怪，因为

sum(arr[-m:])

是如此简单，但可以使其递归并通过避免通过不切片来复制数组来节省内存。

def suffix_sum(arr,m):
    if m<=0:
        return 0
    else:
        return arr[len(arr) - m] + suffix_sum(arr, m - 1)

尽管它重复了很多次，但速度仍然相当快。

注意：我必须使用 Python 3.11 来运行它，因为 3.10 和 3.9 在没有段错误的情况下无法重复那么多。