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:

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

Example:

1
2

pow(2,3);
pow(5,4);

Result:

1
2

8
625

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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.


1

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.


1
2
3
4
5
6

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.

1
2
3
4
5
6
7
8
9
10
11
12
13

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.

1
2
3
4
5
6
7
8
9
10
11
12

int power(int base, int exp) {
 
     //Return 1 when n is 0
     if ( exp == 0 ) 
          return 1;
     else if ( exp == 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?

Tags: , , , , , , ,

  • Bert

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

  • Bert

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

  • RubenV

    pow(2,3);
    pow(5,4);

    Result:

    8
    125

    pow(5,4) ==> 625 instead of 125? :p

    • http://talkbinary.com Diego Villasenor

      Thanks for the correction. I fixed it, I was just glad the logic in the recursive function was correct.