具有递归的快速幂法

Question

我正在编写一个实例方法来计算自然数的幂。如果电源为偶数，则使用类似于base^power = ( base^ power /2)^ power /2的快速加电方法，否则基本^power= base*(base^power/2)^power/2。下面的代码会导致溢出错误。

这是我的代码：

 @Override
public void power(int p) {
    assert p >= 0 : "Violation of: p >= 0";

    // TODO - fill in body
    NaturalNumber one = new NaturalNumber1L(1);
    if (p == 0) {
        this.copyFrom(one);
    } else if (p > 1) {
        this.power(p);
    }

    if (p > 1) {
        if (p % 2 == 0) {
            this.power(p / 2);
            this.multiply(this);
        } else {
            this.multiply(this);
            this.power((p - 1) / 2);
            this.multiply(this);
        }
    }
}

Answer 1

问题是这个代码：

else if (p > 1) {
    this.power(p);
}

在这里，如果p大于1，则递归调用该函数，而不对p进行任何修改。在下面的执行中，输入相同的if并再次调用该函数。这会重复，直到溢出。