C言語関係掲示板

過去ログ

No644 再帰関数とスタックについて

[戻る] [ホームページ]
No.6911

再帰関数とスタックについて
投稿者---勉強中(2003/05/29 17:03:30)


あんまり再帰させすぎるとスタックが溢れて異常終了しますが、
戻り値も引数もvoidならそういうことはないのかな?
と疑問に思ったのでテストコードを書いてみました。

printfで再帰回数を表示させた方は思った通りずっと表示し続けてくれたのですが、
自前のコードで表示した方は693回で固まってしまいました。

原因がわからなくて悩んでいます。
よろしくお願いします

環境: Win98, LSI C-86 3.30c

/*-- テストコード --*/
#include <stdio.h>

unsigned short count = 0;
unsigned short val;
char buf[6];
char *p;

#define SIZE (sizeof(buf) / sizeof(buf[0]))

void main(void)
{
    count++;

#if 1
    p = &buf[SIZE - 1];
    *p = '\0';
    for ( val = count; val != 0; val /= 10 ) {
        p--;
        *p = (val % 10) + '0';
    }
    putchar('[');
    while ( *p != '\0') {
        putchar(*p);
        p++;
    }
    putchar(']');
    putchar('\n');
#else
    printf("[%hu]\n", count);
#endif

    main();
}



No.6912

Re:再帰関数とスタックについて
投稿者---しんちー(2003/05/29 17:18:37)


main 以外の関数を再帰させたほうがよろしいかと思います。
ちなみに、引数と返り値が void でも、戻り番地がスタックに積まれていくためいずれは溢れると思います。

あと、書かれたプログラムは最適化によってはただの繰り返しに最適化される場合もあります。
(いわゆる末尾再帰な書き方になっているため)

No.6929

Re:再帰関数とスタックについて
投稿者---hu(2003/05/30 03:55:09)


>ちなみに、引数と返り値が void でも、戻り番地がスタックに積まれていくためいずれは溢れると思います。

スタックにどんなものが積まれるかというのは、CPUなどのプラットフォームに依存する
(CPUごとに取り決めがある)話なので、一般的な説明をすると…

ある関数のスタックフレームには通常、その関数の引数やローカル変数、呼び元へ
返るための戻りアドレス、さらに、その関数で使用する予定のレジスタから退避された
元の値、などがあります。
これ以外にも、取り決めにより予約されている領域(C言語の世界では全く知らなくて
良いもの)もあるので、ちゃんと無限再帰されているなら、いつかは絶対にスタック
オーバーフローになるはずです。