最大再帰深度を見つける

Question

C++で、最大再帰深度を知る方法は、明示的に再帰を呼び出すことなくクラッシュするまでですか？

これはスタックのサイズによって制限されることがわかりました。おそらく、特定の再帰レベルでスタック内の空き領域の量を見つけることが有用な場合があります。出来ますか？

Answer 1

ここで私が考えることができるのは、getrlimitを使用して、プロセス専用のスタックの最大サイズを取得することです。次に行うべきことは、現在使用されているスタックサイズを取得する方法を見つけることです。私はgetrusageが行く方法だと思ったが、man -pageと2件の投稿を見ると、この特定の機能はもはやサポートされていないようだ。だからあなたは別の方法を見つけなければならない。私はValgrindもスタック使用量を報告しているので、そのソースコードとドキュメントを調べると有用であると信じています。

あなたは現在のスタックサイズを取得することができたら、それはには何も持っていないので、あなたの計算から、これを除外することができるようにあなたが（再帰を開始する前に、あなたは

• 初期状態を測定することができますUSIとともに初期スタック割り当てを除く再帰自体）

• 1回の反復のためにその変化

を行います1回の再帰ステップに必要な合計スタックサイズと割り当てには、指定されたシステムに対してできる再帰回数を近似できる必要があります。私はそれが動作するかどうか確かめても正確な場合でも、あなたが使用しているシステムに依存している（すべてのスタックは、プロセスが持つことができる仮想メモリの量に密接に関連している）。

Answer 2

最大再帰の深さは、関数によって使用されるメモリの量、プラットフォーム上のメモリ量、およびOSまたはコンパイラによる制限（ある場合）によって異なります。

• 関数呼び出し
• 渡されたパラメータによって占められるメモリのオーバーヘッド：再帰呼び出しで

  は、メモリによって占有されています。

• ローカル変数

ないパラメータとローカル変数を持つ再帰関数によって占められるメモリは、大きなオブジェクトの多くを通過し、占有関数よりも高い可能深さ（再帰呼び出しの数）を有するであろう多くのローカル変数。

あなたの質問に対する答えは、再帰呼び出しの最大数は、再帰呼び出しによって占有されるメモリの量、システム上のメモリ量、およびコンパイラまたはオペレーティングシステムによって課せられた制限に依存します。異なる再帰関数は、異なる量のメモリを占有する。

これらの項目がすべてわかっている場合、可能な再帰の最大数を計算できます。