递归计算 x 的负幂次方

Question

我对编程还比较新，正在尝试想出一种递归计算x的-n次方的方法。（希望能解释一下数学背后的原理以及与递归计算x的n次方的区别）：

double power(double x, int n)
{
    if (n == 0) 
        return 1.0;

    return x * power(x, n - 1)
} 

- katebeckett

---

可以使用x^-n = (1/x)^n的公式。该公式不会改变原始含义，但可以使语言更加通俗易懂。 - John Coleman

只需记住 x^(-n) = 1 / (x^n)。 - Barranka

x^-n 可以重写为 1/(x)^n，这将与您现有的函数配合使用。 - Shawn Mehan

Answer 1

x的负n次方在数学上等于1/x的n次方，因此你可以改变经典的递归计算x的n次方以处理它：

double power (double x, int n) {
    if (n < 0) {
        return 1.0 / power(x, -1 * n);
    }
    if (n == 0) {
        return 1.0;
    }
    return x * power (x, n - 1);
}

- Mureinik

---

这种算法有一个冗余比较，每次递归调用都会执行。可以使用包装函数来检查n的符号，然后调用递归辅助函数。 - Orest Hera

@OrestHera 或者只需将最常见的情况 if (n > 0) ... 作为第一个比较。 - pjs

你为什么选择“-1 * n”而不是“-n”？ - pjs

@pjs 只是看起来更明确，没有真正的原因。 - Mureinik

如果你想要更高级一点的方法（对于大的n值来说更快），你可以使用重复平方法而不是递归乘法。 - G. Bach

Answer 2

x^-n 相当于 1/(x^n)。在你的调用方法中只需要像这样声明：double result = 1.0/power(x,n);

- F. Stephen Q

Answer 3

这个过程非常简单。我用VB.NET编写了它，因为它就像英语一样容易理解。

Function I(ByVal x As Double, ByVal n As Integer) As Double
    If n = 0 Then
        Return 1
    End If
    Return 1 / x * I(x, n - 1)
End Function

无论何时使用递归编写函数，识别基本情况都是必不可少的。例如，问题可以分解成什么？

这里的基本情况是n = 0时等于1。

然后是递归步骤，它将从这些基本步骤构建问题。

- Shreyas Kapur

Answer 4

x^-n 实际上是 1/(x^n)

因此，您的函数可以重写为

double power_1(double x, unsigned int n)
{
    if (n == 0) 
        return 1.0;

    return power_1(x, n - 1) / x;
}

请注意，您的算法不是尾递归的。为了进行尾调用优化，建议编写类似以下代码：

double power_1(double x, unsigned int n, double res = 1.0)
{
    if (n == 0) 
        return res;

    return power_1(x, n - 1, res / x);
}

最后一个res参数是结果的累加器。对于外部使用，它应该为1.0。结果通过所有递归调用作为函数参数传递。在C中，默认函数参数不受支持，可以将其称为power_1(x, n, 1.0)或在C++中称为power_1(x, n)。

- Orest Hera

Answer 5

这基本上是不断获取未知数，直到达到 n == 0 的情况。一旦到达那里，它就返回 1，这意味着它可以计算出 n == 1 的情况应该返回什么。你可以把它想象成等待返回它的 x * power(x, n - 1)，直到其中一个 x * power(x, n - 1) 行返回了某些东西，这发生在 n == 0 时。从那里开始，它可以计算出 x == 1 的情况，以此类推，直到最终找到最终答案并返回到您的主代码。

这里有来自 3 的图形：

x=3 的情况是什么？ -需要得到 x=2

  ok, what's the case for x=2?
     -need to get x=1 for that

        ok, what's the case for x=1?
          -need to get x=0 for that

             ok, what's the case for x=0?
                -the answer is one1

        ok, then my answer is a bunch of stuff using case x=0's answer (1)

    ok, then my answer is a bunch of stuff using case x=1's answer which uses x=0's answer (1)

  ok, then my answer is a bunch of stuff using case=2's answer which uses x=1's answer, which uses x=1's answer (1)

- Silvertail

Answer 6

正如其他人所说，x^-n 等于 1/x^n。因此，这可能是一个答案：

function power(double x, int n) {
   if (n == 0) 
      return 1.0;

   return 1/ x*power(x, n + 1)
}

- Diego Magdaleno