Subscribe to our RSS
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.
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.
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.
//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.
//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.
(1 votes, average: 5.00 out of 5)
February 22nd, 2010 at 1:15 pm
frist thanks at all
i need progran working like this
vc++program that calculates the addition of even input numbers and
exits when zero entered
February 22nd, 2010 at 1:54 pm
@ramram You might want to check out the following:
http://talkbinary.com/programming/c/advanced-control-flow-while-loop/