13

私はしばらくの間アルゴリズムに触れていませんでしたが、最近、自分の概念を修正し始めています。驚いたことに、自分の再帰スキルについて最後に覚えているのは、得意だったのに今は得意ではないということでした。だから、私はあなたたちに私を混乱させている基本的な質問があります. 最初に以下のコードを見てください..

private void mergesort(int low, int high) {
    if (low < high) {
        int middle = (low + high)/2 ;
        System.out .println ("Before the 1st Call");
        mergesort(low, middle);
        System.out .println ("After the 1st Call");
        mergesort(middle+1, high);
        System.out .println ("After the 2nd Call");
        merge(low, middle, high);
    }
}

関数呼び出し

mergesort(0,7);

そして、出力は

最初の電話の前に

最初の電話の前に

最初の電話の前に

最初の電話の後

2回目の電話の後

最初の電話の後

最初の電話の前に

最初の電話の後

2回目の電話の後

2回目の電話の後

最初の電話の後

最初の電話の前に

最初の電話の前に

最初の電話の後

2回目の電話の後

最初の電話の後

最初の電話の前に

最初の電話の後

2回目の電話の後

2回目の電話の後

2回目の電話の後

上記のコードと結果で混乱しているのは、2 番目の再帰呼び出しです。4 行目の出力行 (つまり、1st Call の後) までの流れを理解しています。しかし、なぜそれが（2回目の呼び出しの後）（1回目の呼び出しの後）の後に出力されるのか理解できません。コードから理解していることによると、出力後（最初の呼び出しの後）パラメーター（middle + 1、high）を持つmergesort関数を呼び出し、（最初の呼び出しの前に）出力し、mergesortを使用して再帰呼び出しに入る必要があります（低、中）。私は 1 つの再帰呼び出し関数に慣れており、Foreg fibonacci example を理解し、同期しています。

4

9 に答える 9

17

4 行目の出力行では、最初の呼び出しとその後の 2 回の再帰呼び出しから戻っているため、制御がSystem.out .println ("After the 1st Call");

したがって、2 回目の再帰呼び出しの後、条件low < highは false になるため、関数を終了するだけです。次に、制御は 2 回目の再帰呼び出しの直後の行に戻ります。

TIP 再帰を学習するときに私が行っていたことの 1 つは、スタックの深さを追跡し (たとえば、このパラメーターを渡す)、スタックの深さに基づいて出力をインデントすることでした。これは、再帰チェーンのどこにいるかを視覚化するのに役立ち、デバッグを容易にします。

したがって、デバッグ入力は次のようになります。

entered method, low = 0, high = 10
  entered method, low = 0, high = 5
     entered method, low = 0, high = 2
     exiting method, low = 0, high = 2
  exiting method, low = 0, high = 5
exiting method, low = 0, high = 10
于 2012-06-22T14:16:41.647 に答える
5

実行に従ってください...

First call 0,7 --> enters if, middle = 3 (integer division), calls again as (0,3)
Second call 0,3 --> enters if, middle = 1, calls again as (0,1)
Third call 0,1 --> enters if, middle = 0, calls again as (0,0)
Fourth call 0,0 --> does not enter if, back to third call
Third call 0,1 --> calls as middle+1,high which is (1,1)
Fifth call 1,1 --> does not enter if, back to third call
Third call 0,1 --> calls the string you didn't expect

続行できますが、予期しない文字列が実行される場所です。

于 2012-06-22T14:20:19.460 に答える
2

highandの値も出力できますlow。再帰に従う方がはるかに簡単です。

于 2012-06-22T14:18:43.167 に答える
1

次のインデントは再帰に対応しています。

mergesort(0, 7)
    middle=3
    "Before the 1st Call"
    mergesort(0, 3)
        middle=1
        "Before the 1st Call"
        mergesort(0, 1)
            middle=0
            "Before the 1st Call"
            mergesort(0, 0)
                (0 < 0) is false so return
        "After the 1st Call"
        mergesort(1, 1)
            (1 < 1) is false so return
        "After the 2nd Call"

        etc ...
于 2012-06-22T14:35:52.090 に答える
1

4行の出力low=0、middle = 0、high = 1の後、mergesort（middle + 1、high）を呼び出しても何も出力されません（1 <1はfalse）

于 2012-06-22T14:20:59.937 に答える
1

middle変数の値を出力してみてください。

ベスト プラクティスでは、変数出力なしで「関数の前」スタイルのデバッグ メッセージをコーディングしないように指示されています。

于 2012-06-22T14:17:18.767 に答える
0

Eclipse デバッグ ツールに移動します。この手順に従うと、二重再帰のルールが見つかります。それが私がすることです。

于 2017-05-10T03:39:25.927 に答える