C++ 関数の再帰的実装: 再帰の深さに制限はありますか?

C 関数の再帰の深さは制限されており、この制限を超えるとスタック オーバーフロー エラーが発生します。制限値はシステムやコンパイラによって異なりますが、通常は 1000 ～ 10000 の間です。解決策としては、1. 末尾再帰の最適化、2. 末尾呼び出し、3. 反復実装があります。

#C 関数の再帰的実装: 再帰の深さに制限はありますか?

C では、再帰は関数が自分自身を呼び出すことを可能にする強力なテクニックです。ただし、再帰の深さには制限があり、この制限を超えるとスタック オーバーフローと呼ばれるエラーが発生します。

スタック オーバーフロー

各関数呼び出しは、一部のデータ (関数パラメーター、ローカル変数、戻りアドレスなど) をスタックにプッシュします。関数が戻ると、このデータはスタックからポップされます。再帰の深さが大きすぎると、スタックが使い果たされ、スタック オーバーフロー エラーが発生する可能性があります。

再帰の深さの制限

C 再帰の深さの制限の正確な値は、システムとコンパイラに依存するため定義されていません。ただし、通常、制限は 1000 ～ 10000 の間であると考えられます。

実際的なケース

フィボナッチ数列の n 番目の項を計算する次の再帰関数を考えてみましょう:

int fib(int n) {
  if (n <= 1)
    return n;
  else
    return fib(n - 1) + fib(n - 2);
}

fib(10000 ) の場合、再帰の深さが制限を超えるため、スタック オーバーフローが発生します。

解決策

再帰の深さ制限問題にはいくつかの解決策があります:

• 末尾再帰の最適化: Someコンパイラは末尾再帰呼び出しを最適化して反復に変換できるため、再帰スタックの必要性がなくなります。
• 末尾呼び出し: 再帰呼び出しを末尾呼び出しに手動で変換し、関数が戻る前にパラメーターと戻り値を割り当てます。
• 反復実装: 結果を計算するために再帰ではなくループを使用するように関数を書き直します。

結論

C 関数の再帰の深さは制限されており、この制限を超えるとスタック オーバーフロー エラーが発生します。この制限は、末尾再帰最適化、末尾呼び出し、または反復実装を通じて回避できます。

以上がC++ 関数の再帰的実装: 再帰の深さに制限はありますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。