Suffix sum using recursion: Memory limit exceeded error in Python

Question

I found this Suffix Sum challenge on CodeForces as I was practising recursion sums:

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

Second line contains N numbers (−10⁹ ≤ A_i ≤ 10⁹).

Output

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

I tried to solve the question in Python, and this is my code:

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

Though I get the expected output in my compiler for my sample input, I always end up getting 'Memory limit exceeded on test 2' when I submit my code. Test case 2 is hidden, so I am not sure what the test case is, but my guess is that it is a really large array in the order of 10⁴ or 10⁵. When I checked the other submissions, they were all in C++.

So, does the memory limit exceeding have something to do with me using Python and PyPy, or is something wrong with my code?

The result gets accepted when I use a for loop, but as the question is for practising recursion, I am not sure where I am going wrong. It would be of great help if you could help me improve!

Answer 1

Slicing costs memory: each slice is a new list. So you should avoid slicing and only use indexing to retrieve the values you need.

As m could be as large as 10⁵, you'll want to avoid a recursion depth of O(m). You can achieve that by partitioning the problem into halves, making two recursive calls, where to each you provide two indices defining the section of the list to sum up. This second index could also be a distance from the end of the input list, so it has a similar meaning as m and can get a default value of 1:

def suffix_sum(lst, m, last=1):
 if m == last:
 return lst[-m]
 mid = (m + last) // 2
 return suffix_sum(lst, m, mid + 1) + suffix_sum(lst, mid, last)

Now the recursion depth will be ⌈log₂m⌉, which for the worst case of m=10⁵ will be 17.

Note that the base case relies on the fact that m will be at least 1.

Answer 2

Understanding the Problem

The big problem is that arr is being copied potentially 100,000 and it may be of size 100,000 (O(n^2)). When you do slicing and pass the slice, Python will create a copy of the old one and send that to the new function call. I ran this on my computer with 64 GB of ram, and I ran out of memory.

The Solution

It seems weird for this problem to need to be recursive because sum(arr[-m:]) is so simple, but can make it recursive and save memory by avoiding copying the array by not slicing into it.

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

Even though it recurs many times, it's still decently fast.

Note: I had to run this with Python 3.11 because 3.10 and 3.9 can't recur that much without seg-faulting.

• Crystal Fire: Thank you very much! The time complexity, given the size the list, as you mentioned, is exactly the problem. I also tried submitting code without slicing, but the problem accepts solutions only in Python 3.8.10 or PyPy, other versions of Python are not available for submission. This problem is from a set of practice problems in recursion, that is why it needed to be recursive. I used sum(arr[-m:]) to get my submission accepted, so I could check if the hidden test cases will get unlocked. But the test cases remained hidden. Thank you very much, again! Good day to you!
• Crystal Fire: I tried submitting again, without slicing, but it displays Runtime error on Test case 2.