使用递归创建幂方法

Question

我对编程很陌生，Java是我的第一种真正的语言。在课堂上的这一点上，我们正在讨论递归，并被要求制作一个适合某些参数的方法：

方法是这样的：public void power（int p），其中我们不能更改方法的形式参数。我已经在其他地方研究过了，似乎很多解决方案都涉及添加int n（用于对其执行幂运算的数字）作为参数。

在写类似的方法时，我们被鼓励用"这个"来表达我们试图改变的东西。通常在实例方法中使用"this"，例如：this.increment（）.

当我为它编写伪代码时，我发现我想做以下事情：

public void power(int p) {
    assert p >= 0 : "Violation of: p >= 0";
    int x = 0;
    if (p == 0) {
        return 0;
    }
    if (p % 2 == 0) {
        x = this.power(p / 2);
        return x * x;
    } else {
        return this * this.power(p - 1);
    }

我只是不知道如何编写它，这样它才能真正与eclipse和java一起运行。任何见解都将不胜感激！

Answer 1

以下停止条件错误，应返回1。

if (p == 0) {
  return 0; // should return 1
}

如果使用this，则不能在Java中使用乘法运算符*。您可以有一个multiplyBy函数，它不应该使被调用者发生突变：

public int multiplyBy(int x) {
    return this.value * x;
}

正如您在上面的方法中看到的，您需要有一个用于存储整数值的实例属性。所以你的代码现在看起来像：

public void power(int p) {
  assert p >= 0 : "Violation of: p >= 0";
  int x = 0;
  if (p == 0) {
    return 1;
  }
  if (p % 2 == 0) {
    x = this.power(p / 2);
    return x * x;
  } else {
    return this.multiplyBy(this.power(p - 1));
  }
}

Answer 2

在进行递归时，您必须考虑两件事。

• 基本情况：何时停止递归
• 递归大小写：何时继续

对于一种力量，考虑一下它可以这样定义：

pow(x, p) = x * pow(x, p-1) if p > 0 else 1

原因：

• x²是x*x
• x⁰为1

因此，考虑到这一点，让我们考虑一些边缘情况。对于这种情况，我们不想接受任何负值，因此assert工作正常。最好使用一个异常，因为不是每个人都会启用带有-ea标志的断言。

public long power(int x, int p) {
    if(p < 0) {
        throw new IllegalArgumentException("p is negative, not allowed");
    }
    if(p == 0) {
        return 1;
    } else {
        return x * power(x, p - 1);
    }
}

Answer 3

我会创建方法static（因此您不需要实例）。传入要提升为幂的值和指数。类似的东西

public static long power(int n, int pow) {
    assert pow >= 0 : "Violation of: pow >= 0";
    if (pow == 0) { // <-- n^0 = 1
        return 1;
    } else if (pow == 1) { // <-- n^1 = n
        return n;
    }
    return n * power(n, pow - 1); // <-- recurse
}

作为实例方法

通常我会使用Math.pow(double, double)，但如果你真的需要一个原地递归实现，那么你可以做一些类似的事情

class Power {
    public Power(int n) {
        this.n = n;
    }
    private int n;
    private long result = -1;
    public String toString() {
        return String.valueOf(result);
    }
    public long getResult() {
        return result;
    }
    public long power(int pow) {
        assert pow >= 0 : "Violation of: pow >= 0";
        if (pow == 0) { // <-- n^0 = 1
            return this.result = 1;
        } else if (pow == 1) { // <-- n^1 = n
            return this.result = this.n;
        }
        return this.result = this.n * this.power(pow - 1); // <-- recurse
    }
    public void setN(int n) {
        this.n = n;
    }
    public int getN() {
        return n;
    }
}

Answer 4

我想你正在寻找这个。

class Ideone  
{   
  public static void main (String[] args) throws java.lang.Exception  
 {
    Test t = new Test(2);
    System.out.println(t.power(5));
 }
}

class Test
{
int n;
Test(int n)
{
    this.n = n;
}
public int power(int p) {
 int x = 0;
 if (p == 0) {
    return 1;
 }
 if (p == 1) {
     return this.n;
 }
 if (p % 2 == 0) {
    x = this.power(p / 2);
    return x * x;
 } 
 else {
    return this.n * this.power(p - 1);     
     }      
}}

你可以在https://ideone.com/0ghIVe。