Ｃ言語で再帰的処理が出来ない理由

質問

以下のサイトでＣ言語の勉強をしているのですが、このサイトのソースコードをコピペして実行してみたら上手くいきませんでした。
http://wisdom.sakura.ne.jp/programming/c/c30.html

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

#include<stdio.h>

void func(int );

int main() {
func(0);

printf("プログラムを終了します");
return 0;
}

void func(int max) {
if (max <= 10000) {
printf("%d\r",max);
func(max + 1);
}
}

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

実行してみると、何故か４７００～４８００の辺りで止まってエラーになってしまいます。
どうしてエラーになるのでしょうか？

回答No.4

ss-ak · ベストアンサー

一言で言えば「スタックが溢れた」と思われます。

一般的に、C言語プログラムの関数呼び出しは、次のような処理によって実現されます。

(1)次のようなデータを、「スタック」と呼ばれるメモリ領域に保存
・呼び出し先の関数の処理が完了した後に、戻ってくるべき場所(アドレス、といいます)
・呼び出し先の関数に渡す引数値(この例では、maxなどが、それに相当)
(2)呼び出し先の関数の中で新たに変数などを使う場合は、そのための領域をスタックに追加確保(今回の例では、これはありませんが)
(3)呼び出し先の関数の処理を実行
(4)関数の処理が終わったら、(1)(2)で確保したスタックのメモリ領域を解放して、(1)で保存された場所に処理を戻す

(正確には他にもありますが、割愛します)

今回の例では、再帰呼び出しが行われているので(4)まで終わる前に、新たに(1)からの処理が追加で行われ、再帰が深くなるにつれて、次第にスタックが消費されて行きます。
スタックが無尽蔵にあれば、再帰が10001段(で、あってるかな)になるまで(1)から(3)が繰り返され、最終的に今度は関数の再帰処理が一段ずつ終了していくため、(4)が繰り返されます。

ところが、再帰が深くなっていく途中でスタックが尽きてしまうと、そこでスタックメモリ領域が溢れてしまい、そこから先が正常に動作を続けられなくなってしまいます。

スタックメモリがどの程度確保されるかは、環境によりけりで、ソースコードをコンパイルする際のオプション等で指定できる場合もありますが、いずれにしても、10000段もの再帰をするようなプログラムは、こういった実行環境の特性を踏まえていない、不適切な再帰の使い方だと思います。

このように、極端に深い再帰を何も考えずにするようなプログラミングは、悪い見本なので、真似をしないことをおすすめします。

お礼

関数の再帰的処理ってスタックを用いてたのですね。
再帰的処理にそのような問題があったとは驚きです。
こういう処理はなるべく避けるように気を付けたいと思います。

回答ありがとうございました。

回答No.6

TreatMeGently

スタックオーバーフローだと思うけど、printf関数の呼び過ぎで引っ掛かっている可能性もあるね。
　まずはｏｓにもよるけどprintf("%d\r",max);の￥ｒを￥ｎで実行してみてね。
　ダメなら次はｐｒｉｎｔｆを移動させてみてね。
　void func(int max) {
if (max <= 10000) {
　　　　func(max + 1);
　　　　printf("%d\r",max);
　　}
}
　10000まで実行してから帰りに減算しながら数値表示になるよ。
　10000の表示まで行ったらスタックはｏｋかも。

お礼

両方やってみましたが、やはり途中で止まってしまいます。
どうやらスタックの問題だったようです。

回答ありがとうございました。

回答No.5

ss-ak

追記：

＞このように、極端に深い再帰を何も考えずにするようなプログラミングは、悪い見本なので、真似をしないことをおすすめします。

十分なスタックを確保できることが事前にわかっていて、深い再帰をするアルゴリズムに必然性があるなど、十分に考慮した上での場合は、(「何も考えずに」ではないですし)この限りではありません。

お礼

補足ありがとうございました。
深い再帰をする必要のある状況があるかどうかは分かりませんが、再帰的処理の問題点は頭の片隅に入れておきます。

回答No.3

tsunji

関数呼び出しのたびにスタックポインタへレジスタの退避が行なわれるため、再起呼び出しし続けるとスタックオーバーフローしてエラーになる。

ただし、スタック領域が大きい場合、最後まで実行出来る。

お礼

なるほど、スタック領域の問題ですか。
回答ありがとうございました。

回答No.2

jjon-com

http://ideone.com/ では正常に動作します。
質問者はどんなソフトウェア環境でC言語の勉強をしていらっしゃるのでしょうか。

お礼

回答ありがとうございました。

補足

Visual C++ 2010 で勉強しています。

回答No.1

Tacosan

十分なメモリが使えてなかったりして.

お礼

回答ありがとうございました。