< Browse > Home / C++ / Blog article: C++ Recursion – Power

C++ Recursion – Power

February 7th, 2010 | 1 Comment | Posted in C++ by Diego

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:

  1. C++ Recursion
  2. C++ Recursion – Summation
  3. C++ Recursion – Factorial

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.

int power(int base, int exp) {

     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.


int power(int base, int exp)


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.


int power(int base, int exp) {
     
     //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,0) = 1;

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.

int power(int base, int exp) {
     
     //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


Related Posts to C++ Recursion – Power

Follow Discussion

One Response to “C++ Recursion – Power”

  1. Bert Says:

    Thanks. These problems have helped me out understand recursion a lot more. =)

Leave a Reply