算法实验:给定整数x和n,C语言用递归求x的n次幂 mod 1003

在C语言中，我们可以使用递归的方式来计算一个整数x的n次方，并对结果取模1003。下面是一个简单的递归函数示例：

#include <stdio.h>

// 定义递归函数，计算x^n mod 1003
int powerMod(int x, int n, int modulo) {
    if (n == 0) // 基本情况：0次幂等于1，对mod取余操作结果不变
        return 1;
    else if (n % 2 == 0) // 如果n是偶数，递归地将x平方并缩小n的一半
        return (powerMod(x, n / 2, modulo) * powerMod(x, n / 2, modulo)) % modulo;
    else // 如果n是奇数，先乘以x再递归地计算n-1次幂
        return (x * powerMod(x, n - 1, modulo)) % modulo;
}

int main() {
    int x = 2; // 要计算的底数
    int n = 5; // 次幂
    int modulo = 1003; // 取模值

    printf("(%d)^%d mod 1003 = %d\n", x, n, powerMod(x, n, modulo));
    return 0;
}

这个程序首先检查基本情况（n为0），然后处理奇数和偶数的情况。对于偶数n，它会将问题简化为求x^(n/2)两次的结果；对于奇数n，它先乘以x，然后再递归计算(n-1)次幂。