c - 大数递归函数崩溃C/C++

Question

我对以下代码发生的崩溃感到困惑:

#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，则所有内容都会打印，并且一切正常。

如果“i”设置为 65095 或更大，则它不会向控制台打印任何内容，在 win8 上发出崩溃消息，并在 XP 上退出。在输出文件中，它变为:

 initially x in else is 29

 initially

它没有完成文件最后一行中“最初”之后的句子。

显然崩溃是一个段错误。这可能是某种缓冲区溢出吗？我怎样才能让它达到数亿？

感谢您的宝贵时间。

Answer 1

每个递归级别都需要一个新的堆栈帧，其中至少包含局部变量、返回地址和返回值、可能的调用参数...而且堆栈大小非常有限，通常为 1-2 MB。这就是您的函数导致堆栈溢出的原因。

您可以尝试在编译期间增加堆栈大小或使用尾递归，并希望编译器能够优化不必要的堆栈帧，但这些都是糟糕的想法，因为它们依赖于编译器，并且前者仍然不会任意扩展。

相反，重写函数以用迭代代替递归。