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

Question

お世話になります、ＡＥと申します。
次のような件に悩まされています。

○画像のラベリング処理において、再帰呼び出しによって塗りつぶし処理を行っているのですが、再帰の回数が多くなると途中でメモリリークによるものと思われるエラーが発生し処理が中断してしまいます。
＃ただし、物理メモリを全部使い果たした様子はありません。

ソースコードやエラーメッセージを添付できず、漠然とした質問で大変心苦しいのですが、一般論として、

○Windows上で開発したプログラムにおいては、再帰の回数（あるいは再帰呼び出しのために確保されるメモリ量）は有限なのでしょうか？また有限であったとしてそれを拡張する設定があるのでしょうか？

ということについてご意見などいただければと思います。

＊＊＊＊
無論、プログラム自体の不具合によってメモリリークを引き起こしているんじゃないの？とか、そもそもメモリが足りてないんじゃないの？というご意見もあるかと思いますが、それは取り敢えずおいておいて、一般的な意見として、「メモリの許す限り何回でもいけるぞ！」とか「同じような経験をしたぞ！」とかいう意見を伺えれば幸甚です。
合わせて解決策がもしあるものでしたらご意見ください。

一般的なUNIXではlimitでユーザが使えるメモリ量を設定できると思うのですが、そういう類の設定がWindowsにもあるぞ！というご意見などもお待ちしております。
勉強不足で申し訳なのですが、よろしくお願いいします。

liar_adan · Accepted Answer

再帰の回数は有限です。というより、再帰のために使えるメモリの量が有限です。

数年前ためしたところでは、単純な級数の再帰で、
1万回程度の再帰呼び出しが限界でした。

この現象は、C言語のプログラムが使うメモリが、いくつかに
分かれていることに原因があります。
(メモリとしては同じなのですが、使われ方が違うのです。)
だいたい、4種類になります。

(1)コード領域(プログラムを記憶しておく)
(2)静的記憶領域(即値データを記憶しておく)
(3)スタック領域
(4)ヒープ領域

関数の再帰呼び出しのとき使うメモリは、(3)の「スタック領域」です。
一方、malloc()などで確保できるメモリは、(4)の「ヒープ領域」です。

一般的に、ヒープ領域の方がはるかに多くのメモリを確保できます。
スタック領域に使えるメモリは、それほど多くはありません。
そのかわり、関数呼び出しなどに使いやすい構造になっています。
スタックのメモリは、あくまでも「一時置き」と考えられています。
(これでもずいぶん多くなったのです。
MS-DOSの時代は、ちょっと深い再帰呼び出しをすると
すぐにスタックメモリが足りなくなりました)

スタックの量を増やすコンパイルオプションは、
コンパイラによって存在したと思いますが、
すみませんが覚えていません。
極端に増やすことはできないと思います。
どのみち限界があるので、
あまり深い再帰呼び出しはしない方がいいです。
(環境によって、どの程度なら大丈夫というのはありますが)

実用プログラムであれば、面倒でも、再帰を使わない構造に書き直す方がいいのではないでしょうか。

anmochi · Answer

これにはそもそもプログラムがどのように動作しているのかを理解する必要がある。

　誤解を恐れずに言うと、１プログラムが使用するメモリには4種類ある。どれも物理的にはメモリに違いないのだが。
・コード：プログラムが置かれる
・データ：C言語だと、関数外で定義した変数などが置かれる
・ヒープ：C言語だと、malloc、MemoryAllocで確保したもの
・スタック：関数呼び出し履歴、関数内で定義した変数(実体はヒープに置かれる事もある)

　イメージとして、4LDKを考えてください。コードの部屋、データの部屋、ヒープの部屋、スタックの部屋。ここで、君の症状の場合、スタックの部屋が満杯になっているのではないかと思う。4LDKなので、スタック君の部屋が手狭になったからと言って、壁をぶち抜いて他の部屋にスタック君の持ち物を置く訳にはいかない。
　これをスタックオーバーフローと言い、関数呼び出し履歴が多すぎてスタック部屋が満杯になった状態だ。

　スタックサイズを変更する事、その関数の引数や関数内変数を減らす事で、ある程度は対応できると思うが、根本的にはやはり色の塗り替えを部分的に分けるなどの対処が必要でしょうな。

BLUEPIXY · Answer

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

rinkun · Answer

C言語においては再帰呼出しはスタックを消費します。
従って、スタックサイズの制限値が再帰段数の制限になりますが、16bit時代はともかく32bitモデルではスタックは通常は十分に大きいです。
従って、再帰呼出しされる関数で巨大な配列を自動変数で宣言しているとかでない限り簡単には制限には掛かりません。

なお、マルチスレッドの場合は初期スレッド以外はスタックサイズが小さい場合もあるので要確認です。
またコンパイラの設定でスタックサイズを指定している場合もありますのでこれも確認ください。

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

再帰の回数は有限です。

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

再帰関数の処理で制限になるのは、メモリというよりスタックとして確保されているメモリのサイズです。

C言語においては再帰呼出しはスタックを消費します。

似たような質問が見つかりました

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

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