ページ 11

【雑談】再帰の限界

Posted: 2011年12月20日(火) 17:23
by みけCAT
再帰をしすぎるとスタックオーバーフローで落ちるとよく言われています。
では、いったいどのくらい再帰をすれば落ちるのでしょうか?
それを調べてみたいと思います。
おそらく環境に依存すると思うので、みんなに協力して調べていただけたらありがたいです。
よろしくお願いします。

調べ方は、まず添付したsaiki_test.zipをダウンロードし、解凍してください。
解答するとsaiki_test_0.exe~saiki_test_9.exeがあります。
それぞれのexeファイルを実行すると、数字が大量に表示されたあと、おそらくある所で強制終了します。
強制終了する直前に出力された行の数字をそれぞれのexeファイルについて調べてください。
Windows以外の環境の方は、
sourceフォルダに入っているsaiki_test_0.c~saiki_test_9.cをそれぞれコンパイルし、実行してください。
その際、最適化はかけないでください。(重要)
あとはexeファイルの時と同じです。

報告する際は、
OSの種類(Windowsなどだけでなく、例えばWindows Vista Home Premium SP2 32ビットなど)、
メモリの容量、
ソースをコンパイルした人はコンパイラの種類、
その他関係があると思われる情報とともに報告してください。

報告用テンプレート
OS:
メモリ:
コンパイラ(コンパイルした場合):
saiki_test_0:
saiki_test_1:
saiki_test_2:
saiki_test_3:
saiki_test_4:
saiki_test_5:
saiki_test_6:
saiki_test_7:
saiki_test_8:
saiki_test_9:
その他(必要と思えば):

自分の結果
OS:Windows Vista Home Premium SP2 32ビット
メモリ:2.00GB
コンパイラ:gcc version 3.2.3 (mingw special 20030504-1)
saiki_test_0:130163
saiki_test_1:65081
saiki_test_2:65081
saiki_test_3:65081
saiki_test_4:65081
saiki_test_5:43387
saiki_test_6:43387
saiki_test_7:43387
saiki_test_8:43387
saiki_test_9:32540
その他:なし

Re: 【雑談】再帰の限界

Posted: 2011年12月20日(火) 17:33
by h2so5
OS: MacOS X 10.6
メモリ: 4.00GB
コンパイラ:gcc 4.2
saiki_test_0:523982

Re: 【雑談】再帰の限界

Posted: 2011年12月20日(火) 17:44
by softya(ソフト屋)
スタックサイズとスタックフレームのサイズは処理系依存と呼び出し規約で決まりますので、このテストの意味が余りありません。それとスレッドのスタックのことも考慮されていません。スタックフレームもcdeclだったりstdcallとC言語でも色々変わります。
「呼出規約 - Wikipedia」
http://ja.wikipedia.org/wiki/%E5%91%BC% ... F%E7%B4%84
あとパソコンでのgccやVC++ならスタックサイズはリンク時に変更が可能です。なのでメモリの容量には依存しません。

それと実際のプログラムはローカル変数やら引数の数やら違うものが多すぎて参考にならないと思います。

Re: 【雑談】再帰の限界

Posted: 2011年12月20日(火) 17:46
by jay
OS:Windows 7 Home Premium 32ビット
メモリ:4.00GB

saiki_test_0:130167
saiki_test_1:65083
saiki_test_2:65083
saiki_test_3:65083
saiki_test_4:65083
saiki_test_5:43559
saiki_test_6:43559
saiki_test_7:43559
saiki_test_8:43559
saiki_test_9:32541

みけCATさんとほぼ同じ数値になりました~

Re: 【雑談】再帰の限界

Posted: 2011年12月20日(火) 17:59
by softya(ソフト屋)
あと同じ数値にならないのはファイルストリームバッファの吐き出しのタイミングの違いの気がします。
fflush(stdout);
を入れると同じバイナリならパソコンが違っても同じ数字になるのではないでしょうか?

Re: 【雑談】再帰の限界

Posted: 2011年12月21日(水) 00:51
by ISLe
Mac OS XはUNIX系なのでOSに設定されたスタックサイズがプロセス起動時に与えられます。
limitコマンドで変更できるらしいです。

ウィンドウズは実行ファイルにスタックサイズが記録されていて使用されます。
コンパイラのオプションで変更できます。
実行ファイルのバイナリを書き換えて変更することもできます。
デフォルトのスタックサイズは、MinGW gccとCygwin gccは2MB、Visual C++は1MBです。

わたしも特定のプログラムで再帰できる深さを調べても意味がないと思います。

Re: 【雑談】再帰の限界

Posted: 2011年12月21日(水) 07:42
by みけCAT
>>softya(ソフト屋)さん、ISLeさん
そうですか・・・
すみません。
解決にしておきます。

Re: 【雑談】再帰の限界

Posted: 2011年12月21日(水) 10:28
by softya(ソフト屋)
コンパイラやOSの仕組みを知ると言う意味では意義がありますよ。
みけCATさん自身が呼び出し規約とかスタックフレームの構造とか理解したいと言う主旨ならもっと追求すべきだと思います。