O(N²) Test Failing

Question

Why do i get a Stack Overflow exception with this:

// Calling method:
OofNSq(50000);

// Method:
public static int OofNSq(int n)
{
    if (n <= 0)
    {
        return 0;
    }

    return n + OofNSq(n - 1);
}

n = 30728 when it is thrown. If I change n to less than 19,271 then it works. 

An INT has a size of -2,147,483,648 to 2,147,483,647 so I'm missing something.

Answer 1

A summary of the information from the comments:

1. A stack-overflow exception is a result of exceeding stack space (which is relatively small).
   It is caused by the recursive calls in your code. Each call requires space on the stack.
   When you start with n==50000, then by the time you get to n==30728, you have alsmost 20000 nested recursive calls, all occupying space on the stack and you have ran out of it.

2. The code in question does not have complexity of O(n^2).
   Time and space complexity do not add up. They are analyzed separatly.
   In your case of calculating the sum 1+...+n:
   Time complexity: O(n) because you have O(n) stages, each containing addition and a function call (O(1) for each such stage).
   Space complexity: also O(n) due to the recursive calls occupying space on the stack as explained above.

3. If you change your algorithm from recursive to iterative (using a loop), the space complexity will drop to O(1) (time will still be O(n)).
   It will also solve your stack-overflow exception problem.