Question

Given two integers x and n, where n is non-negative, efficiently calculate the value of power function pow(x, n). Example: pow (-2, 10) = 1024. How many recursive calls are you invoking ?

Answer 1

Code:
--------
int pow(int x, int n)
{
   if (n == 0) {
      return 1;
   }
   else{
      int half = pow(x, n / 2);
      if (n % 2 == 0) {
         return half*half;
      }
      else {
         return x*half*half;
      }
   }
}



Recursive calls:
------------------
Recursive formula for the above pow() function is
T(n) = T(n/2) + 1
Solving Recursive formula
T(n) = T(n/2) + 1
     = T(n/4) + 1 + 1
     = T(n/8) + 1 + 1 + 1
     ......
     ......
     ......
     = T(n/n) + 1 + .... + 1 + 1 + 1 [log2(n) terms]
     = 1 + 1 + .... + 1 + 1 + 1 [log2(n) terms]
     = log2(n)
So, Number of recursive calls = log2(n)