让我们从一些数学事实开始：
- 对于正n，aⁿ=a⨯a⨯…⨯an次
- 对于负数n，aⁿ=⅟a⁻ⁿ=⅟（a⨯a⨯…⨯a）。这意味着 a 不能为零。
- 对于n = 0，即使 a 为零或负，aⁿ= 1 。
因此，让我们从n个正数开始，然后从那里开始。
因为我们希望我们的解决方案是递归的，所以我们必须找到一种方法来基于较小的n定义aⁿ，然后从那里开始。人们通常认为递归的方法是尝试找到n-1的解，然后从那里开始工作。
实际上，由于a since =a⨯（aⁿ⁻¹）在数学上是正确的，因此幼稚的方法将与您创建的方法非常相似：
public static int pow( int a, int n) { if ( n == 0 ) { return 1; } return ( a * pow(a,n-1));}但是，其复杂度为O（n）。为什么？因为对于n = 0，它不做任何乘法。对于n = 1，它执行一次乘法。对于n =
2，它调用pow（a，1），我们知道它是一个乘法，并将其相乘一次，所以我们有两个乘法。在每个递归步骤中都有一个乘法，有n个步骤。所以是O（n）。
为了使这个O（log n），我们需要将每个步骤应用于n 的 一部分 ，而不仅仅是n-1。在这里，有一个数学的事实，可以帮助我们：一个N 1 + N
2 = A 区N1 ⨯a 氮气。
这意味着我们可以将aⁿ计算为n / 2⨯an / 2。
但是，如果n为奇数会怎样？像a⁹将是一个4.5 ⨯a
4.5。但是我们在这里谈论整数幂。处理分数是完全不同的事情。幸运的是，我们可以将其表述为a⨯a⁴⨯a⁴。
因此，对于偶数，使用n / 2⨯an / 2；对于奇数，使用a⨯a n / 2⨯an / 2（整数除法，得到9/2 = 4）。
public static int pow( int a, int n) { if ( n == 0 ) { return 1; } if ( n % 2 == 1 ) { // Odd n return a * pow( a, n/2 ) * pow(a, n/2 ); } else { // Even n return pow( a, n/2 ) * pow( a, n/2 ); }}这实际上为我们提供了正确的结果（对于n为正数）。但实际上，这里的复杂度还是O（n）而不是O（log
n）。为什么？因为我们要计算两次幂。这意味着我们实际上在下一级别将其称为4次，在下一级别将其称为8次，依此类推。递归步骤的数量是指数的，因此可以通过我们将n除以2来实现的节省被抵消。
但实际上，只需要进行一些小的更正：
public static int pow( int a, int n) { if ( n == 0 ) { return 1; } int powerOfHalfN = pow( a, n/2 ); if ( n % 2 == 1 ) { // Odd n return a * powerOfHalfN * powerOfHalfN; } else { // Even n return powerOfHalfN * powerOfHalfN; }}在此版本中，我们仅调用一次递归。因此，我们很快就从64的幂中获得了32、16、8、4、2、1，然后完成了。每一步只有一个或两个乘法，只有六个步。这是O（log
n）。
所有这些的结论是：
- 为了获得O（log n），我们需要递归，该递归在每个步骤上只占n的一部分，而不只是n-1或n-任何东西。
- 但是，这只是故事的一部分。我们需要注意不要多次调用递归，因为在一个步骤中使用多个递归调用会创建指数复杂度，而使用n的分数会抵消该复杂度。
最后，我们准备好处理负数。我们只需要得到倒数⅟a⁻ⁿ。有两件事要注意：
- 不允许被零除。也就是说，如果a == 0，则不应执行计算。在Java中，在这种情况下会引发异常。最合适的现成异常是IllegalArgumentException。这是RuntimeException，因此您无需在方法中添加
throws
子句。main
读参数时，如果在方法中捕获了它或阻止了这种情况的发生，那将是很好的。 - 您无法再返回整数（实际上，我们应该使用
long
，因为使用会以很低的幂遇到整数溢出int
）-因为结果可能是分数。
因此，我们定义该方法，使其返回double。这意味着我们还必须修复的类型
powerOfHalfN。结果如下：
public static double pow(int a, int n) { if (n == 0) { return 1.0; } if (n < 0) { // Negative power. if (a == 0) { throw new IllegalArgumentException( "It's impossible to raise 0 to the power of a negative number"); } return 1 / pow(a, -n); } else { // Positive power double powerOfHalfN = pow(a, n / 2); if (n % 2 == 1) { // Odd n return a * powerOfHalfN * powerOfHalfN; } else { // Even n return powerOfHalfN * powerOfHalfN; } }}请注意，处理负数n的部分仅在递归的顶层使用。一旦我们
pow()递归调用，它总是带有正数，并且直到它达到0为止，符号都不会改变。
那应该是您运动的适当解决方案。但是，个人而言，我不喜欢
if最后的内容，因此这里是另一个版本。你能告诉我为什么这样做吗？
public static double pow(int a, int n) { if (n == 0) { return 1.0; } if (n < 0) { // Negative power. if (a == 0) { throw new IllegalArgumentException( "It's impossible to raise 0 to the power of a negative number"); } return 1 / pow(a, -n); } else { // Positive power double powerOfHalfN = pow(a, n / 2); double[] factor = { 1, a }; return factor[n % 2] * powerOfHalfN * powerOfHalfN; }}
