使用递归的幂函数

我必须用Java 编写一个power 方法。它接收两个整数，它们是正数还是负数并不重要。它的复杂度应该是O(logN)。它还必须使用递归。我当前的代码得到两个数字，但我一直输出的结果为零，我不明白为什么。

import java.util.Scanner;

public class Powers {

    public static void main(String[] args) {
        float a;
        float n;
        float res;

        Scanner in = new Scanner(System.in);
        System.out.print("Enter int a ");
        a = in.nextFloat();

        System.out.print("Enter int n ");
        n = in.nextFloat();

        res = powers.pow(a, n);

        System.out.print(res);
    }

    public static float pow(float a, float n) {
        float result = 0;

        if (n == 0) {
            return 1;
        } else if (n < 0) {
            result = result * pow(a, n + 1);
        } else if (n > 0) {
            result = result * pow(a, n - 1);
        }

        return result;
    }
}

让我们从一些数学事实开始：

• 对于正 n，aⁿ = a⨯a⨯…⨯a n 次
• 对于负数 n，aⁿ = ⅟a⁻ⁿ = ⅟(a⨯a⨯…⨯a)。这意味着a不能为零。
• 对于 n = 0，aⁿ = 1，即使a为零或负数。

因此，让我们从积极的 n 情况开始，并从那里开始工作。

由于我们希望我们的解决方案是递归的，因此我们必须找到一种基于较小的 n 来定义 aⁿ 的方法，并从那里开始工作。人们思考递归的通常方式是尝试找到 n-1 的解决方案，并从那里开始工作。

事实上，由于 aⁿ = 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)。

In order to make this O(log n), we need every step to be applied to a fraction of n rather than just n-1. Here again, there is a math fact that can help us: a^n₁+n₂ = a^n₁⨯a^n₂.

This means that we can calculate aⁿ as a^n/2⨯a^n/2.

But what happens if n is odd? something like a⁹ will be a^4.5⨯a^4.5. But we are talking about integer powers here. Handling fractions is a whole different thing. Luckily, we can just formulate that as a⨯a⁴⨯a⁴.

So, for an even number use a^n/2⨯a^n/2, and for an odd number, use a⨯ a^n/2⨯a^n/2 (integer division, giving us 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)。

所有这一切的结论是：

1. 为了获得 O(log n)，我们需要在每一步都对 n 的一小部分进行递归，而不仅仅是 n - 1 或 n - 任何东西。
2. 但这个分数只是故事的一部分。我们需要小心，不要多次调用递归，因为在一个步骤中使用多次递归调用会产生指数复杂性，而使用 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;
    }
}