求 pow(x,n) 先来说说快速幂，正常的做法线性速度，O(n)的时间复杂度。快速幂的时间的复杂度O(log2(n))
其数学推导如下：
当n为偶数时 若2k = n 即k = n/2 则x^(2k) = x^(k)x^(k);
当n为奇数时 若2k+1=n 即k = n/2 则x^(2k+1) = x^(k)x^(k)*x;
递归结束条件 ： n = 0 return 1.0

这里还需注意一下 n可能为正 也可能为负

具体程序 见代码：

//采用递归很巧妙的方法
    public double myPow(double x, int n) {
    	if(n<0){
    		return 1/calcPow(x, -n);  //需要注意    n为负的情况
    	}else{
    		return calcPow(x, n);
    	}
    	
    }
    
    public double calcPow(double x, int n){
    	if(n==0){
    		return 1.0;
    	}
    	double val = calcPow(x, n/2);
    	if(n%2==0){
    		return val*val;
    	}else{
    		return val*val*x;
    	}
    }


而对于快速幂取模。求(a^n)%M

对于求模，有个很关键的公式 （ac）%m = (a%m)(c%m)%m
同时呢： (a+d)%m = ((a%m)+(d%m))%m
数学推导如下：
若n为偶数： 假设 n = 2k (a^2k)%m = ((a^k)%m)((a^k)%m)%m
若n为奇数： 假设 n = 2k+1 (a^(2k+1))%m = (((a^k)%m(a^k)%m)%m*a%m)%m

递归结束条件 ： n = 0 return 1.0

具体程序见代码： 递归方法 method1：

public int modPow(int x,int n,int m){
		return modOfQuickPow(x, n, m);
	}
//快速幂取模的方法   求(x^n)%m   这里的n假设为非负数  m假设为正整数   x为正整数   
	private int modOfQuickPow(int x,int n,int m){
		if(n==0){
			return 1;
		}
		if(n==1){
			return x%m;
		}
		if(n%2==0){
			// (a^2k)%m = ((a^k)%m)*((a^k)%m)%m
			return (modOfQuickPow(x, n/2, m)%m)*(modOfQuickPow(x, n/2, m)%m)%m;
		}else{
			//(a^(2k+1))%m = (((a^k)%m*(a^k)%m)%m*a%m)%m
			return (modOfQuickPow(x, n/2, m)%m)*(modOfQuickPow(x, n/2, m)%m)%m*(x%m)%m;
		}
	}


递归 method2

//快速幂取模  方法二
private int modOfQuickPow1(int x,int n,int m){
	if(n==0){
		return 1;
	}
	if(n==1){   //如果这个条件没有会无限递归下去  比如1    n/2 = 0  而 n-n/2 = 1 死循环
		return x%m;
	}
	return (modOfQuickPow1(x, n/2, m)%m*modOfQuickPow1(x, n-n/2, m)%m)%m;
}