Pow(x, n) (LeetCode Math)

Question: Implement pow(x, n).

Idea: pow(x, n)= pow(x, n/2) * pow(x, n/2). We just need to handle a few cases, e.g. "n<0", "n is odd", "n is even".

Time: O(lgn) Space: O(lgn) (we need a stack to cache the intermedia results. The iterative version will be O(1)).

Recursive Code: 

 public class Solution {  
   public double pow(double x, int n) {  
     if(n==0)  
       return 1;  
     if(n<0)  
     {  
       if(n==Integer.MIN_VALUE)  
         return 1.0/pow(x,Integer.MAX_VALUE)/x;  
       else  
         return 1.0/pow(x,-n);  
     }  
     if(n==1)  
       return x;  
     double half=pow(x,n/2);  
     if(n%2==0)  
       return half*half;  
     else  
       return half*half*x;  
   }  
 }