2

関数を呼び出すときにパラメーターとして送信せずに、再帰内でインデックス変数を使用したい。ただし、最初にリセットすると (i = 0 など)、実行するたびにリセットされます。カウンターとして使用したい（関数の実行をカウントするため）。

4

5 に答える 5

3

まず第一に、明らかに一度だけ初期化したいでしょう。再帰の一般的なパターンは次のとおりです。

public void run(int opt) {
  run_helper(opt, 0);
}

private void run(int opt, int depth) {
  if (whatever) { run(opt, depth + 1); }
}

外側のメソッドは、初期化以外は何も行いません。

頻繁に提案される「解決策」（たとえば、質問への最初のコメントなど）は、静的変数を使用することです。このアプローチは悪いスタイルであり、マルチスレッドを追加すると、さまざまな奇妙な方法でプログラムが失敗する原因となります (たとえば、UI バージョンを作成したり、マルチスレッド Web サーバーで実行したりするなど)。最悪の場合、最初は機能しているように見えても、多くのユーザーがいる場合にのみ微妙に誤動作し始めることがあります。したがって、定数以外のすべてについて「静的」を避けてください。

「静的」では、一般的に次のようになります。

static int counter;

public void start() {
  counter = 0;
  recurse();
}

public void recurse() {
  counter += 1;
  if (whatever) { recurse(); }
}

ここで、2 人のユーザーがstart同時に呼び出すとします。彼らはお互いのカウンターを上書きします！静的とは、スレッドとユーザー間で共有されることを意味するためです。

これは非常に理解しやすい解決策です：

class MyTask {
  int counter = 0;

  public void recurse() {
    counter++;
    if (whatever) { recurse(); }
  }

  public int getIterations() {
    return counter;
  }
}

public void run() {
  MyTask task = new MyTask();
  task.run();
  System.out.println("Task took "+task.getIterations()+" itertions.");
}

次に、タスクを作成して実行し、最後にカウンターを取得します。クリーンで、非常にシンプルで、効率的で信頼性があります。複数のスレッド/ユーザーがある場合、それぞれに個別の MyTask オブジェクトがあり、問題は発生しません。

さらに、追加の統計を追加することができ、それらはすべてタスク オブジェクトにきれいにラップされます。「反復あたりの平均時間」？「平均再帰深度」？問題ない。タスク オブジェクトを使用して、結果を保存することもできます。

の使用はThreadLocalここで提案されています。私はこれに同意しません。タスク オブジェクトの利点はまったくありません。ThreadLocalと task オブジェクトを使って実装してみるだけで、違いがわかります。さらに、ThreadLocal経験的にヒープ値にアクセスするよりも 10 倍遅くなります ( https://stackoverflow.com/a/4756605/1060350を参照)。それintはおそらくさらに悪いからです。したがって、パフォーマンス クリティカルな codepath を決して呼び出さないでThreadLocal#getください。を使用する場合ThreadLocalは、このコードパスの外で使用し、ローカル変数 (または Task オブジェクト) を使用して、「ローカル静的」変数を重要なコードパスにフィードします。

于 2012-05-12T20:29:13.523 に答える
1

2 つの方法を使用して分離する必要があります。1 つは再帰反復を開始してカウンターをゼロに初期化するための public であり、もう 1 つは再帰呼び出しが行われる場所である非公開です。このようにして、パブリック メソッドを呼び出すたびにカウンターが初期化されます。これは次のようになります (Java の場合):

public class Recursion{
    private int iterations=0;

    private int calcFactorial(int n){
        iterations++;
        if (n==2)
            return 2;
        else
            return n * calcFactorial(n-1);
    }

    public int factorial(int n){
        //initialize the counter
        iterations = 0;
        return calcFactorial(n);
    }

    public int getIterations(){
        return iterations;
    }
}
于 2012-05-12T20:54:29.957 に答える
0

属性を使用できますが、なぜですか？値をパラメータとして渡してみませんか？

public class Empty {

    private int steps = 0;  

    public static void main (String args [])
    {
        Empty e = new Empty ();
        System.out.println (e.reverse ("This is a test"));
        System.out.println ("steps: " + e.steps);
    }

    public String reverse (String s) {
        ++steps;
        if (s.length () < 2) 
            return s;
        else return reverse (s.substring (1)) + s.charAt (0);
    }
}

私が得たコメントから、再帰をいつ終了するかを検出するためのカウンターとして使用します。それはあまり役に立たないようです。list.length（）などのパラメーターから導出できる条件はありませんか？

もちろん、メソッドを2回呼び出すと、カウンターがさらに増えます。2つのスレッドで同時に使用されていない場合はリセットできます。また、内部オブジェクトのラップされたメソッドは、最初にカウンターをリセットせずに呼び出すのを防ぐのに役立つ場合があります。

しかし、それはカウンターを回すよりもはるかに定型的です。

パラメータは、呼び出しをカウントするためのはるかにクリーンなソリューションです。

デバッグ中のスタックオーバーフローを防止したい場合、好奇心をそそる代替手段は、ランダマイザーを呼び出して、10000のケースのうちの1つを返すことです。

于 2012-05-12T21:27:18.803 に答える
0

インデックスが停止条件として使用されることを考えると、単純なパラメーター ベースのアプローチを使用します。JavaScript の実装:

var recurse = function() {
    recurseHelper(0);
};

var recurseHelper = function(iteration) {
    // run for 100 iterations, 
    if (iterationCount > 100)
        return;

    // do stuff...


    recurseHelper(iteration + 1);
}

ただし、関数を特定の回数だけ呼び出したい場合、特に再帰を使用する必要があるのはなぜですか? ループを使用できます。再び JavaScript で:

for (var i = 0; i < 100; i++) {
    // do stuff...
}

コンパイラは、再帰アルゴリズムの複雑さによっては、再帰構造よりもループの巻き戻しの方が楽しい場合があります。

于 2012-05-12T21:04:37.203 に答える
-1

最も自然なことは、特に再帰をいつ停止するかを決定するために使用される場合、投稿で説明したように補助パラメーターを使用することです。メンバー変数に依存している場合は、再帰メソッドを呼び出す前にカウンターをリセットするヘルパー メソッドを用意し、再帰関数を呼び出したいときはいつでもヘルパー メソッドを呼び出すことができます。

単一の方法に固執したい場合は、次のようにする必要があります。

insideMethodデフォルトで false に設定されているというメンバー変数を作成します。メソッドが呼び出されると、この変数が検査されます。false の場合は最初の呼び出しであり、カウンターをリセットする必要があります。それ以外の場合はカウンターをインクリメントする必要があります。その後、insideMethodは true に設定されます。戻るときに、true に設定されたのがこのinsideMethod呼び出しである場合にのみ、false に設定し直す必要があります。

insideMethodインデックス変数を ThreadLocalにすることを忘れないでください。

擬似コード:

ThreadLocal<Boolean> insideMethod = false
ThreadLocal<Integer> index = 0

....

void recMethod(args) {
    boolean topCall = (insideMethod == false)
    insideMethod = true

    if (topCall)
        index = 0
    else
        index++

    // Body of the method...

    if (topCall)
        insideMethod = false
}
于 2012-05-12T20:28:22.873 に答える