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

(1) 使用伪代码来表示计算a的n次方的递归算法如下：

function power(base a, exponent n):
   if n == 0:
       return 1   // a^0 = 1 (递归的基本情况)
   else if n is odd:
       return a * power(a, n - 1) // 如果指数是奇数，a^n = a * a^(n-1)
   else:
       return power(a, n / 2) * power(a, n / 2) // 如果指数是偶数，a^n = (a^(n/2))^2

(2) 递归算法的递推关系式可以用下面的形式表示：

对于任意正整数n，如果存在基本情况f(0) = 1，那么对于n > 0，有：
f(n) = a * f(n - 1)/2)^2，当n是偶数
f(n) = a * f(n - 1)，当n是奇数

(3) 替换法计算递推表达式的渐进表达式通常涉及到数学归纳法。对于上述公式，我们可以发现当n足够大时，递归会趋向于O(log n)，因为每次递归都会减半。所以渐进表达式为 O(log a * n)。

迭代法则是避免直接递归的方式，通过循环实现。例如，使用一个while循环，初始值为1，然后不断乘以base，直到达到n次。迭代版本的渐进表达式同样是 O(n)，因为它需要做n次乘法操作。