我用递归，如果exp是偶数，5^10 =25^5。

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&&exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&&exp%2!=0){
      return base*pow(base,exp-1);
   }
}

我用递归，如果exp是偶数，5^10 =25^5。

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&&exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&&exp%2!=0){
      return base*pow(base,exp-1);
   }
}

请注意，平方求幂并不是最优的方法。这可能是一种适用于所有指数值的通用方法，但对于特定的指数值，可能有更好的序列，需要更少的乘法。

例如，如果你想计算x^15，用平方求幂的方法会给你:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

这一共有6次乘法。

事实证明，这可以通过“仅仅”5次加法链幂运算来完成。

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

没有有效的算法来找到这个最优的乘法序列。从维基百科:

The problem of finding the shortest addition chain cannot be solved by dynamic programming, because it does not satisfy the assumption of optimal substructure. That is, it is not sufficient to decompose the power into smaller powers, each of which is computed minimally, since the addition chains for the smaller powers may be related (to share computations). For example, in the shortest addition chain for a¹⁵ above, the subproblem for a⁶ must be computed as (a³)² since a³ is re-used (as opposed to, say, a⁶ = a²(a²)², which also requires three multiplies).

O(log N)的解决方案在Swift…

// Time complexity is O(log N)
func power(_ base: Int, _ exp: Int) -> Int { 

    // 1. If the exponent is 1 then return the number (e.g a^1 == a)
    //Time complexity O(1)
    if exp == 1 { 
        return base
    }

    // 2. Calculate the value of the number raised to half of the exponent. This will be used to calculate the final answer by squaring the result (e.g a^2n == (a^n)^2 == a^n * a^n). The idea is that we can do half the amount of work by obtaining a^n and multiplying the result by itself to get a^2n
    //Time complexity O(log N)
    let tempVal = power(base, exp/2) 

    // 3. If the exponent was odd then decompose the result in such a way that it allows you to divide the exponent in two (e.g. a^(2n+1) == a^1 * a^2n == a^1 * a^n * a^n). If the eponent is even then the result must be the base raised to half the exponent squared (e.g. a^2n == a^n * a^n = (a^n)^2).
    //Time complexity O(1)
    return (exp % 2 == 1 ? base : 1) * tempVal * tempVal 

}

迟到的人:

下面是一个尽可能处理y < 0的解。

It uses a result of intmax_t for maximum range. There is no provision for answers that do not fit in intmax_t. powjii(0, 0) --> 1 which is a common result for this case. pow(0,negative), another undefined result, returns INTMAX_MAX intmax_t powjii(int x, int y) { if (y < 0) { switch (x) { case 0: return INTMAX_MAX; case 1: return 1; case -1: return y % 2 ? -1 : 1; } return 0; } intmax_t z = 1; intmax_t base = x; for (;;) { if (y % 2) { z *= base; } y /= 2; if (y == 0) { break; } base *= base; } return z; }

这段代码使用了一个永久循环for(;;)，以避免在其他循环解决方案中常见的最终基数*=基数。这个乘法是1)不需要的，2)可能是int*int溢出，也就是UB。

int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}