関数は再帰後にアクションをどのように実行できますか？

Question

私は、再帰は関数自体の中で関数を呼び出す手法であることを知っています。 しかし、以下のコードは、最初の再帰後cout一部を行うことができ、どのように私を混乱させる：

（このコードは、ハノイのパズルの塔を解く）

#include <iostream> 
using namespace std; 

void move_rings(int n, int src, int dest, int other); 

int main(void) 
{ 
    int rings;      
    cout << "Number of Rings: "; 
    cin >> rings; 
    move_rings(rings, 1, 3, 2); 

    system("PAUSE"); 
} 

void move_rings(int rings, int source, int destination, int other) 
{ 
    if (rings == 1) 
    { 
     cout << "Move from " << source << " to " << destination << endl; 
    } 
    else  
    { 
     move_rings(rings - 1, source, other, destination); 
     cout << "Move from " << source << " to " << destination << endl; 
     move_rings(rings - 1, other, destination, source); 
    } 
} 

機能、あなたが見ることができるようにmove_ringsはifステートメントの後に自身を呼び出します。

私はこれを視覚化すると、私は決して終わることのないループを参照してください。この関数は

cout << "Move from " << source << " to " << destination << endl; 

一部を行うことをするために...どのようにそれは可能でしょうか？

は、プログラムの出力は以下です：

Move from 1 to 3 
Move from 1 to 2 
Move from 3 to 2 
Move from 1 to 3 
Move from 2 to 1 
Move from 2 to 3 
Move from 1 to 3 

Answer 1

再帰は最初に把握するのが少し難しいかもしれません。ベースケースこれは、再帰関数でなく、がもう自分自身を呼び出すための条件であり、もう1つの部分（ "else "）、関数が呼び出され続けます。 "rings == 1"の条件が基本ケースです。

関数 "move_rings"は毎回小さい引数で呼び出されます。後続の各呼び出しで、 "rings == 1"が真になるまで、変数 "rings"は小さくなり（したがって、基底のケースに近づく）、関数は自身を呼び出すことを停止します。

希望に役立ちます。

Answer 2

たびに関数再帰、それが最終的に1ずつ減少リング・カウントを取得し、すべての枝がrings==1状態に達すると終了します。これは、else状態の枝とif状態の枝を持つ2分木として想像することができます。

Answer 3

move_ringsを呼び出すたびに、パラメータrings - 1が渡されるためです。最後に、渡されたパラメータは1となり、rings == 1は真となります。

再帰的（または任意の種類のリエントラント）関数を扱う場合、ローカル変数の仕組みを理解することが重要です。関数を呼び出すたびに、ローカル変数とパラメータを独自にインカネーションします。煉瓦のスタック（ハノイの塔にある杭のようなもの）を想像してください。各ブリックには関数パラメータが含まれています。関数が呼び出されると、最上位のレンガの値を使用して、その関数のパラメータがスタックの最上部に配置され、関数が実行されます。関数が戻ると、一番上のレンガは破棄され、下のレンガの値に戻ります。

Answer 4

elseブランチでは、rings - 1でコールが行われます。あなたがそれを増やさないので、最終的にringsは1となり、ifブランチがヒットします。この分岐で再帰が発生しないので、このメソッドは終了します。

Answer 5

​​が呼び出されるたびに、最初の引数が小さくなるためです。最終的に、無限の数のリングを仮定すると、関数は1つのリングでのみ呼び出されます。これは再帰を返す終了条件です。

これはバイナリツリー構造のようです。無限の数のノードを仮定すると、最終的にそれ以上ノードが存在しない葉ノードに到達します。次に、リーフノードを見つけた他のコードパスと共に、スタックのトラバースを開始することができます。

Answer 6

move_rings関数を呼び出すたびに、リング数が1減らされます。最終的には、リング数は1になります。 しかし、このコードは、うまく書かれていないため、無限ループを生成する可能性があります。リングの数が1より大きくなることはありません。したがって、メイン関数に入力された呼び出し回数が1未満の場合、再帰を停止する条件には決して達しません。

Answer 7

move_ringsがmove_ringsを呼び出すと、関数の2番目の呼び出しが完全に新しく開始します。それは完全に別々の変数セットを持っています。他の機能と同じようにmove_ringsと呼ばれます。それはちょうど同じ名前を持ち、同じロジックを含む "別の関数"と呼ばれることがあります。

関数の2回目の呼び出しでは、最初の呼び出しがそのパラメーターの値よりも小さい値を渡したため、ringsの値は低くなります。最終的には、これらの再帰呼び出しの1つで、値は1になり、関数の先頭にあるifテストは真となります。これにより、さらに再帰が回避され、その関数が戻ります。直前の関数の呼び出しは、まるでほかの関数を呼び出したかのように、元の場所から再開します。それは印刷を行い、同様のことが起きた後、再帰呼び出しを行い、完了します。そして、すべての方法で "バックアップ"。