リカーシブ関数で返された結果はどのように計算されますか？

Question

私はリターンの仕組みを理解していたのですが、再帰に入った後は元々考えられていたものより少し失われていると思います。

私はカウントのための関数を持っているとします。これは、文字が文字列内で何回ポップアップするかを示します。

int frequency(char ch, string input, int pos) { 
    if (pos == inputString.length()) { 
     return 0; 
    } 

    if (inputString[pos] == ch) { 
     return 1 + frequency(ch, inputString, pos + 1); 
    } 
    else { 
     return frequency(ch, inputString, pos+1); 
    } 
} 

私は、文字列「ジェフ」、それに合格していたと「F」を探しているなら、それは2の値を返します。

これはどのように停止するのですか？

• 戻り値の型intを持つ任意のメソッドを終了return 0ていますか？

• もしそうなら、なぜそれがまだ最終リターンが0を返すと言うとき、2の値を返すのですか？

Answer 1

最後のリターン

return 0; 

は、関数が再帰中に呼び出される唯一の最後の時間です。これは、ある時点で再帰を停止するために必要です。この前のコールの最後の一つの他のreturn文のいずれかが実行され、例えばの場合：

return 1 + frequency(ch, inputString, pos + 1); 

したがって0は再帰の1と任意の以前の結果に加算されます。

PS： 関数のreturn文が関数を再び呼び出す限り、再帰は続行されます。戻り値が単に何かを返すときにのみ（関数を再度呼び出すことなく）、再帰は停止します。ここで

がNまでのすべての整数の合計を計算し、よりシンプルな例です：

int calcSum(int N){ 

    if (N == 1) return 1;   // recursion stops here 

    return N + calcSum(N-1);  // otherwise continue to add up 

} 

一つの機能に複数のreturn文は、再帰に特別ではありません。この関数は遭遇した最初の戻り値を返します。

Answer 2

再帰呼び出しを関数呼び出しのスタックと考えてください。ある時点でヒットする可能性がありますreturn 0;これは、スタック上の関数呼び出しの1つが完了したことを意味します。スタック上の要素がポップされます。関数のの最後のは、スタックが空のときに戻ります。

Answer 3

どのように停止するのがわかりますか？これ以上の再帰呼び出しは、それが停止します再帰的に呼び出された関数内の特定のブランチから追加されていない、とコールスタックが発行されたコールの逆順（LIFO）の値を返すとクリアされます

。それはここで行われます：

if (pos == inputString.length()) { 
    return 0; 
} 

は、他の支店のいずれかが再帰関数を呼び出すと、呼び出しスタックにダウンステップを取る：

if (inputString[pos] == ch) { 
    return 1 + frequency(ch, inputString, pos + 1); 
      // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
} 
else { 
    return frequency(ch, inputString, pos+1); 
     // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 
} 

• はreturn 0;が戻り型intを持つ任意のメソッドを終了してい？それは0

  • で初期化することができ、もしそうなら、なぜそれはまだ2、確定申告の値を返さない任意の戻り値の型について

  はい、と行います返品は0と言っていますか？

再帰呼び出しの結果の結果がスタック上に蓄積されたため

：

return 1 + frequency(ch, inputString, pos + 1); 
//  ^the result of the operation will be saved on the stack when the call returns 

...そして、あなたはあなたのドライバの機能で（最初の）再帰呼び出しの最終結果を参照してください。

---

ところで、パフォーマンスとメモリの使用によってはるかに安価な実装は、単純なループになります。とにかく線形時間挙動に関する欠点はありません。

int frequency(char ch, string input) { 
    int result = 0; 
    for(int pos = 0; pos < input.size(); ++pos) { 
     if (input[pos] == ch) { 
      ++result; 
     } 
    } 
    return result; 
}