Java Language Computing the sum of integers from 1 to N


Example

The following method computes the sum of integers from 0 to N using recursion.

public int sum(final int n) {
    if (n > 0) {
        return n + sum(n - 1);
    } else {
        return n;
    }
}

This method is O(N) and can be reduced to a simple loop using tail-call optimization. In fact there is a closed form expression that computes the sum in O(1) operations.