小さな例での再帰の理解

Question

こんにちは私はこのような小さな再帰的な方法をcppに書いています。私は再帰を理解しようとしています

void print(int n) 
{ 
    if(n==6) 
     return; 

    print(++n); 
    cout<<n<<endl; 
    //output is 6 5 4 3 2 

} 
void print(int n) 
{ 
    if(n==6) 
     return; 

    print(n+1); 
    cout<<n<<endl; 
    //output is 5 4 3 2 1 

} 

void print(int n) 
{ 
    if(n==6) 
     return; 

    print(n++); 
    cout<<n<<endl; 
    //programme crash 

} 

内部で何が起こっているのか教えてください。

Answer 1

スタック上に関数呼び出しが配置されます。これをプレートのスタックのように考えてください。あなたのコードで "print（x）"が呼び出されるたびに、このプレートのスタックに追加されます。スタックの中かっこに到達するか、return文に当たると、関数はスタックから削除されます。

これらの関数でprint（0）を呼び出すと仮定します。そのような印刷物（0）はスタック上の最初のものです。最後の関数は、print（0）を "永遠に"呼び出すので、それ以上の "板"の余地がないとクラッシュします。これは無限再帰と呼ばれ、無限再帰はスタックの制限のため無限になることはめったにありません。

他の関数については、 "cout"ステートメントは "after"関数がスタックから削除された場合にのみ呼び出されます。これらのメソッドのそれぞれは、print（6）呼び出しを例外としてスタック上に新しいものを配置し続けます。これはしばしば基本ケースと呼ばれ、再帰的プロセスの終わりです。これはスタックからのプレートのカスケード除去を開始するため、すべてのcoutステートメントを実行できます（無限回帰ケースとは異なります）。

これらのコードがどのように異なるかを理解するには、n ++、++ n、n + 1の違いを理解しておく必要があります。

Answer 2

これは、式の評価に問題があるほど再帰的に問題はありません。 nが6に達すると停止する3つのルーチンがあります。さもなければ、彼らは異なった表現で増分と再発の何らかの形をします。再帰呼び出しの後、ローカル値nを出力し、呼び出し元に戻ります。

プリントを呼び出すたびに、新しいローカル変数スペースをランタイムスタックに追加することに注意してください。これらのそれぞれにはnという独自のコピーがあります.1つ増分してもそれ以外は変わりません。

• ++ NインクリメントNのローカル値と再度関数を呼び出します。
• n + 1ローカルコピーnを変更しないでくださいが、次に高い値で再度関数を呼び出します。
• ++ NNの現在値で再度関数を呼び出します。返されるとすぐに、ローカル値nをインクリメントしてから印刷してください。

Answer 3

時には、コールシーケンスを試して説明するのに役立ちます。

関数f1から関数f7のシーケンスを想像してください。ここで、f1はf2を呼び出し、f3はf3を呼び出すなどしてf7を呼び出します。：だからF1によって開始呼び出しシーケンスは、（0）、として示されるかもしれない（と他のは非常に似ています）

void f1(int n) 
{ 
    if(n==6) 
     return; 
    f2(++n); 
    std::cout<<n<<std::endl; 
} 

：（Iは0で開始するので、ない1）

F1は次のようになりますただNUMを交換、再帰を使用して移動するために、今すぐ

          // no cout of 7 
            return to f6(6) 
            cout<<... n is 6 
          return to f5(5) 
          cout<<... n is 5 
        return to f4(4) 
        cout<<... n is 4 
       return to f3(3) 
       cout<<... n is 3 
     return to f2(2) 
     cout<<... n is 2 
return to f1(1) 
cout<<... n is 1 

：

f1(0)--v    : because f2 is called with ++n 
     f2(1)--v   : because f3 is called with ++n etc. 
       f3(2)--v 
        f4(3)--v 
          f5(4)--v 
            f6(5)--v 
              f7(6) 

そして、すべての関数呼び出し

はリターンを持っていますFOO

void foo(int n) 
{ 
    if(n==6) 
     return; 
    foo(++n); 
    std::cout<<n<<std::endl; 
} 

と呼び出しシーケンスを持つbered Fさん（fooで開始した（0））私は最初の部分の再帰を呼び出す

foo(0)--v    -- given 0, calls foo with 1 
     foo(1)--v    -- give 1, calls foo with 2 
       foo(2)--v    -- etc 
         foo(3)--v 
           foo(4)--v 
             foo(5)--v 
               foo(6) - return 

のように見えるかもしれません^^^^^^^^^^^ ^^^^^^^^^^^^^

         return to foo(6) (was 5) 
             cout<<... n is 6 
           return to foo(5) (was 4) 
           cout<<... n is 5 
         return to foo(4) (was 3) 
         cout<<... n is 4 
       return to foo(3) (was 2) 
       cout<<... n is 3 
     return to foo(2) (was 1) 
     cout<<... n is 2 
return to foo(1) (was 0) 
cout<<... n is 1 

第2の部分は、すべてのこれらの機能のリターンは、この特定のスタック用の「崩壊」は、私は時々「decursion」として注意（A古い軍事用語の新しい使用）。

coutが再帰呼び出しの後にあるため（つまり、デカッションで）、再帰呼び出し中に入力 'n'が増加しても出力シーケンスは減少しています。

行あたりしたがって、この特定の配列COUTの1桁：

6 
5 
4 
3 
2 
1 

アップデート - なぜ最後のコードスニップのクラッシュをしましたか？

再帰呼び出し後にポストインクリメントが発生するため、最後のコードスニップがクラッシュします。 foo（0）を呼び出すとfoo（n ++）が呼び出されますが、これは単にfoo（0）を再度呼び出すだけで、n（再び）をインクリメントします。 2回目以降のfoo（）再帰はそれぞれ同じ値0を参照するため、終了条件（n == 6）は決して発生せず、スタックは無限関数呼び出しでオーバーフローします。