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

Question

以下のサイトでＣ言語の勉強をしているのですが、このサイトのソースコードをコピペして実行してみたら上手くいきませんでした。
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);
        }
}

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

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

ss-ak · Accepted Answer

一言で言えば「スタックが溢れた」と思われます。

一般的に、C言語プログラムの関数呼び出しは、次のような処理によって実現されます。

(1)次のようなデータを、「スタック」と呼ばれるメモリ領域に保存
・呼び出し先の関数の処理が完了した後に、戻ってくるべき場所(アドレス、といいます)
・呼び出し先の関数に渡す引数値(この例では、maxなどが、それに相当)
(2)呼び出し先の関数の中で新たに変数などを使う場合は、そのための領域をスタックに追加確保(今回の例では、これはありませんが)
(3)呼び出し先の関数の処理を実行
(4)関数の処理が終わったら、(1)(2)で確保したスタックのメモリ領域を解放して、(1)で保存された場所に処理を戻す

(正確には他にもありますが、割愛します)

今回の例では、再帰呼び出しが行われているので(4)まで終わる前に、新たに(1)からの処理が追加で行われ、再帰が深くなるにつれて、次第にスタックが消費されて行きます。
スタックが無尽蔵にあれば、再帰が10001段(で、あってるかな)になるまで(1)から(3)が繰り返され、最終的に今度は関数の再帰処理が一段ずつ終了していくため、(4)が繰り返されます。

ところが、再帰が深くなっていく途中でスタックが尽きてしまうと、そこでスタックメモリ領域が溢れてしまい、そこから先が正常に動作を続けられなくなってしまいます。

スタックメモリがどの程度確保されるかは、環境によりけりで、ソースコードをコンパイルする際のオプション等で指定できる場合もありますが、いずれにしても、10000段もの再帰をするようなプログラムは、こういった実行環境の特性を踏まえていない、不適切な再帰の使い方だと思います。

このように、極端に深い再帰を何も考えずにするようなプログラミングは、悪い見本なので、真似をしないことをおすすめします。

TreatMeGently · Answer

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

ss-ak · Answer

追記：

＞このように、極端に深い再帰を何も考えずにするようなプログラミングは、悪い見本なので、真似をしないことをおすすめします。

十分なスタックを確保できることが事前にわかっていて、深い再帰をするアルゴリズムに必然性があるなど、十分に考慮した上での場合は、(「何も考えずに」ではないですし)この限りではありません。

tsunji · Answer

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

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

jjon-com · Answer

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

Tacosan · Answer

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

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

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

スタックオーバーフローだと思うけど、printf関数の呼び過ぎで引っ掛かっている可能性もあるね。

追記：

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

この回答への補足

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

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

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

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

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

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

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