为什么我在 C 中的递归函数会导致堆栈溢出？

Question

我正在尝试创建一个函数来计算 x 的 n 次方（其中 x 可以是双精度数，n 必须是 int）。递归算法是 this one，但在 C 中实现它给了我堆栈溢出错误。

我试着在这里找到我的答案，但我找到的最接近的是 this，它不能满足我的需要。

这是我的代码：

double power_adapted(double x, int n) {
    if (n == 0)
        return 1;
    else if (n == 1)
        return x;
    else if (n % 2 == 0)
        return power_adapted(power_adapted(x, n / 2), 2);
    else
        return x * power_adapted(power_adapted(x, (n - 1) / 2), 2);
}

Answer 1

递归调用总是将 2 作为 n 传递，因此它们总是会触发另一个递归调用。

我认为您误解了公式。我会将其解释为：

else if (n % 2 == 0) {
    double v = power_adapted(x, n / 2);
    return v * v;
}
else {
    double v = power_adapted(x, (n - 1) / 2);
    return x * (v * v);
}

Answer 2

我认为你试图完成的事情没有意义。

如果你看一下这部分代码，

else if (n % 2 == 0)
    return power_adapted(power_adapted(x, n / 2), 2);
else
    return power_adapted(power_adapted(x, (n - 1) / 2), 2);

虽然嵌套调用可能没有问题（作为声明），但外部调用总是 n = 2 并且基本情况取决于 n.

解决问题：

通过查看提供的公式，我认为您应该有一个从 n == 2 到 return x * x 的基本情况（这是对算法最简单的更改）。因此，该算法可以表述如下：

double power_adapted(double x, int n) {
    if (n == 0)
        return 1;
    else if (n == 1)
        return x;
    else if (n == 2)
        return x * x;
    else if (n % 2 == 0)
        return power_adapted(power_adapted(x, n / 2), 2);
    else
        return x * power_adapted(power_adapted(x, (n - 1) / 2), 2);
}

为什么我在 C 中的递归函数会导致堆栈溢出？

Why does my recursive function in C cause a stack overflow?

c

stack-overflow

recursion

function

解决问题：