遞歸「權力」的功能

Question

我們將得到一個任務，解決了遞歸函數可以使用下面的規則計算數量的功率（拍了快照）：

http://i.imgur.com/sRoQJ1j.png

我似乎無法想象這樣做，因爲我一直在嘗試過去4個小時。 我嘗試：

public static double power(double x, int n) { 
    if(n == 0) { 
     return 1; 
    } 
    // x^n = (x^n/2)^ 2 if n > 0 and n is even 
    if(n % 2 == 0) { 
     double value = ((x * power(x, n/2)) * x); 
     return value; 
    } else { 
     double value = x * ((x * power(x, n/2)) * x); 
     return value;  
    } 
} 

我相信我做錯了，當我乘以X與遞歸函數，而我應該被x乘以（功率= X * X * ......，X（N個）） ...

我也可以看到，在此聲明：

double value = ((x * power(x, n/2)) * x); 

這是錯誤的，因爲我不是平方值只是隨x相乘。我想我需要首先將它存儲在一個變量中，然後做一些類似value *的值來平衡最終結果 - 但這只是給了我一個巨大的數字。

任何幫助表示讚賞，謝謝。

Answer 1

問題是，在此聲明：

if(n % 2 == 0) { 
     double value = ((x * power(x, n/2)) * x); 
     return value; 

它既是語法（括號不匹配）的語義（深遞歸，不正確的）。

應該被替換：

if(n % 2 == 0) { 
     double value = power(x*x, n/2); 
     return value; 

其原因在於：

的x ^（2 * K）=（X^2）^ķ

哪幾乎是字面上代碼中實現的內容。因爲我們知道n是偶數，所以有一個k = n/2，這樣上面的等式成立。

與奇數情況下的相同：

else { 
     double value = x * power(x*x, n/2); 
     return value; 

這是因爲：

的x ^（2 * K + 1）= X * X ^（2 * k）的（版本@ rgettman）

k = (n-1)/2隨着，其可以被進一步優化以：

的x ^（2 * K + 1）= X * X ^（2 * K）= X *（X^2）^ K（我們的版本）

可以進一步優化這個爲：

public static double power(double x, int n) { 
    if(n == 0) { 
     return 1; 
    } 
    double xb = x*x; 
    if((n&0x01) == 0x00) { 
     return power(xb,n>>>0x01); 
    } else { 
     return x*power(xb,n>>>0x01); 
    } 
} 

或者，你可以改變遞歸方面爲while算法（因爲它主要是尾遞歸：

public static double power(double x, int n) { 
    double s = 1.0d; 
    while(n != 0) { 
     if((n&0x01) != 0x00) { 
      s *= x; 
     } 
     n >>>= 0x01; 
     x *= x; 
    } 
    return s; 
} 

性能：

實現了三個不同的版本。這jdoodle顯示基準測試。附：

• power1 @rgettman;
• power2在這個答案中提出的遞歸版本;和
• power3非遞歸版本。

如果一個集L到10'000'000（從而計算從0所有功率可達L），在一個運行的結果：

  L = 10M   L=20M 
power1: 1s 630 018 699  3s 276 492 791 
power2: 1s 396 461 817  2s 944 427 704 
power3: 0s 803 645 986  2s 453 738 241 

不要拿數字逗號後很認真。儘管Java在納秒測試中，這些數字是非常不準確的，並且更多地與側事件（如操作系統調用，高速緩存故障等）有關，而不是真正的程序運行時。

Answer 2

在您的「偶數」情況下，您可以使用遞歸調用計算它，並像您那樣通過n/2。但是你需要將結果與自身相乘來平方。

double value = power(x, n/2); 
value *= value; 
return value; 

在你的「奇」的情況下，可以通過指數減去1的遞歸調用乘x。

double value = x * (power(x, n - 1)); 
return value; 

Answer 3

您需要了解遞歸如何在內部工作。邏輯很簡單，就是將函數調用和返回值存儲在堆棧中。當達到方法終止條件時，彈出這些值並從方法返回。

您需要簡單：

public static double power(double x, int n) { 
    if(n == 0) { 
     return 1; 
    } else { 
     double value = (x * power(x, (n-1))); 
     return value; 
    } 
}