你的实现是O（logN）的，但它可以稍微更有效。
注意，在下文中，对数是以2为底的对数。
您有log（n）次power(a*a,n/2)调用，以及对 n 中设置的每个位的power(a, n-1)调用。
在 n 中设置的位数至多为log（n）+1。
因此，对power的调用次数至多为log（n）+log（n）+1。例如，当 n = 15时，调用序列为

power(15), power(14), power(7), power(6), power(3), power(2), power(1)

log（n）+log（n）+1 = 3+3+1 = 7
下面是一个更高效的实现，它只有log（n）+2次power调用。

int power(int a, int n) {
  if(n == 0) {
    return 1;
  }
  if (n&1 == 0) {
    return power(a*a, n/2);
  }else{
    return a * power(a*a, n/2);
  }
}

在这种情况下，当 n = 15时的调用序列是

power(15), power(7), power(3), power(1), power(0)

我删除了if (n == 1)条件，因为我们可以通过添加一个对power的调用来避免执行log（n）时间的测试。
然后我们有log（n）+2次调用，这比2log（n）+1次调用要好。

算法保持O（lgN）的原因是，即使对于奇数情况具有额外的调用，因为额外调用的数量由常数限制。在最坏的情况下，N/2 在每次迭代时都是奇数，但这只会使额外调用的数量加倍（常数为2）。也就是说，在最坏的情况下，将有21 g N 个调用来完成算法。
为了更容易地观察到算法是0（lgN），您可以重写函数以始终在每次迭代时将功率减少一半，使得在最坏情况下，仅存在lgN 调用。为了利用尾部递归，可以添加一个函数参数来累加奇数 N 的进位乘数。

int power_i (int a, unsigned N, int c) {
    if (N == 0) return c;
    return power_i(a*a, N/2, N%2 ? a*c : c);
}

int power (int a, unsigned N) {
    return power_i(a, N, 1);
}

尾递归的优点是优化后的代码将被大多数现代C编译器转换为简单的循环。
在线试用！

幂函数有两种基本情况：n = 0和n = 1。
幂函数有两个递归调用。在任何给定的调用中，只进行其中一个。
让我们首先考虑当n是偶数时的情况：在这种情况下，使用n / 2进行递归调用。
如果所有调用都使用这种情况，那么你在每个调用中将n减半，直到达到1。这实际上是log(n)调用（基本情况下加1）。
另一种情况是，当n是奇数时，n只减1。如果所有的调用最终都使用这个递归调用，那么这个函数将被调用n次;显然不是对数而是线性的。

但是当你从奇数中减去1时会发生什么？它变成了一个偶数。因此，上述令人担忧的线性行为不会发生。

最差情况为：n是奇数，因此使用第二递归调用。现在n是偶数，因此第一次递归调用。现在n是奇数，这个使用第二，…以此类推，直到n为1。在这种情况下，每第二次调用将n减少到n / 2。因此，您需要2 * log(n)调用（再加上一个基本情况）。
所以是的，这是在O(log(n))中。这个算法通常被称为binary exponentiation。

这是另一种表示法：

long double xpow(long double a, int b ) {
    double ret = 1;
        while (b) {
            if (b & 1)
                ret = ret  * a ;
            a = a * a ;
            b >>= 1;
        }
     return ret;
}