Computing the sum of integers from 1 to N
suggest changeThe 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.
Found a mistake? Have a question or improvement idea?
Let me know.
Table Of Contents