再帰関数の実行時間がかかります

Question

私のコードをプロファイリングしたところ、私のプログラムはこの特定の再帰関数を実行する時間の約85％を費やしていました。関数は、初期位置（x、y）が与えられたときに、マルコフ連鎖内の状態集合に達する確率を計算することを目的としています。

private static boolean condition(int n){ 
    int i = 0; 
    while (n >= i){ 
     if(n == i*4 || n == (i*4 - 1)) 
      return true; 
      i++; 
     } 
    return false; 
} 

public static double recursiveVal(int x, int y, double A, double B){ 

    if(x> 6 && (x- 2 >= y)){ return 1;} 
    if(y> 6 && (y- 2 >= x)){ return 0;} 
    if(x> 5 && y> 5 && x== y){ return (A*(1-B)/(1 -(A*B) - ((1-A)*(1-B))));} 

    if(condition(x+ y)){ 
     return (recursiveVal(x+1, y,A,B)*A + recursiveVal(x, y+1,A,B)*(1-A)); 
    } 
    else{ 
     return (recursiveVal(x+1, y,A,B)*(1-B) + recursiveVal(x,y+1,A,B)*B); 
    } 
} 

再帰関数の99％がwhileループに置き換えられる可能性があると言われました。私はこれを行うには問題があります。誰でも実行時間を改善したり、これを反復ループとして書き直す方法を知っていますか？

おかげ

Answer 1

あなたは基本的には、再帰呼び出しのために以前に計算結果をキャッシュメモ化と呼ばれる技術を使用することを試みることができます。

• Wikipedia article on memoization。

補足として、コードの再フォーマットをお勧めします。ここにyoruコードの簡略版があります。

private static boolean condition(int n){ 
    for (int i = 0; i <= n; i++) 
     if(n == i*4 || n == (i * 4 - 1)) 
      return true; 
    return false; 
} 

public static double recursiveVal(int x, int y, double A, double B){ 

    if (x > 6 && (x - 2 >= y)) 
     return 1; 

    if (y > 6 && (y - 2 >= x)) 
     return 0; 

    if(x > 5 && y > 5 && x == y) 
     return A*(1-B)/(1 -(A*B) - ((1-A)*(1-B))); 

    double val1 = recursiveVal(x+1, y, A, B); 
    double val2 = recursiveVal(x, y+1, A, B); 

    return condition(x + y) 
     ? A * val1 + val2 * (1-A) 
     : (1-B) * val1 + B * val2; 
} 

Answer 2

あなたが2つ（離散）変数に関数を計算していることに注意し、繰り返しのフォームにこれを変換するには。テーブルを使用して関数の値を格納し、特定の順序でテーブルを埋めることができます。これにより、必要な値を必要な時に計算しておくことができます。 （この場合、より高い値のxおよびyから）。この場合

、（元の再帰における塩基ケースに相当する）境界の場合は、次のとおり

f(7, y..5), f(8, 6) 
f(x..5, 7), f(6, 8) 
f(7, 7) 

その後、我々はf(7, 6)とf(6, 7)に記入し、「下方に」進む - すなわち F（6 f（x、5）... f（x、y）、f（x、y）、f（x、y） ）。

関数呼び出し構文のように見えるのは、テーブル参照（実際は配列構文に変換される）に相当します。

Answer 3

あなたは次のように手順があり、反復1に再帰関数をリファクタリングする場合：

1）再帰のベースケースを決定します。ベースケースに達すると、再帰が終了します。すべての再帰には、基本ケースが定義されている必要があります。さらに、各再帰呼び出しは、基本ケースに向かって進展する必要があります（そうでなければ、再帰呼び出しは無限に実行されます）。
2）ベ​​ースケースに達するまで反復するループを実装します。
3）ベースケースに向かって進んでください。再帰的なメソッドの代わりにループの先頭に新しい引数を送信します。この方法は、「n」は4またはN + 1の倍数であるかどうかを判断しようとしている

Answer 4

、それが何をしているかを理解しようとすると、コードが速く/簡単にすることができる方法の例...

されます4の倍数。これはもっと短く書くことができます。

private static boolean condition(int n){ 
    return (n+1) & 3 <= 1; 
}