Large number recursion function crash C/C++

Question

I'm perplexed by a crash I'm getting with the following code:

#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;

}

If 'i' is less than 65095 then everything prints, and everything works fine.

If 'i' is set to 65095 or greater, then it prints nothing to the console, issues a crash message on win8, and simply exits on XP. In the output file it gets down to:

 initially x in else is 29

 initially

It does not finish the sentence after 'initially' in the last line of the file.

Apparently the crash is a segfault. Could this be a buffer overflow of some sort? How can I get it to run into the hundreds of millions?

Thank you for your time.

Read [Recursion vs. Stack](http://stackoverflow.com/questions/35097729/recursion-vs-stack) for an explanation of why recursion can cause stack overflows. — kaylum, May 07 '16 at 11:43
@GillBates: then he should use a language that optimizes this to tail recursion. — Jongware, May 07 '16 at 12:33
Looks like C code. I removed the C++ tag. If you use a C++ compiler, though, change to C++, but remove the C tag then. C and C++ are **different languages**. And see [ask]. — too honest for this site, May 07 '16 at 14:11

score 1 · Answer 1 · answered May 07 '16 at 12:06

Every recursion level requires a new stack frame which contains at least the local variables, return address and return value, potentially call arguments... And stack size is very limited, usually 1-2 MB. This is why your function causes a stack overflow.

You could try to increase the stack size during compilation or use tail recursion and hope the compiler will optimize the unnecessary stack frames away but these are terrible ideas as they are compiler dependent and the former will still not scale arbitrarily.

Instead, rewrite your function to replace recursion with iteration.

score 0 · Answer 2 · answered May 07 '16 at 12:03

Every invocation of a function requires some space on a memory area known as the stack, which is not freed up until the function returns. The operating system limits the size of this (usually to something quite small, much smaller than the heap say). Calling a function many times recursively means all those calls are active simultaneously and thus eventually the available stack space is exceeded. The symptom of this is a segmentation fault - known as stack overflow.

Large number recursion function crash C/C++

2 Answers2