递归"Power Of"函数

Question

我们被分配解决一个递归函数，该函数可以使用以下规则计算数字的幂（拍了快照）：

http://i.imgur.com/sRoQJ1j.png

过去 4 小时我一直在尝试，我似乎无法弄清楚如何做到这一点。我的尝试：

public static double power(double x, int n) {   
    if(n == 0) {
        return 1;
    }
    //    x^n = ( x^n/2 )^ 2  if n > 0 and n is even
    if(n % 2 == 0) {
        double value = ((x * power(x, n/2)) * x);
        return value;
    } else {
        double value = x * ((x * power(x, n/2)) * x);
        return value;       
    }
}

我认为当我将 x 与递归函数相乘时我做错了，而我应该乘以 x (power Of = x * x * .... x(n))...

我也可以在这个声明中看到：

 double value = ((x * power(x, n/2)) * x);

这是错误的，因为我不是对值进行平方而是将它与 x 相乘。我想我需要先将它存储在一个变量中，然后执行类似 value * value 的操作来计算最终结果的平方 - 但这只会给我一个巨大的数字。

感谢任何帮助，谢谢。

Answer 1

问题出在这条语句中：

if(n % 2 == 0) {
        double value = ((x * power(x, n/2)) * x);
        return value;

语法上（括号不匹配）和语义上（更深层次的递归，不正确）。

应替换为：

if(n % 2 == 0) {
        double value = power(x*x, n/2);
        return value;

原因是：

x^(2*k) = (x^2)^k

这几乎就是代码中实现的内容。因为我们知道n是偶数，所以有k = n/2，所以上面的等式成立。

同奇数情况：

else {
        double value = x * power(x*x, n/2);
        return value;

这是因为：

x^(2*k+1) = x*x^(2*k) (version of @rgettman)

加上k = (n-1)/2，可以进一步优化为：

x^(2*k+1) = x*x^(2*k)=x*(x^2)^k (our version)

您可以进一步优化为：

public static double power(double x, int n) {   
    if(n == 0) {
        return 1;
    }
    double xb = x*x;
    if((n&0x01) == 0x00) {
        return power(xb,n>>>0x01);
    } else {
        return x*power(xb,n>>>0x01);
    }
}

或者，您可以将递归方面转换为 while 算法（因为它主要是 尾递归:

public static double power(double x, int n) {
    double s = 1.0d;
    while(n != 0) {
        if((n&0x01) != 0x00) {
            s *= x;
        }
        n >>>= 0x01;
        x *= x;
    }
    return s;
}

性能:

实现了三个不同的版本。 jdoodle 显示基准测试。有：

power1 @rgettman 的版本；
power2 这个答案中提出的递归版本；和
power3非递归版本。

如果将 L 设置为 10'000'000（从而计算 all 从 0 到 L 的功率，一个运行结果：

           L = 10M           L=20M
power1: 1s 630 018 699     3s 276 492 791
power2: 1s 396 461 817     2s 944 427 704
power3: 0s 803 645 986     2s 453 738 241

不要把逗号后面的数字当回事。尽管 Java 以纳秒为单位进行测量，但这些数字非常不准确并且与附带事件（如 OS 调用、缓存故障等）的关系比与真实程序的关系更大运行时间。

Answer 2

在您的 "even" 情况下，您可以使用递归调用计算它，并像您所做的那样传递 n/2。但是你需要将结果乘以它自己的平方。

double value = power(x, n/2);
value *= value;
return value;

在您的 "odd" 情况下，您可以将 x 乘以指数减去 1 的递归调用。

double value = x * (power(x, n - 1));
return value;

Answer 3

您需要了解递归在内部是如何工作的。逻辑很简单就是将函数调用和returned 值存储在堆栈中。当达到方法终止条件时，从方法中弹出值和 return。

你只需要这个：

public static double power(double x, int n) {   
    if(n == 0) {
        return 1;
    } else {
        double value = (x * power(x, (n-1)));
        return value;
    }
}

递归"Power Of"函数

Recursive "Power Of" function

java

recursion