递归计算x^-n

Question

我对编程相当陌生，并试图想出递归计算x^-n的方法。 （数学和计算递归的x^N之间的差后面的解释，将不胜感激）：

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

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

Answer 1

X ^-n在数学上等于1/X ^ñ，所以你能适应X ^ñ的经典递归运算处理它太：

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); 
} 

Answer 2

x^-n相当于1/(x^n)。只要有像double result = 1.0/power(x,n);的声明，您的调用方法

Answer 3

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; 
} 

注意你的算法不是尾递归。对于tail call optimization它是有用的写类似的东西：

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)。

Answer 4

该过程相当简单。我已经在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.

然后就是反复步骤，将构建问题出这些基地步骤。

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) 

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) 
}