使用递归的幂函数 [英] Power function using recursion

问题描述

我必须用Java编写一个power方法。它接收两个整数，如果它们是正数或负数则无关紧要。它应该具有 O（logN）的复杂性。它还必须使用递归。我当前的代码得到两个数字，但我保持输出的结果为零，我无法弄清楚原因。

I have to write a power method in Java. It receives two ints and it doesn't matter if they are positive or negative numbers. It should have complexity of O(logN). It also must use recursion. My current code gets two numbers but the result I keep outputting is zero, and I can't figure out why.

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;
    }
}

推荐答案

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

Let's start with some math facts:

• 对于正n，aⁿ=a⨯a⨯...⨯an次


• 对于负n，aⁿ=⅟a - ⁿ=⅟（a⨯a⨯...⨯a）。这意味着 a 不能为零。


• 对于n = 0，aⁿ= 1，即使 a 为零或负数。

• For a positive n, aⁿ = a⨯a⨯…⨯a n times
• For a negative n, aⁿ = ⅟a⁻ⁿ = ⅟(a⨯a⨯…⨯a). This means a cannot be zero.
• For n = 0, aⁿ = 1, even if a is zero or negative.

所以让我们从积极的n案例开始，然后在那里工作。

So let's start from the positive n case, and work from there.

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

Since we want our solution to be recursive, we have to find a way to define aⁿ based on a smaller n, and work from there. The usual way people think of recursion is to try to find a solution for n-1, and work from there.

事实上，因为从数学上来说，aⁿ= a ⨯（aⁿ - 1），天真的方法与你创建的非常类似：

And indeed, since it's mathematically true that aⁿ = a⨯(aⁿ⁻¹), the naive approach would be very similar to what you created:

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）。

However, the complexity of this is O(n). Why? Because For n=0 it doesn't do any multiplications. For n=1, it does one multiplication. For n=2, it calls pow(a,1) which we know is one multiplication, and multiplies it once, so we have two multiplications. There is one multiplication in every recursion step, and there are n steps. So It's O(n).

为了使这个O（log n），我们需要将每个步骤应用于分数 n而不仅仅是n-1。在这里，有一个数学事实可以帮助我们： ^{n 1 + n 2} = a ^{n 1} ⨯a ^{n 2} 。

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₂.

这意味着我们可以将aⁿ计算为 ^{n / 2} ⨯a ^{n / 2} 。

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

但如果n是奇数，会发生什么？像a⁹这样的东西将是 ^4.5 ⨯a ^4.5 。但我们在这里讨论整数权力。处理分数是完全不同的事情。幸运的是，我们可以将其表述为a⨯a⁴⨯a⁴。

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⁴.

因此，对于偶数使用 ^{n / 2} ⨯a< sup> n / 2 ，对于奇数，使用a⨯a ^{n / 2} ⨯a ^{n / 2} （整数除法，给出9 / 2 = 4）。

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 );
    }
}

这实际上给了我们正确的结果（积极的那就是）。但事实上，这里的复杂性是O（n）而不是O（log n）。为什么？因为我们两次计算权力。这意味着我们实际上在下一级别调用它4次，在下一级别调用8次，依此类推。递归步骤的数量是指数级的，所以这取消了我们通过将n除以2所做的假设。

This actually gives us the right results (for a positive n, that is). But in fact, the complexity here is, again, O(n) rather than O(log n). Why? Because we're calculating the powers twice. Meaning that we actually call it 4 times at the next level, 8 times at the next level, and so on. The number of recursion steps is exponential, so this cancels out with the supposed saving that we did by dividing n by two.

但事实上，只需要一个小的修正：

But in fact, only a small correction is needed:

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，16,8,4,2,1和非常快速地获得64的幂。每一步只有一到两次乘法，而且只有六个步骤。这是O（log n）。

In this version, we are calling the recursion only once. So we get from, say, a power of 64, very quickly through 32, 16, 8, 4, 2, 1 and done. Only one or two multiplications at each step, and there are only six steps. This is O(log n).

所有这一切的结论是：

1. 要获得一个O（log n），我们需要递归，每个步骤的n分数而不是n - 1或n - 任何东西。


2. 但分数是只是故事的一部分。我们需要注意不要多次调用递归，因为在一个步骤中使用几个递归调用会产生指数复杂性，使用一小部分n取消。

最后，我们准备好处理负数。我们只需得到倒数⅟a - ⁿ。有两件重要的事情需要注意：

Finally, we are ready to take care of the negative numbers. We simply have to get the reciprocal ⅟a⁻ⁿ. There are two important things to notice:

• 不允许除以零。也就是说，如果你得到a = 0，你不应该执行计算。在Java中，我们在这种情况下抛出异常。最合适的现成例外是IllegalArgumentException。这是一个RuntimeException，因此您不需要在方法中添加 throws 子句。如果您在读取参数时在 main 方法中捕获它或阻止发生这种情况将会很好。


• 你不能再返回一个整数（事实上，我们应该使用 long ，因为我们使用进行整数溢出以获得相当低的权限int ） - 因为结果可能是小数。

• Don't allow division by zero. That is, if you got a=0, you should not perform the calculation. In Java, we throw an exception in such a case. The most appropriate ready-made exception is IllegalArgumentException. It's a RuntimeException, so you don't need to add a throws clause to your method. It would be good if you either caught it or prevented such a situation from happening, in your main method when you read in the arguments.
• You can't return an integer anymore (in fact, we should have used long, because we run into integer overflow for pretty low powers with int) - because the result may be fractional.

所以我们定义方法以便它返回double 。这意味着我们还必须修复 powerOfHalfN 的类型。结果如下：

So we define the method so that it returns double. Which means we also have to fix the type of powerOfHalfN. And here is the result:

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之前不会改变。

Note that the part that handles a negative n is only used in the top level of the recursion. Once we call pow() recursively, it's always with positive numbers and the sign doesn't change until it reaches 0.

这应该是你锻炼的适当解决方案。但是，我个人不喜欢最后的 if ，所以这是另一个版本。你能说出为什么会这样吗？

That should be an adequate solution to your exercise. However, personally I don't like the if there at the end, so here is another version. Can you tell why this is doing the same?

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;
    }
}

这篇关于使用递归的幂函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！