题目：

 Implement pow(x, n).

 

题解：

pow(x,n)就是求x的n次方。x的N次方可以看做：x^n = x^(n/2)*x^(n/2)*x^(n%2)。所以利用递归求解，当n==1的时候，x^n=x。

当然n是可以小于0的，2^(-3) = 1/(2^3)。按照上面那个规律就可以解决了。

 

代码如下：

 

 1     

public 

double power(

double x, 

int n) {

 2         

if (n == 0)

 3             

return 1;

 4  

 5         

double v = power(x, n / 2);

 6  

 7         

if (n % 2 == 0) {

 8             

return v * v;

 9         } 

else {

10             

return v * v * x;

11         }

12     }

13  

14     

public 

double pow(

double x, 

int n) {

15         

if (n < 0) {

16             

return 1 / power(x, -n);

17         } 

else {

18             

return power(x, n);

19         }

20     }

 Reference: http://fisherlei.blogspot.com/2012/12/leetcode-powx-n.html