高效求解xn 目的：掌握基本递归算法设计。 内容：编写程序exp5-1.py，采用递归高效求解xn问题，要求最多使用log2n次递归调用。

下面是一个递归高效求解 $x^n$ 的 Python 代码，最多使用 log2n 次递归调用：

def fast_pow(x, n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    elif n % 2 == 0:
        return fast_pow(x * x, n // 2)
    else:
        return x * fast_pow(x * x, (n - 1) // 2)

代码中用到了二分法的思想，将 $x^n$ 分解为 $(x^2)^{\frac{n}{2}}$，这样每次递归调用时，指数都会减半。当指数为偶数时，直接将底数平方并继续递归；当指数为奇数时，先递归计算 $(x^2)^{\frac{n-1}{2}}$，再将其乘以 $x$，即可得到 $x^n$ 的值。这样，递归调用的次数就只有 log2n 次了。