C++请使用 2 种方法,求解 xn。 (1)利用传统递归法求解该问题。 (2)使用二分法思想,结合递归方法求解该问题

在C++中，我们可以使用两种方法求解 \(x^n\) 的问题：

1. **递归法**:
递归是一种通过函数自身调用解决问题的方法。对于 \(x^n\) 的递归求解，我们可以创建一个名为 `power` 的函数，它会检查基本情况（当 n 为0时，结果是1），然后将问题分解成两部分：\(x^{n/2} \times x^{n/2}\)，如果 n 是偶数；或者 \(x \times x^{(n-1)/2}\)，如果 n 是奇数。

   long long power(int x, int n) {
     if (n == 0)
       return 1;
     else if (n % 2 == 0)
       return power(x, n / 2) * power(x, n / 2);
     else
       return x * power(x, (n - 1) / 2);
   }

2. **二分法结合递归（迭代）法**:
这种方法通常用于计算大整数幂，因为递归可能会导致栈溢出。我们可以在循环中逐步将指数除以2，并使用乘方运算来更新结果。这种方法不是真正意义上的二分法，但确实体现了二分的思想——每次减半处理。

   long long power(int x, int n) {
     long long result = 1;
     while (n > 0) {
       // 如果指数是奇数，则加上原数
       if (n & 1) {
         result *= x;
       }
       // 将原数自乘并减半指数
       x *= x;
       n >>= 1; // 右移操作符相当于除以2
     }
     return result;
   }