Ｃ言語における再帰呼び出しの限界？について

質問

お世話になります、ＡＥと申します。
次のような件に悩まされています。

○画像のラベリング処理において、再帰呼び出しによって塗りつぶし処理を行っているのですが、再帰の回数が多くなると途中でメモリリークによるものと思われるエラーが発生し処理が中断してしまいます。
＃ただし、物理メモリを全部使い果たした様子はありません。

ソースコードやエラーメッセージを添付できず、漠然とした質問で大変心苦しいのですが、一般論として、

○Windows上で開発したプログラムにおいては、再帰の回数（あるいは再帰呼び出しのために確保されるメモリ量）は有限なのでしょうか？また有限であったとしてそれを拡張する設定があるのでしょうか？

ということについてご意見などいただければと思います。

＊＊＊＊
無論、プログラム自体の不具合によってメモリリークを引き起こしているんじゃないの？とか、そもそもメモリが足りてないんじゃないの？というご意見もあるかと思いますが、それは取り敢えずおいておいて、一般的な意見として、「メモリの許す限り何回でもいけるぞ！」とか「同じような経験をしたぞ！」とかいう意見を伺えれば幸甚です。
合わせて解決策がもしあるものでしたらご意見ください。

一般的なUNIXではlimitでユーザが使えるメモリ量を設定できると思うのですが、そういう類の設定がWindowsにもあるぞ！というご意見などもお待ちしております。
勉強不足で申し訳なのですが、よろしくお願いいします。

回答No.2

liar_adan · ベストアンサー

再帰の回数は有限です。というより、再帰のために使えるメモリの量が有限です。

数年前ためしたところでは、単純な級数の再帰で、
1万回程度の再帰呼び出しが限界でした。

この現象は、C言語のプログラムが使うメモリが、いくつかに
分かれていることに原因があります。
(メモリとしては同じなのですが、使われ方が違うのです。)
だいたい、4種類になります。

(1)コード領域(プログラムを記憶しておく)
(2)静的記憶領域(即値データを記憶しておく)
(3)スタック領域
(4)ヒープ領域

関数の再帰呼び出しのとき使うメモリは、(3)の「スタック領域」です。
一方、malloc()などで確保できるメモリは、(4)の「ヒープ領域」です。

一般的に、ヒープ領域の方がはるかに多くのメモリを確保できます。
スタック領域に使えるメモリは、それほど多くはありません。
そのかわり、関数呼び出しなどに使いやすい構造になっています。
スタックのメモリは、あくまでも「一時置き」と考えられています。
(これでもずいぶん多くなったのです。
MS-DOSの時代は、ちょっと深い再帰呼び出しをすると
すぐにスタックメモリが足りなくなりました)

スタックの量を増やすコンパイルオプションは、
コンパイラによって存在したと思いますが、
すみませんが覚えていません。
極端に増やすことはできないと思います。
どのみち限界があるので、
あまり深い再帰呼び出しはしない方がいいです。
(環境によって、どの程度なら大丈夫というのはありますが)

実用プログラムであれば、面倒でも、再帰を使わない構造に書き直す方がいいのではないでしょうか。

お礼

詳細な説明、ありがとうございました。
大変、ヒントになりました。
プログラミング自体は長年やっているのですが、この辺りの知識が乏しく情けないかぎりです。

結果としては再帰を使わない構造で書き直しておりますので、実用上問題ない状況にしてはいるのですが、以前から気になっていたものですので。
本当にありがとうございます。

回答No.4

anmochi

これにはそもそもプログラムがどのように動作しているのかを理解する必要がある。

　誤解を恐れずに言うと、１プログラムが使用するメモリには4種類ある。どれも物理的にはメモリに違いないのだが。
・コード：プログラムが置かれる
・データ：C言語だと、関数外で定義した変数などが置かれる
・ヒープ：C言語だと、malloc、MemoryAllocで確保したもの
・スタック：関数呼び出し履歴、関数内で定義した変数(実体はヒープに置かれる事もある)

　イメージとして、4LDKを考えてください。コードの部屋、データの部屋、ヒープの部屋、スタックの部屋。ここで、君の症状の場合、スタックの部屋が満杯になっているのではないかと思う。4LDKなので、スタック君の部屋が手狭になったからと言って、壁をぶち抜いて他の部屋にスタック君の持ち物を置く訳にはいかない。
　これをスタックオーバーフローと言い、関数呼び出し履歴が多すぎてスタック部屋が満杯になった状態だ。

　スタックサイズを変更する事、その関数の引数や関数内変数を減らす事で、ある程度は対応できると思うが、根本的にはやはり色の塗り替えを部分的に分けるなどの対処が必要でしょうな。

お礼

ご回答ありがとうございます。
まさしく、メモリの取り扱いについての意識が低かったと反省というか甘さを感じております。
改めて、この辺りを勉強しなおそうと考えているところです。
参考になりました。

回答No.3

BLUEPIXY

再帰関数の処理で制限になるのは、メモリというよりスタックとして確保されているメモリのサイズです。
スタックサイズを必要なだけ拡大するか、
あるいは、プログラムの中で使う変数をスタックではなくヒープで確保管理して再帰処理できるようにするかすればいいでしょう

お礼

修正のヒント、ありがとうございます。
やはり皆さんのおっしゃるようにスタック領域のサイズによるものと思います。
実のところ、ボリュームデータ（画像を立体に積み上げたようなデータ）を取り扱う処理をしておりまして、その内部のラベリングであるとか抽出であるとかそういう処理を行っております。ですので、皆さんが懸念しておられたようなとてつもなく深く再帰呼び出しされていることは疑いありません。
＃これは認識していましたが、物理メモリの量でのみ考えていたところに落とし穴があったと。
つまり結論として通常のヒープ領域ではなくスタック領域がオーバーフローしていたということかと考えております。

今回の皆さんのご回答を下にこれらのメモリの扱い方を改めて勉強したいと思います。
ありがとうございました。

回答No.1

rinkun

C言語においては再帰呼出しはスタックを消費します。
従って、スタックサイズの制限値が再帰段数の制限になりますが、16bit時代はともかく32bitモデルではスタックは通常は十分に大きいです。
従って、再帰呼出しされる関数で巨大な配列を自動変数で宣言しているとかでない限り簡単には制限には掛かりません。

なお、マルチスレッドの場合は初期スレッド以外はスタックサイズが小さい場合もあるので要確認です。
またコンパイラの設定でスタックサイズを指定している場合もありますのでこれも確認ください。

お礼

早速の対応、ありがとうございます。
なるほど、肝はスタックなのですね。
参考になりました。