Big Oh Runtime of a Recursive Sum

Question

If I use a for loop to find the sum of n numbers between 0 and n my runtime is O(n). But if I create a recursive function such as:

int sum(int n) {
    if(n == 0)
        return 0;
    return n + sum((n - 1));
}

Would my runtime still be O(n)?

Answer 1

Yes, your runtime will still be O(N). Your recursive function will "loop" N times until it hits the base case.

However keep in mind that your space complexity is also O(N). Your language has to save n + ... before evaluating sum((n - 1)), creating a stack of recursive calls that is N long.

Answer 2

@Primusa's answer addresses your recursive runtime question. While my answer wont address your runtime question, it should be noted that you dont need an algorithm for this. The closed formula for the sum is (n+1)*(n) / 2.

thanks Carl Gauss!