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

Question

我正在尝试创建一个函数来计算 x 的 n 次方(其中 x 可以是 double ，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);
}