c - 创建自己的幂函数的程序运行时错误

Question

好的，所以我正在阅读程序以创建您自己的幂函数(Write a C program to calculate pow(x,n))

我读到它是使用此函数计算功率的第一种方法:

int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);

}

我了解了这个程序的概念，它给出了正确的结果。

现在，这里写了 power(x, y/2)*power(x, y/2) 所以我们只是计算 power(x,y/2) 的平方)。所以，如果我的 power() 函数是正确的，那么我可以将它更改为 power(power(x,y/2),2) 。也就是说，我们只是在计算 power(x,y/2) 的平方。

所以，当我将我的程序更改为:

int power(int x, unsigned int y)
{
    if( y == 0)
        return 1;
    else if (y%2 == 0)
        return power(power(x, y/2),2);   // Square of power(x,y/2)
    else
        return x*power(power(x, y/2),2);   // x*Square of power(x,y/2)

}
int main()
{
    int x = 2;
    unsigned int y = 3;

    printf("%d\n", power(x, y));
    return 0;
}

上述程序给出了运行时错误。

我无法弄清楚运行时错误的可能原因是什么。谁能帮帮我？

Answer 1

您正在从内部调用函数 power，将 2 作为第二个参数传递。

这本质上是一个无限递归，最终导致堆栈溢出。

---

如果您的输入参数是非负整数，那么您可以按如下方式实现它:

递归:

unsigned long long power(unsigned long long x,unsigned int y)
{
    if (y == 0)
        return 1;
    return power(x,y/2)*power(x,y-y/2);
}

迭代:

unsigned long long power(unsigned long long x,unsigned int y)
{
    unsigned long long res = 1;
    while (y--)
        res *= x;
    return res;
}

高效:

unsigned long long power(unsigned long long x,unsigned int y)
{
    unsigned long long res = 1;
    while (y > 0)
    {
        if (y & 1)
            res *= x;
        y >>= 1;
        x *= x;
    }
    return res;
}