指数计算应该是递归程序设计的入门级题目，但是在一场面试中写一个bug-free的代码还是需要多多注意边界条件。首先是底数的正负会影响结果，其次是指数的正负，也会影响结果。因为函数原型是pow(int x, int n),所以指数一定是整数。题目的一个简单思路是使用一个循环计算n遍x的乘积，但是这样的计算复杂度太高。如果我们想计算pow(x,16),我们需要做15次乘法，这样的开销很大。使用分治法换一个角度考虑，pow(x,16)其实可以分成两个pow(x,8)的乘积，同样的，pow(x,8)可以分成两个pow(x,4)的乘积，这样计算下去，只需要计算4次乘法就可以完成。如果pow(x,15)该怎么算？其实只要计算两个pow(x,7)的乘积再乘以x即可。在实现的时候有一个细节需要注意。当写递归的代码时，不要使用return pow(x,n/2)*pow(x,n/2)这样的语句，因为这样会造成重复计算pow(x,n/2)两次，增加运算的复杂度。使用一个变量保存pow(x,n/2)的结果才是正解。此题同样是Leetcode OJ上的题目，下面是其Java实现。
public class Solution {
/**
* Implement pow(x, n).
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(new Solution().pow(2.0,10));
}
public double pow(double x, int n) {
// Start typing your Java solution below
// DO NOT write main() function
boolean neg = false;
if((x == 0 && n == 0) || (x == 1)){
return 1;
}
else if(x == 0){
return 0;
}
else if (x > 0){
neg = false;
}
else{
if(neg){
return pow(x*(-1),n);
}
else{
return (-1)* pow(x*(-1),n);
}
}
if(n == 0){
return 1;
}
else if(n == 1){
return x;
}
else if (n > 0){
if( n % 2 == 0){
double temp = pow(x, n/2);
return temp * temp;
}
else{
double temp = pow(x, (n-1)/2);
return temp * temp * x;
}
}
else{
double temp = pow(x, n*(-1));
return 1.0 / temp;
}
}
}