C++ Recursion – Power Continued

Creating a power function using Recursion

So, previously we tried computing the Power function using recursion but we didn’t take into account when the exponent was negative. This continues the previous function, so if you haven’t yet, go back. Make sure you understand the following as well:

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

Power Function using Recursion

Below is our previous power function which takes into account only positive exponents. So how would we go on by taking into account negative exponents?

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;

}


Let’s start by coming up with a formula again. 

power(2,-1) = (1/2);

power(2,-2) = (1/2) * power(2, -1) = (1/2) * (1/2) = (1/4);

power(2,-3) = (1/2) * power(2,-2) = (1/2) * (1/4) = (1/8);

power(2,-4) = (1/2) * power(2,-3) = (1/2) * (1/8) = (1/16);

...

//Until exp == -1
power(base, -exp) = (1/base) * power(base, exp+1);


Taking into account negative exponents

So now that we have a formula, what would be our base case? We surely don’t want our previous base case to return 1 when (n==0) because that would be wrong.


if ( exp == -1 ) return (1/base);


Then simply applying the formula to do the computation of other values below -1:

int power(int base, int exp) {

      if ( n < - 1)
          return (1/base) * power(base, exp+1);
     else if ( n == -1 )
          return (1/base);
     //Return 1 when n is 0
     else if ( n == 0 )
          return 1;
     else if ( n == 1 )
           return base;
     else
          return base * power(base, exp-1);
     int result = base;

}



Now try it. Does it work?

Finalizing the Power Function using Recursion

Unfortunately, this won't work. Whenever you try computing the power of lets say power(2,-3) you will receive 0. Why? Because when you divide and have an int as one of the operands, an int is returned. Below is the fix. If you want to return a double, make sure both your operands are doubles.

int power(int base, int exp) {

      if ( n < - 1)
          return (1.0/base) * power(base, exp+1);
     //Return (1.0/base) when n == -1
     else if ( n == -1 )
          return (1.0/base);
     //Return 1 when n is 0
     else if ( n == 0 )
          return 1;
     else if ( n == 1 )
           return base;
     else
          return base * power(base, exp-1);
     int result = base;

}



By this time you should be able to work out similar problems involving recursion. Make sure you are truly grasping the subject. If not, feel free to ask questions.

Tags: , , , , , , ,