哪种递归调用效率最高？

Question

所以我有一个任务是编写一个方法，在递归的帮助下找到 x 的 n 次方。基本情况是如果 n = 0，则 x^n = 1。如果 n 是奇数，则 x^n = x*(x^2)^((n-1)/2)。如果 n 是偶数，则 x^n = (x^2)^(n/2)。不确定您是否需要此信息，但只是添加以防万一。

我的问题是我有两种使用递归调用的方法，但我不确定哪一种是“最佳”或最有效的方法。

方法如下：

public double findNthPowerOfXV2(int n, double x){
        if(n == 0){                                                                                     
            return 1;                                                                                   
        }else if(!(n % 2 == 0)){                                                                        
            return x * findNthPowerOfXV2(((n-1)/2), x) * findNthPowerOfXV2(((n-1)/2), x);               
            //return x * findNthPowerOfXV2(((n-1)/2), x * x) also works, but not sure which is best
        }else{

            return findNthPowerOfXV2(n/2, x) * findNthPowerOfXV2(n/2, x);
            //return findNthPowerOfXV2(n/2, x * x) also works, but not sure which is best
        }
}

被注释掉的代码行，对我来说，看起来更好更正确。当我说被注释掉的行使该方法执行更少的循环时，我不确定我是否错了？但是，当我测试完成该方法所需的时间时，未注释掉的行比注释掉的行要快。即使它有两个递归调用，我猜这会导致更多循环？

这是我用来测试方法时间使用的代码：

Date start2 = new Date();
int rounds2 = 0;
double time2;
Date stop2;
do {
  main.findNthPowerOfXV2(5000, 1.001);
  stop2 = new Date();
  ++rounds2;
}while(stop2.getTime() - start2.getTime() < 1000);
time2 = (double) stop2.getTime() - start2.getTime() / rounds2;
System.out.println(time2);

当我使用未注释掉的行时，我得到 1.597890920672E12 当我使用被注释掉的行时，我得到 1.597915039728E12

那么用哪个更正确呢？我正在寻找关于哪个更好用以及原因的解释。提前致谢:)

Answer 1

你是对的，commented-out 版本原则上更有效。考虑一下我们进行了多少次调用，例如，在计算 2^4.

时

首先是低效版本：

如果我们加倍n，这棵树的大小就会加倍，所以这个算法就是O(n)。另一种查看方式是假设它对递归调用是正确的，然后证明它对碱基调用也是正确的。在这种情况下，我们进行了两次递归调用，每个调用执行 n/2 操作（根据假设），因此碱基调用执行 2 * n/2 = n 操作。

现在是高效版本：

- 2^4
  - 2^2
    - 2^1
      - 2^0

在这里，如果我们 double n 树的值增加 1，所以这是 O(log n).

我会把严格的证明留给reader。在这两种情况下，我都忽略了 n 的奇数值，因为它们在 big-O 方案中无关紧要。

您无法衡量这种差异的事实可能更多地说明了您的基准测试代码：

构造一个 new Date 对象会调用内存管理器，可能会触发垃圾收集器，并且可能会执行系统调用以从操作系统获取当前时间，因此可能需要比您正在测试的实际功能更长。
Java 运行时（我假设这是 Java）使用了一个 just-in-time 编译器，它只在一个函数被多次调用时才启动，所以第一次运行，结果不具有代表性
也许编译器足够聪明，可以识别出该函数是纯函数，并且您正在使用相同的参数进行两次调用，因此它可能不像看起来那样效率低下。

哪种递归调用效率最高？

Which recursive call is the most efficient?

algorithm

recursion

big-o