递归计算base的n次方值

Question

这是我的解决方案：

 public int powerN(int base, int n) {

    if(n == 0)
       return 1;

    else if(n % 2 == 0)
       return base * base;

    else
       return base * powerN(base, n-1); 

 }

但是，如果 n > 3 那么这个功能就不起作用了。 例如，powerN(2, 4) 产生 4，powerN(2, 5) 产生 8。 我知道存在一个更简单的解决方案，但令我困扰的是我无法弄清楚为什么它不能正常工作。

Answer 1

else if(n % 2 == 0)
   return base * base;

这一位是不正确的 - 它返回任何偶次幂的平方，而不仅仅是 2。看起来您正在尝试实现 平方和乘法优化。因此，如果您想要计算 powerN(base, n)，您可以使用什么递归调用来利用 n 是偶数这一事实？您将为 base 和 n 传递哪些新值？使用恒等式 b^2‌n = (b²) ⁿ。

Answer 2

变成伪代码

让我把你的代码翻译成伪代码：

public int powerN(int base, int exponent)  {
    if the exponent is 0
        then return 1
    otherwise, if the exponent is even
        then return base * base
    otherwise
        base * powerN(base, exponent - 1)
}

第二个分支有一个逻辑错误。您的代码所说的是这样的：“只要指数是偶数，结果就应该是base * base（即base平方）”。您已经提到过，这是运行代码时得到的结果。

如何解决

您可能想要做的是将 base 提高到 exponent 的一半（base * base * base * ... for 指数/2 次），然后将该数字与其自身相乘。这样，您就可以得到基数乘以自身指数倍。

用伪代码来说：

otherwise, if the exponent is even
    then return powerN(base, exponent / 2) * powerN(base, exponent / 2)

实际上，这实际上是这样的：

otherwise, if the exponent is even
    then {
        let x = powerN(base, exponent / 2)
        return x * x
    }

完成。大多。

将其翻译回 Java 即可。

Answer 3

有问题的代码是：

else if(n % 2 == 0)
   return base * base;

这个 if 会捕获 2 的所有幂。因此 0,2,4,8 会导致错误的计算。

您应该担心的唯一极端情况是当n <= 0时。

这是更正后的代码：

public static int powerN(int base, int n) {
    if (n < 0) {
        throw new IllegalArgumentException("Illegal Power Argument");
    }
    if (n == 0) {
        return 1;
    } else {
        return base * powerN(base, n - 1);
    }
}

这是测试：

public static void main(String args[]) throws NullPointerException {
    for (int i = 0; i < 10; i++) {
        System.out.println(powerN(2, i));
    }
}

和输出：

run:
1
2
4
8
16
32
64
128
256
512
BUILD SUCCESSFUL (total time: 1 second)

Answer 4

在偶数情况下，您需要在返回之前base = powerN(base, n/2);。

Answer 5

为了计算幂，您只需要考虑 x^0 的特殊情况，对于所有其他情况（n>0），您可以使用 x*powerN(x, n-1) 的递归

Answer 6

class Square{
    int r=1;
     int power(int n, int p) throws Exception
    {
         int s=n;
        if(n<0||p<0)
        {
        throw new Exception("n and p must be positive");
        }

    if(p==2)
    {
        return n*n*r;
    }
    else
    {
        r=r*n;
        return power(n,p-1);
    }

    }
}

Answer 7

这是 C++ 中的答案，这是一系列 a^b =

int power(int a, int b)
{
   int k = a;
   int c = b;
   if (c == 1)
    {
        return a;
    }
   else if (c == 0)
    {
        return 1;
    }
   else if (c >= 1)
   {
        c--;
        k = k*power(k,c);
   }
   cout << k << endl;
   return k;

}

int main()
{
    cout << "Enter a number " << endl;
    int n;
    cin >> n;
    cout << "Enter power " << endl;
    int c1 = 0;
    cin >> c1;
    cout << endl ;
    cout << "These are all the powers up to " << n << " to the power " << c1 << endl;
    power(n,c1);
    return 0;
}

Answer 8

public static int powerN(int base, int n ){
    if (n==0){
        return 1;
    }else
        return base*powerN(base,n-1);
}

Answer 9

你的问题是代码

if (n % 2 == 0)
返回基数 * 基数；

这使得您的函数在幂 (n) 为偶数时返回底数的平方，而在幂 (n) 为奇数时返回立方。
你需要的唯一终止条件是 n==0 return 1 并且它应该递归地满足你的 n 次方底数规范

Answer 10

public int powerN(int base, int power) {
    if (power == 1)
        return base;
    else if (power % 2 == 0) {
        int x = powerN(base, power / 2);
        return x * x;
    } else {
        int x = powerN(base, (power - 1) / 2);
        return x * x * base;
    }
}