用c++的方式请使用 2 种方法，求解 x n。 （1）利用传统递归法求解该问题。 （2）使用二分法思想，结合递归方法求解该问题

1. 利用传统递归法求解 x^n

#include <iostream>

using namespace std;

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

int main() {
    double x = 2;
    int n = 10;
    cout << pow(x, n) << endl;
    return 0;
}

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

#include <iostream>

using namespace std;

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

int main() {
    double x = 2;
    int n = 10;
    cout << pow(x, n) << endl;
    return 0;
}

在这里，我们对n的奇偶性进行了判断，如果n为偶数，我们只需要计算一次pow(x, n/2)即可，如果n为奇数，我们需要计算两次pow(x, n/2)，再乘上x。这样就保证了算法的时间复杂度为O(logn)。