VC++ 再帰呼び出しについて

質問

VC++6.0にてプログラミングを行っているものですが、
関数の再帰呼び出しについて質問です。

再帰呼び出しの際にスタックに積まれる変数というのは、
再帰呼び出しをする関数に渡す引数のことですか？

スタックオーバーフローを起こさないために、
staticなポインタにHeap領域上の 変数を割り当てるとよい。
と分かったのですが、 この意味は、例えば

static int *a = new int;

ということなのですか？

回答No.3

isobeman · ベストアンサー

再帰では、複雑な処理を簡潔に書けて、良いように思えますが、スタックオーバーフローの危険性を常に考慮すべきです。
スタック領域を消費するのは、ローカル変数の他、関数の引数、戻り値等です。また、ポインタ変数もスタックを使用しますので、いくら使用するメモリを動的に割り当てたとしても、ポインタ変数分のスタックメモリ（4バイト）は消費されます。

スタックオーバーフローを起こさないためには、再帰呼び出しの回数を制限するなどする必要がありますが、制限してしまっては、処理が完結しないこともあります。
このような場合には、再帰以外の方法を検討する必要があります。
forやwhileループを使用して、同じ処理が実現できないか検討してみましょう。

staticなポインタに動的にメモリを割り当てる方法を使用すれば、有る程度スタックオーバーフローの発生を遅らせることができますが、気をつけなければならないことがあります。
static変数は、その関数内でいつでも同じメモリ領域を使用するようになりますので、以下のようにする必要があります。

// 良い例
void func()
{
static int* i = new int;
// ここで何か処理をする
delete i;
func();
}

以下のようにすると、駄目です。
deleteで削除されるべきアドレスが、再帰先で上書きされてしまうためです。

// 駄目な例
void func()
{
static int* i = new int;
// ここで何か処理をする
func();
delete i;
}

また、こうしたところで、関数の呼び出しには、必ずスタックが消費されますので、完全にスタックオーバーフローを阻止することはできません。

再帰を使用しないアルゴリズムを考えましょう。

回答No.4

isobeman

↓に追加です。

再帰関数に引数をつけているなら、引数をやめてしまって、static変数で次の再帰関数に値を伝える方法もできますね。通常の引数とはちょっと勝手が違いますが、スタックオーバーフローは延期できると思います。
また、戻り値も同様に、voidにして戻り値用のstatic変数を用意すればよいと思います。
ただ、staticは、通常のローカル変数とは勝手が違いますから、注意が必要です。

ちなみに、この場合、再帰に突入するコールで引数を渡せない＆戻り値を受け取れない、という問題が発生します。なので、もしやるとすると、モジュールレベル変数を使用した方がよいかもしれません。

、、、やればやるほど複雑怪奇になり、「再帰＝きれいに書ける」の定理が崩れてきますので、再帰をなくす方向がおすすめです。

お礼

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

私の知りたいことが簡潔に書かれていて大変参考になりました。

再帰を用いないプログラムを考え直すことにします。

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

回答No.2

noname#30727

記憶が曖昧ですが、VC++6.0の生成するスタックチェックコードは、一度に64KB以上くらいの大きさを確保すると、エラーを出すようになっていたはずです。
OS依存だと思いますが、それより小さいサイズを確保していくぶんには、デフォルトのスタック（1MB程度？）を使い切ったとしてもヒープと同じように自動的にサイズが増えていくので問題になることは少ないでしょう。

再帰かどうかは関係ないですが、関数を呼び出したときに、引数、ベースポインタ、戻りアドレス、呼び出し先関数の自動変数の合計サイズぶんのスタックが使用されます。普通に数十レベルくらいネストしても気にする程ではありません。

void recursiveFunction(int n)
{
char buff[256];
if (n < 100) {
recursiveFunction(n + 1);
}
}

int main()
{
recursiveFunction(0);
return 0;
}

↑くらいのネストなら「深刻」とは言えないです。
もっと巨大な領域を確保する必要があるなら、

struct MyDataType
{
char c[10000];
int n[1000];
double f[2000];
};

void recursiveFunction(int n)
{
MyDataType *p = new MyDataType;
if (n < 100) {
recursiveFunction(n + 1);
}
delete p;
}

↑のようにnewを使えばいいと思います。

補足

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

上のnewを用いたプログラムでは、
MyDataType型のポインタpは使われているのですか？

私も上記のようなnewを用いた再帰関数を試してみたのですが、
やはりスタックオーバーフローで止まってしまいました。

やはり、ネストが深すぎるのでしょうか？

回答No.1

はなおか じった（@Jitta）

こんにちは。

　関数で使うローカルな変数は、別の関数を呼び出すときにすべてスタックに積まれます。つまり、ローカル変数が多くて（領域が大きければなお効果的）、関数呼び出しのネストが深いと、再帰呼び出しでなくてもスタックオーバーフローをおこします。再帰呼び出しでは、気をつけないと呼び出しが何重にもなり、スタックオーバーフローをおこしやすい、ということです。

　このことは、人間が処理の流れを目で追いかけることに喩えるとよくわかると思います。あなたの頭は、いくつの呼び出しを覚えていられますか？覚えられなくなった時点であなたのスタックがオーバーフローしたことになります。

　関数中でstatic宣言すると、次の呼び出しで以前の内容は消えてしまいます。

main() {
recallFunc();
}

recallFunc() {
static int i = 1;
printf("i = %d\n", i++);
recallFunc();
}

さて、結果はどうなるでしょう？

補足

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

なるほど、おそらく理解しました。
staticな変数を用いた再帰呼び出しでは、
処理がうまく行えないですね。

Heap領域のみを使えば問題ないのでしょうか？
それでもやはり、ネストが深いとスタックオーバーフローになってしまうんでしょうか？