使用递归分治算法计算整数幂

Question

我已经实现了一个递归函数来查找 m^n（m 的 n 次方）。

现在我想实现相同的功能，但将问题分成两个相等的部分，例如

m^n = m^(n/2) * m^(n/2) = ...（对于偶数 n 个，m^2、m^4、m^6）。

在下面的实现中，如果我给出 m = 2 和 n = 4 ，我的输出是4，而它应该是16。

public class Recursion {

  public static void main(String[] args) {
    System.out.println(pow(2, 4));
  }

  public static long pow(long m,long n) { 
    if (n > 0)
      return m * pow(m, ((n/2) - 1) * pow(m, ((n/2) - 1)));
    else
      return 1;
  }

}

Answer 1

public static long pow(long m,long n)
{ 
    if (n <= 0) {
        return 1; // Be lazy first
    } else if (n % 2 == 1) {
        return m * pow(m, n - 1); // Normal slow strategy
    } else { // n even
        long root = pow(m, n / 2); // Do not evaluate twice
        return root * root;
    }
}