C语言递归实现X的N次幂函数输出错误结果原因排查

你的代码存在4个核心问题，小数值输入能得到正确结果只是巧合：

• 递归求幂的逻辑本质错误：你写的return x*power(x, n*0.5)不符合分治求幂的运算规则。正确的递归折半求幂逻辑为：指数为偶数时，xⁿ = (x^(n/2))²；指数为奇数时，xⁿ = x * (x^{(n/2))²。你的写法每次递归仅乘一次底数，没有对递归返回的半值做平方运算，只要指数不是2的整数次幂，结果从根上就是错的。比如计算2}3时，你的代码会返回4，和正确结果8相差一倍。你测试x=3、n=2能得到9，只是因为2是2的整数次幂，计算路径刚好凑对了结果。
• 整数溢出触发未定义行为：32位int类型的取值范围仅为-2147483648~2147483647，362^123是一个远超这个范围的极大值，运算过程中一旦超出int的存储上限就会触发有符号整数溢出，这是C语言标准定义的未定义行为，输出负数是最常见的溢出现象。
• 浮点数隐式转换存在隐患：你用n*0.5计算指数折半值，0.5是双精度浮点数，运算结果为浮点类型，传入形参int n时会直接截断小数部分，不仅和整数除法n/2的逻辑不匹配，当指数值极大时还可能因为浮点数精度损失，导致传入的递归参数错误。
• 边界场景无兼容处理：代码仅设置了n=0的递归终止条件，如果用户输入负指数，代码会进入无限递归，最终触发栈溢出崩溃。

如果要坚持仅用乘法、递归实现幂运算，可以参考以下写法，注意内置整数类型能存储的幂运算结果范围非常有限：

#include <stdio.h>

// 如需计算更大范围的结果，可将返回值替换为long long，或实现专门的大数运算结构
long long power(int x, int n)
{
    if (n == 0) return 1;
    long long half_res = power(x, n / 2); // 用整数除法折半，完全避免浮点数误差
    if (n % 2 == 0) {
        return half_res * half_res;
    } else {
        return (long long)x * half_res * half_res;
    }
}

int main()
{
    int x, n;
    printf("Enter base and exponent:\n");
    scanf("%d%d", &x, &n);
    printf("%lld\n", power(x, n));
    return 0;
}

注：即使用64位long long类型（最大可存储约9e18的整数），也只能支持指数很小的幂运算，类似362^123量级的结果必须通过自定义大数运算才能正确输出，用C语言内置整数类型必然溢出。

内容的提问来源于stack exchange，提问作者Alfa Hores