Sum of First 'n' Natural Numbers

Write a recursive function to do:

1 + 2 + 3 + 4 + 5 + 6 + 7
1 + 2 + 3 + 4 + ... + n

sum(n) = 1 + 2 + 3 + 4 + ... + (n - 1) + n

if n > 0 : sum(n) = sum(n - 1) + n
if n = 0 : sum(n) = 0

You can also simply use a formula: n(n + 1) / 2

Different ways to solve this problem:

Constant time O(1) operation:

int sum(int n) {
  return n * (n + 1) / 2;
}

Using for loop time O(n) and space O(n) operation:

int sum(int n) {
  int i, s = 0;
  for (i = 1; i <= n; i++) {
    s = s + i;
  }
  return s;
}

Using recursion time O(n) and space O(n) operation:

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

In our applications, we mostly use loops, but in mathematics we use recursions to solve problems.