5

私は現在、関数の再帰がどこでも使用されているいくつかの分割統治アルゴリズムをプログラミングしていますが、それがどのように機能するかが非常に漠然としているか、正確にはわかりません。そのため、ここに投稿し、基本的すぎることを気にしないでください。

たとえば、次のコードがあるとします。

#include<iostream>
using namespace std;
void Recursion(int n)
{
  cout << n << endl;
  if(n > 0)
  {
    Recursion(n-1);
  }
  cout<<n<<endl;
}

int main()
{
  Recursion(3);
  return 0;
}

Recursion(3) をテストしたところ、ターミナルでの出力は次のとおりです。

3
2
1
0
0
1
2
3

関数の再帰呼び出しの概念は理解できますが、その仕組みがわかりません。たとえば、関数を再度呼び出すことができなくなった後、彼らは何をしますか? たとえば、ここでは、3 から 0 に出力されることは理解できますが、0 から 3 に再度出力されるのはなぜですか? 関数再帰は1回の再帰のためにスタックに格納され、「底」に達すると削除する必要があるためだと聞きました。

しかし、とにかく、私はそれについて知りません。それで、誰かが私を助けて、ここで何が起こったのか、関数呼び出しの正確な流れを明確に教えてもらえますか?

ご協力いただきありがとうございます！

4

4 に答える 4

6

再帰を理解する鍵は、コール スタックの概念です。コールスタックは「フレーム」で構成されています。スタック フレームには、関数のローカル変数と非表示の戻りアドレスが含まれています。古典的な物理的なアナロジーは、プレートの積み重ねです。関数呼び出しを行うと、プレート (スタック フレーム) がスタックの一番上に追加されます。機能から戻ると、トップ プレート (スタック フレーム) が取り外されます。上にあるプレート（スタックフレーム）のみ使用できます。

再帰関数は、通常の関数と同じように機能します。特定の時点でローカル変数の複数のインスタンスをスタックに持つことができるため、少し注意が必要です。ただし、他の関数と同様に、関数はスタックの一番上にあるスタック フレームのみを参照します。

これがどのように機能するかを説明するために、呼び出しスタックがどのように拡大および縮小するかを示すプログラムを見てみましょう。

基本ケースから始めましょう: 0.Recursion(0);

  1. メインを入力してください: スタックは空です: スタックの一番下->||<-スタックの一番上
  2. Recursion(0);スタックが成長した再帰を入力してください: スタックの下部->|0|<-スタックの上部
  3. cout << n << endl;n の値が 0 であるため、出力は「0」です。
  4. if (n > 0). 0 は 0 より大きくないため、Recursion(-1) は呼び出されません。
  5. cout << n << endl;n の値が 0 であるため、出力は「0」です。
  6. main() に戻ると、スタックは再び空になります: スタックの下部->||<-スタックの上部

出力は次のようになります

0
0

十分に単純で、再帰は発生しませんでした。次のステップに進みましょう。Recursion(1);

  1. メインを入力してください: スタックの下部->||<-スタックの上部
  2. Recursion(1);再帰を入力してください: スタックの一番下->|1|<-スタックの一番上
  3. cout << n << endl;n の値は 1 なので、出力は「1」です。
  4. if (n > 0). 1 は 0 より大きいのでRecursion(0);、呼ばれます。
  5. 再帰を入力してください: スタックの一番下->|1,0|<-スタックの一番上
  6. cout << n << endl;このスタック フレームの n の値は 0 であるため、出力は「0」です。
  7. if (n > 0). 0 は 0 より大きくないため、関数は再帰しません。
  8. cout << n << endl;n の値が 0 であるため、出力は「0」です。
  9. Recursion の最初の呼び出しに戻ります。スタックの一番下->|1|<-スタックの一番上
  10. cout << n << endl;n の値は 1 なので、出力は「1」です。

出力

1
0
0
1

n == 2 で最後にもう一度実行してみましょう

  1. メインを入力してください: Bottom->||<-Top
  2. Recursion(2);再帰を入力してください: Bottom->|2|<-Top
  3. cout << n << endl;"2"
  4. if (n > 0). 2 は 0 より大きいのでRecursion(1);、呼ばれます。
  5. 再帰を入力してください: Bottom->|2,1|<-Top
  6. cout << n << endl;「1」
  7. if (n > 0). 1 は 0 より大きいのでRecursion(0);、呼ばれます。
  8. 再帰を入力してください: Bottom->|2,1,0|<-Top
  9. cout << n << endl;「0」
  10. if (n > 0). 0 は 0 より大きくないため、関数は再帰しません。
  11. cout << n << endl;「0」
  12. 戻る。下->|2,1|<-上
  13. cout << n << endl;「1」
  14. 戻る。下->|2|<-上
  15. cout << n << endl;"2"
  16. main() に戻ります。下->||<-上

出力

2
1
0
0
1
2
于 2013-07-28T01:32:06.010 に答える
6

そうです、再帰関数もわかりにくいと思います。再帰関数が表示された場合は、次のようにします。すべてのコードを頭の中で段階的に実行します。このアドバイスは些細なことのように思えるかもしれませんが、ほとんどの場合、私にとってはうまくいきます。コードを見てみましょう: パラメータ 3 を指定して Recursion() 関数を呼び出します。n と n>0 が出力されるため、Recursion(2) が呼び出されます (まだ実行中の Recursion(3) 呼び出しから戻っていないことに注意してください)。それと今は Recursion(2) にもあります. recursion(1) と 0 も同じです. n>0 条件は false. 0 を出力し, recursion(0) から戻ります. 1 を出力し, recursion から戻ります. (1) そしてそれは再帰に行きます(3)

Recursion(3)
    Recursion(2)
        Recursion(1)
            Recursion(0)  
            return from Recursion(0)
        return from Recursion(1)
    return from Recursion(2)
return from Recursion(3)
于 2013-07-27T22:43:13.230 に答える
4

自分自身を呼び出す関数は、別の関数を呼び出す関数と違いはありません。先に進む前に、呼び出した関数が戻るのを待つ必要があります。

ところで、再帰は洗練されているように見えるかもしれませんが、一般的に最も効率的なプログラミング方法ではありません。たとえば、関数をインライン化することが不可能になるため、コンテキスト スイッチのオーバーヘッドが保証されます。再帰関数の同じ結果を得るより効率的な方法が常にあります。しかし、いくつかの問題については、再帰的な実装がより直感的であり、それほど遅くはありません。コメントで示したマージソートの例は良い例です。

これに関するいくつかの興味深い議論:
再帰から反復への移行方法
すべての再帰を反復に変換できますか?

私の最後のアドバイスは、たとえば階乗を計算するときなど、問題がこのアプローチを必要としない場合は、再帰的に行かないことです。

于 2013-07-27T22:42:23.560 に答える