Por que recebo uma exceção Stack Overflow com isto:
// Calling method:
OofNSq(50000);
// Method:
public static int OofNSq(int n)
{
if (n <= 0)
{
return 0;
}
return n + OofNSq(n - 1);
}
n = 30728 quando é lançado. Se eu alterar n para menos de 19.271, funcionará.
Um INT tem um tamanho de -2.147.483.648 a 2.147.483.647, então estou faltando alguma coisa.
Um resumo das informações dos comentários:
Uma exceção de estouro de pilha é resultado de exceder o espaço de pilha (que é relativamente pequeno).
É causado pelas chamadas recursivas no seu código. Cada chamada requer espaço na pilha.
Quando você começa com n==50000, quando chega a n==30728, você tem quase 20.000 chamadas recursivas aninhadas, todas ocupando espaço na pilha e você acabou.
O código em questão não possui complexidade de O(n^2).
A complexidade do tempo e do espaço não se soma . Eles são analisados separadamente.
No seu caso de cálculo da soma 1+...+n:
Complexidade de tempo : O(n) porque você tem O(n) estágios, cada um contendo adição e uma chamada de função ( O(1) para cada estágio).
Complexidade de espaço : também O(n) devido às chamadas recursivas que ocupam espaço na pilha conforme explicado acima.
Se você alterar seu algoritmo de recursivo para iterativo (usando um loop), a complexidade do espaço cairá para O(1) (o tempo ainda será O(n) ).
Isso também resolverá seu problema de exceção de estouro de pilha.