java - 使用重复平方计算幂的递归方法

Question

我写了这个递归方法:

public class Main {

    public static int p(int x, int n) {
        if (n == 0)
            return 0;
        else if (n % 2 == 0)
            return p(x, (n / 2)) * p(x, (n / 2));
        else
            return x * p(x, (n - 1 / 2)) * p(x, (n - 1 / 2));

    }

    public static void main(String[] args) {

        System.out.println(Main.p(2, 3));

    }

}

但是，在运行它时，我收到了 StackOverflowError - 我查了一下，似乎递归“太深”并且堆栈无法处理它。但我很困惑，因为当 n=0 时，递归应该停止，因为这是基本情况。我该如何纠正这个问题？

Answer 1

您需要使用正确的括号，即确保您的括号执行您想要的操作。

public class Main
{
    public static int p(int x, int n) 
    {
        if (n == 0)
            return 1;
        else if (n % 2 == 0)
            return p(x, (n / 2)) * p(x, (n / 2));
        else
            return x * p(x, ((n - 1) / 2)) * p(x, ((n - 1) / 2));
    }

    public static void main(String[] args)
    {
        System.out.println(Main.p(2, 3));
    }

注意:注意括号中的 (n - 1)。另请注意，当 n == 0 时，我们返回 1，因为任何数字的 0 次方都是 1。

此外，您最好不要静态调用该方法(从技术上讲，这是“草率编程”)。

您最好将类实例化为对象并以这种方式调用方法。