Subscribe to our RSS
C++ Recursion – Power
Creating a power function using Recursion
Below is an example of how to calculate the x to the power of n. This tutorial expects you to understand the following:
Example:
pow(2,3); pow(5,4);
Result:
8 125
Iterative version of a function that calculates the power function
To understand how to calculate the power function using recursion, let’s write a simple algorithm that will do it for us using iteration.
if ( exp == 0 ) {
return 1;
}
//Initial value for the result is the base
int result = base;
//Multiplies the base by itself exp number of times
for ( int i = 1; i < exp; i++ ) {
result = result * base;
}
return result;
}
Calculating the power function using recursion
So how would we go by solving this using recursion? First of all we need a function header.
Next, what would be our base case? When we are trying to calculate n to the power of 0, the result should be 1. Also, when we try calculating n to the power of 1, the result should be n.
//Return 1 when n is 0
if ( n == 0 ) return 1;
else if ( n == 1 ) return base;
}
Now, how would we go on by computing the power function using recursion? Let’s come up with a formula by calculating the following.
power(2,1) = 2;
power(2,2) = 2 * power(2,1) = 2 * 2 = 4;
power(2,3) = 2 * power(2,2) = 2 * 4 = 8;
power(2,4) = 2 * power(2,3) 2 * 8 = 16;
…
power(base, exp) = base * power(base, exp-1);
Translating the above formula to code, is then fairly trivial. This would allow us to apply our power function to any two positive integers.
//Return 1 when n is 0
if ( n == 0 )
return 1;
else if ( n == 1 )
return base;
else
return base * power(base, exp-1);
int result = base;
}
Have any questions? Feel free to ask below or request any other examples.
Going further
- 1. How would you make this function take care of negative exponents?
(2 votes, average: 5.00 out of 5)
February 8th, 2010 at 5:42 pm
Thanks. These problems have helped me out understand recursion a lot more. =)