（1）使用伪码写出递归算法来求解a的n次方（a为某一常数）； （2）列出该递归算法的递推关系式； （3）使用替换法和迭代两种方法分别计算递推表达式的渐进表达式。

（1）使用伪代码表示递归算法来求解a的n次方（假设a为非零整数）：

function power(a, n):
    if n == 0:        # 基本情况，任何数的0次方都是1
        return 1
    else if n is odd:  # 如果n是奇数，则 a^(n-1) * a
        return a * power(a, n - 1)
    else:            # 如果n是偶数，则 (a^k)^2 = a^(2k)
        return power(a, n / 2) * power(a, n / 2)

（2）该递归算法的递推关系式可以表述为：
如果n是奇数，\( P(n) = a \times P(n-1) \)，其中P(n)表示a的n次方。
如果n是偶数，\( P(n) = P(\frac{n}{2}) \times P(\frac{n}{2}) \)。

（3）对于替换法（也称主定理），若递推关系满足 \( P(n) = T(n) + cP(n/k) \)，且 \( T(n) \) 是一个关于n的多项式函数，c是一个常数，k是大于1的正整数，那么\( P(n) \) 的渐近表达式通常取决于 \( T(n) \)。对于上述情况，\( T(n) = a^n \)，所以 \( P(n) = O(a^n) \)。

对于迭代法，我们可以将其转化为循环结构来避免递归带来的栈空间消耗。首先初始化一个变量res为1，然后使用while循环，每次将res乘以a并更新n，直到n减到0为止。此时的迭代版本不会有渐进表达式的明显改变，依然是 \( O(n) \)，因为需要n次乘法操作。