将模指数运算算法修改为递归算法，并计算递归与非递归算法的复杂度

将模指数运算（也称为快速幂算法，Fast Exponentiation）转化为递归算法，我们通常会利用指数运算的性质：\( a^{b \mod m} = (a^{\frac{b}{m}})^{b \mod m} \)。这个过程可以分为两个部分：首先对指数 \( b \) 进行取模，然后对底数 \( a \) 进行递归计算。

**非递归版本（迭代法）**：

int fastModPow(int base, int exponent, int modulus) {
    if (exponent == 0) return 1;
    int result = 1;
    while (exponent > 0) {
        if (exponent % 2 != 0)
            result = (result * base) % modulus;
        base = (base * base) % modulus;
        exponent /= 2;
    }
    return result;
}

**递归版本**：

int recursiveModPow(int base, int exponent, int modulus) {
    if (exponent == 0) return 1;
    else if (exponent % 2 == 0)
        return recursiveModPow(base * base % modulus, exponent / 2, modulus);
    else
        return base * recursiveModPow(base, exponent - 1, modulus) % modulus;
}

**时间复杂度分析**：
对于非递归版本，每次循环都会将 \( exponent \) 减半，因此它的时间复杂度是 \( O(\log_2{b}) \)，其中 \( b \) 是 \( exponent \) 的值。

递归版本同样如此，但由于函数调用栈的存在，它的空间复杂度是 \( O(\log_2{b}) \)，因为每个递归层级对应一次函数调用。尽管如此，由于现代编译器通常会对这种基本情况优化，实际运行时的空间消耗可能会较小。