遞歸計算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) 
}