C++请使用 2 种方法，用户输入数据，求解 x n。 （1）利用传统递归法求解该问题。 （2）使用二分法思想，结合递归方法求解该问题。

(1) 递归法求解 x^n：

#include <iostream>
using namespace std;

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

int main() {
    double x;
    int n;
    cout << "请输入一个数 x 和一个整数 n，计算 x 的 n 次方：" << endl;
    cin >> x >> n;
    cout << x << " 的 " << n << " 次方是：" << power(x, n) << endl;
    return 0;
}

(2) 使用二分法思想，结合递归方法求解 x^n：

#include <iostream>
using namespace std;

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

int main() {
    double x;
    int n;
    cout << "请输入一个数 x 和一个整数 n，计算 x 的 n 次方：" << endl;
    cin >> x >> n;
    double ans = power(x, abs(n));
    if (n < 0) ans = 1 / ans;
    cout << x << " 的 " << n << " 次方是：" << ans << endl;
    return 0;
}

两种方法的时间复杂度都是 O(log n)。