C++ Recursion – Summation

Creating a sum function

---

Below is an example of how to calculate the total of a sequence of numbers. In this case we will be calculating the sum of 10 + 9 + … + 2 + 1

Example:

sum(10);

Result:

55

Iterative version of a function that calculates the summation

---

To understand how to calculate the sum using recursion, let’s write a simple algorithm that will do it for us using iteration.

//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

---

So how would we go by solving this using recursion? First of all we need a function header.

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.

int sum(int n) { 

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

Now, how would go on by computing the sum using recursion? Let's start by drawing a diagram on how this could be done.

From the drawing above, we calculate the sum of 1 by adding 1 to the sum of 0, which is our terminating condition, which is 0.

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

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.

Related Posts

• C++ Recursion – Factorial (0)
• C++ Recursion – Palindrome (0)
• C++ Recursion – Reverse elements of a vector (0)
• C++ Recursion – Greatest Common Divisor (0)
• C++ Recursion – Fibonacci (0)