多数の再帰関数のクラッシュC/C++

Question

私は、私は次のコードで取得していますクラッシュによって当惑している：「私は」未満65095枚のその後、すべてのプリントで、すべてが正常に動作している場合

#include <stdio.h> 

FILE *ofp; 
const char *mode = "r"; 
char outputFilename[] = "data.txt"; 

unsigned long long int chaser(unsigned long long int x) { 

if (x == 0) { 

    printf("x was 0 at some point \n",x); 

    fprintf(ofp,"x was 0 at some point \n",x); 

    return 0; 

    } 

    else { 

    fprintf(ofp,"initially x in else is %lld\n",x); 

    x = chaser(x-1) + 1; // recursion overflow? 

    fprintf(ofp,"after, x in else is is %lld\n",x); 

    } 

    return x; 

} 


int main() { 

ofp = fopen(outputFilename, "w"); 

if (ofp == NULL) { 

    fprintf(stderr, "Can't open output file %s!\n",outputFilename); 

    return(1); 

    } 

unsigned long long int i = 65096; // 65095 and above fail 

unsigned long long int n; 

n = chaser(i); 

printf("finished %lld\n",n);  

fclose(ofp);  

return 0; 

} 

。

'i'が65095以上に設定されている場合、コンソールには何も印刷されず、win8でクラッシュメッセージが表示され、XPでは終了します。出力ファイルでは、次のようになります。

initially x in else is 29 

initially 

ファイルの最後の行で「最初」の後に文が終了しません。

明らかにクラッシュはセグメンテーションです。これは、ある種のバッファオーバーフローですか？どうすれば数億に達することができますか？

ありがとうございます。

Answer 1

関数を呼び出すたびに、スタックと呼ばれるメモリ領域にスペースが必要になります。この領域は、関数が戻るまで解放されません。オペレーティングシステムはこれのサイズを制限します（通常、ヒープよりもはるかに小さい非常に小さなものに制限されます）。関数を何度も再帰的に呼び出すと、それらの呼び出しがすべて同時にアクティブであることを意味し、最終的に使用可能なスタック領域を超えてしまいます。この現象はスタックオーバーフローと呼ばれるセグメンテーションフォルトです。

Answer 2

すべての再帰レベルでは、少なくとも局所変数、戻りアドレス、戻り値を含む新しいスタックフレームが必要です。おそらく引数を呼び出します。 スタックサイズは通常1〜2 MBに制限されています。 これは、関数がスタックオーバーフローを引き起こす理由です。

コンパイル中にスタックサイズを増やしたり、テール再帰を使用したり、コンパイラが不要なスタックフレームを最適化してくれることを期待しても構いませんが、これらはコンパイラに依存しており、

代わりに、繰り返しで再帰を置き換える関数を書き直してください。