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

方法一：传统递归法

可以使用递归函数来求解 xn，递归函数的基本思路是将问题不断地拆分成更小的子问题，并将子问题的解合并成原问题的解。

C++代码如下：

#include <iostream>
using namespace std;

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

int main() {
    int x, n;
    cout << "请输入底数x和指数n：" << endl;
    cin >> x >> n;
    int ans = pow(x, n);
    cout << x << "的" << n << "次方是：" << ans << endl;
    return 0;
}

方法二：二分法思想结合递归方法

二分法思想可以帮助我们优化递归过程，减少递归次数，从而提高效率。

具体实现思路是：将指数 n 不断除以 2，如果 n 是偶数，则将底数 x 的幂次方缩小一半，变为 x^(n/2) 的平方；如果 n 是奇数，则将底数 x 的幂次方先缩小一半，变为 x^((n-1)/2) 的平方，然后再乘上一个 x。

C++代码如下：

#include <iostream>
using namespace std;

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

int main() {
    int x, n;
    cout << "请输入底数x和指数n：" << endl;
    cin >> x >> n;
    int ans = pow(x, n);
    cout << x << "的" << n << "次方是：" << ans << endl;
    return 0;
}

这两种方法的时间复杂度都是 O(logn)，效率较高。但是需要注意，当指数 n 很大时，使用递归方式可能会导致栈溢出，需要注意优化递归过程。