递归码功率函数

Question

我实现了一个递归函数计算x的y

public static int power(int x, int y){
    if(y>0){
        x = x*x;
        power(x,y-1);
    }
    return x;
}

该方法应该返回x ^ y的值,但它返回原始x值的平方(x ^ 2),即使y大于2,我缺少什么？

Answer 1

你没有返回递归结果(当你递归时).更改

power(x,y-1);

至

return power(x,y-1);

你最后的回报应该是1(因为它是这种<= 0情况).更改

return x;

至

return 1;

实际上,正如评论中指出的那样,你的算法比我想象的更有缺陷.应该是这样的

if (y > 0) {
    return x * power(x, y - 1);
}
return 1;

如果你想支持更大范围的值,那么你可以做x一个long和return一个BigInteger.如果我们对问题应用一点数学,我们也可以优化算法.就像是

public static BigInteger power(long x, int y) {
    if (y < 0) { // <-- throw an error on negative values for y
        throw new UnsupportedOperationException(String.format( //
                "Cannot calculate power(%d, %d).", x, y));
    } else if (y == 0) { // <-- x^0 = 1
        return BigInteger.ONE;
    } else if (y == 1) { // <-- x^1 = x
        return BigInteger.valueOf(x);
    } else if (y == 2) { // <-- x^2 = x * x
        BigInteger bi = BigInteger.valueOf(x);
        return bi.multiply(bi);
    }
    // x^y = x^(y/2) * x^(y/2)
    final int half = (y / 2);
    if (y == 2 * half) { // <-- handle even y values
        return power(x, half).multiply(power(x, half));
    } else { // <-- handle odd y values
        return power(x, half).multiply(power(x, 1 + half));
    }
}