当n是偶数时，优化x ^ n的recursion方法
我需要写一个使用Java的recursion方法，这个方法使用了一个double x和一个整数n，并返回x ^ n。 这是我迄今为止。
public static double power(double x, int n) { if (n == 0) return 1; if (n == 1) return x; else return x * (power(x, n-1)); } 此代码按预期工作。 但是，我正在努力去做更多的事情，并执行以下可选练习：
“可选的挑战：当n是偶数时，使用x ^ n =（x ^（n / 2））^ 2，可以使这个方法更有效率。
当n是偶数时，我不知道如何实现最后一个公式。 我不认为我可以使用recursion。 我试图实现以下，但它也行不通，因为我不能把一个int的权力加倍。
if (n%2 == 0) return (x^(n/2))^2;
有人能指出我正确的方向吗？ 我觉得我失去了一些明显的东西。 所有帮助赞赏。
这与x ^ n == x *（x ^（n-1））的原理完全相同：插入recursion函数x ^（n / 2）和（…）^ 2，但是确保你不要为n == 2input无限recursion（因为2也是偶数）：
if (n % 2 == 0 && n > 2) return power(power(x, n / 2), 2); }
或者，你可以使用一个中间variables：
if (n % 2 == 0) { double s = power(x, n / 2); return s * s; }
我可能只是把2作为一个特例，并且避免了“和”条件和额外的variables：
public static double power(double x, int n) { if (n == 0) return 1; if (n == 1) return x; if (n == 2) return x * x; if (n % 2 == 0) return power(power(x, n / 2), 2); return x * (power(x, n - 1)); }
PS我认为这应该也工作:)
public static double power(double x, int n) { if (n == 0) return 1; if (n == 1) return x; if (n == 2) return x * x; return power(x, n % 2) * power(power(x, n / 2), 2); }
当n是偶数时，公式就是你所写的： n除以2，recursion调用power ，并将结果平方。
当n是奇数时，公式稍微复杂一些：从n减1 ，对n/2进行recursion调用，对结果进行平方，并乘以x 。
if (n%2 == 0) return (x^(n/2))^2; else return x*(x^(n/2))^2;
n/2截断结果，所以减1不是明确的。 这是Java中的一个实现：
public static double power(double x, int n) { if (n == 0) return 1; if (n == 1) return x; double pHalf = power(x, n/2); if (n%2 == 0) { return pHalf*pHalf; } else { return x*pHalf*pHalf; } }
演示。
提示： ^操作不会在Java中执行幂运算，但是你写的函数， power会。
另外，不要忘记对一个数字进行平方，就像把它乘以一样。 不需要任何函数调用。
对你的函数做一个小的修改，它会减lessrecursion调用的次数：
public static double power(double x, int n) { if (n == 0) { return 1; } if (n == 1) { return x; } if (n % 2 == 0) { double temp = power(x, n / 2); return temp * temp; } else { return x * (power(x, n - 1)); } }
以来
x^(2n) = (x^n)^2
你可以把这个规则添加到你的方法中，或者使用你写的幂函数，就像Stefan Haustein所build议的那样，或者使用常规的乘法运算符，因为看起来你可以这样做。
请注意，不需要两个基本情况n = 1和n = 0，其中一个足够了（最好使用基本情况n = 0，因为否则您的方法将不会被定义为n = 0）。
public static double power(double x, int n) { if (n == 0) return 1; else if (n % 2 == 0) double val = power(x, n/2); return val * val; else return x * (power(x, n-1)); }
在任何情况下都不需要检查n> 2。
这只是提醒我可以做更多的优化，以下代码。
class Solution: # @param x, a float # @param n, a integer # @return a float def pow(self, x, n): if n<0: return 1.0/self.pow(x,-n) elif n==0: return 1.0 elif n==1: return x else: m = n & (-n) if( m==n ): r1 = self.pow(x,n>>1) return r1*r1 else: return self.pow(x,m)*self.pow(x,nm)
什么是更多的中间结果可以记住，避免冗余计算。
