pow再帰メソッドの再帰呼び出しを減らすには？

Question

powメソッドの自己実装で再帰呼び出しの量を減らす方法に関する質問がありました。ここに私が書いたものがありますが、これは改善できるのでしょうか？

public static int pow(double a, int b) { 
    boolean isNegative = false; 

    if(b < 0) { 
     isNegative = true; 
    } 

    if(b == 0) { 
     return 1; 
    } 
    else if(b == 1) { 
     return (isNegative ? (1/b) : b); 
    } 

    return (isNegative ? ((1/b) * (1/b) * pow(a, b + 2)) : (b * b * pow(a, b - 2))); 
} 

Answer 1

はい、改善できます。

はそれについてこのように考える：

• bが偶数の場合には、^ B = A ^（B/2）* A ^（B/2）。
• bが奇数の場合、a^b = a ^（b/2）* a ^（b/2）* a（/は整数除算を意味します）。

コード（脳コンパイル、コーヒーなど、まだ中に蹴られていません）：これは、与え

public static double pow(double a, int b) { 
    if (b < 0) 
     return 1/pow(a, -b); 
    if (b == 0) 
     return 1; 
    double halfPow = pow(a, b/2); 
    if (b % 2 == 0) 
     return halfPow * halfPow; 
    else 
     return halfPow * halfPow * a; 
} 

あなたはO（ログb）の（n）のOとは対照的に、再帰呼び出し、中あなたの解決策。

Answer 2

memoizationをご覧ください。

Answer 3

EDIT：基本的に、次の3つの問題持っている：

• コードは動作しません（編集のように、それは今完全にaを無視する）
• コードが
• 複雑すぎますコードはあなたが望む以上に再帰しています

最初のものを修正せずにこれらの3つを修正しようとすると無意味です。

あなたの最初のコールポートは、いくつかの単体テストでなければなりません。彼らはあなたのコードが現在壊れていることを非常に迅速に証明し、あなたがそれを修正したら、それを変更して、何かを壊したかどうかを知ることができるという確信を与えます。

次に、簡単にすることを目指すべきです。たとえば、あなたが簡単にあなたの方法を始めることができ：

if (b < 0) 
{ 
    return 1/pow(a, -b); 
} 

...あなたは、それ以上bの負の値を心配する必要はありません。

最後にを残しておき、再帰的ソリューションを反復的解決に変えることができます。