Creating a sum function

Example:

1

sum(10);

Result:

1

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

Iterative version of a function that calculates the summation

1
2
3
4
5
6
7
8
9
10

//Our initial total is zero
int total = 0;
 
//We want the sum from 1 + 2 + ... + 9 + 10
int n = 10;
 
//The following for loop will calculate the summation from 1 - n
for ( int i = 1; i <= n; i++ ) { 
     total = total + i;
}

Calculating the summation using recursion

1

int sum(int n)

Next, if you remember from the basics of recursion, our function needs a base case or terminating condition. What would it be in this case? When we are trying to sum the sequence consisting of only 0. We also don’t want to calculate the summation of negative numbers.

1
2
3
4
5

int sum(int n) { 
 
     //Return 0 when n is 0
     if ( n <= 0 ) return 0;
}

Now, how would we go on by computing summation using recursion? Let’s come up with a formula by calculating the summation of 1, 2, and 3.

1
2
3
4
5
6
7
8
9
10
11

summation(0) = 0;
 
summation(1) = 1 + summation(0) = 1 + 0 = 1;
 
summation(2) = 2 + summation(1) = 2 + 1 = 3;
 
summation(3) = 3 + summation(2) = 3 + 3 = 6; 
 
...
 
summation(n) = n * summation(n-1);

Translating the following formula into code, is then fairly trivial. This would allow us to apply our summation formula to any positive integer.

1
2
3
4
5
6
7
8

int sum(int n) { 
 
     //Return 0 when n is 0
     if ( n <= 0 ) return 0;
     else 
          return n + sum(n-1);
 
}

The previous recursive function will work as follows (in our case, sum(3)).

]

Have any questions? Feel free to ask below.