pythonrecursionruntime-error

Runtime Error Hangup(SIGHUP) for recursion solution to sum of series problem


Problem:

Given an int N, calculate the sum of series 13+23+33+43...... till the nth term using recursion (Link to problem)

Implemented Solution in Python:

#User function Template for python3

class Solution:
    def sumOfSeries(self,n):
        #code here
        if n>0:
            return (n*n*n) + self.sumOfSeries(n-1)
        else:
            return 0
            
#{ 
 # Driver Code Starts
#Initial Template for Python 3

if __name__=='__main__':
    t=int(input())
    for _ in range(t):
        N=int(input())
        ob=Solution()
        print(ob.sumOfSeries(N)) 
# } Driver Code Ends

The solution works for small inputs but is giving the above error of large values like 18468

I am unable understand the meaning of the error and what is causing it

I attempted to solve the same problem using recursion in C++ and it is not presenting any error

C++ Solution:

//{ Driver Code Starts
// Initial template for C++
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
// User function template for C++

class Solution {
  public:
    long long sumOfSeries(long long n) {
        // code here
        if (n==1) 
            return 1;
        else
            return (n*n*n)+sumOfSeries(n-1);
    }
};

//{ Driver Code Starts.
int main() {
    int t;
    cin >> t;
    while (t--) {
        long long N;
        cin >> N;
        Solution ob;
        cout << ob.sumOfSeries(N) << "\n";
    }
}
// } Driver Code Ends

Solution

  • The online judge host closes the terminal as the Python code takes too much time to complete.

    This is not unexpected. Python code generally runs slower than C++, which explains why it could happen to the Python code and not to the similar C++ code.

    Note how the challenge has not suggested that you should solve this with recursion. As n is given to be in the range up to 50000, you should reject the idea to apply recursion here. Moreover, the challenge asks to implement a solution with O(1) time complexity.

    Here is a hint on how to do that:

    n-th triangular number squared.

    If this is not enough to write a O(1) solution, here is a spoiler:

    return (n*(n+1)//2)**2