java - 二进制幂错误

Question

给定整数 n 和 k，求 n^k 的值。我尝试递归地执行此操作，但我不明白我哪里出错了。有人可以帮忙吗？

  int binaryPower(int n, int k) {

     if (k == 0) {
       return 1;
     }
     if (k % 2 == 0) {
       return binaryPower(n * n, k / 2);
         }
     return binaryPower(n, k - 1);
     }

Answer 1

错误出现在n % 2 != 0的情况下。在这里，您必须返回 binaryPower(n, k - 1) * n;，但您返回 binaryPower(n, k - 1);。

目前，如果我们以3³为例。
3³ -> 3² -> 9¹ -> 9⁰ -> 1

应该是:
3³ -> 3² * 3-> 9¹ *3 -> 9⁰ * 3 * 9 -> 27

更改的代码:

int binaryPower(int n, int k) {

     if (k == 0) {
         return 1;
     }

     if (k % 2 == 0) {
         return binaryPower(n * n, k / 2);
     }

     return binaryPower(n, k - 1) * n;  // Changed
 }