Stack Overflow error in recursive C++ function

Question

#include<iostream>
using namespace std;
int f()
{
    static int count=0;
    count++;
    if (count>=5000)
        return count;
    return f();
}
int main ()
{
    cout<<f();
    return 0;
}

this function overflows the stack after the value of count exceeds 4800 can anybody tell how to resolve this issue ?

It's obvious but use a bigger stack. How you do that will depends on your compiler/linker. — john, Sep 20 '13 at 18:30
`int f() { ... return f(); }`, recursion is finite. Every depth level needs a bit on the stack, and the latter is not bottomless. — Roman R., Sep 20 '13 at 18:30
Turn on optimizations? Replace entire function with "return 5000"? Or initialize your value to 4999. — Yakk - Adam Nevraumont, Sep 20 '13 at 18:31

score 5 · Answer 1 · answered Sep 20 '13 at 18:30

Don't use recursion - use a regular loop. Every time you call your f() method, you will occupy few words on the stack, and you will overflow it at some point.

Usually, there's way to increase stack size (depending on your system and/or compiler), but I don't want to recommend that (especially because it will overflow again, just with the value of count bigger than 4800).

Or just int f(){ return 5000; } would do.

score 3 · Answer 2 · answered Sep 20 '13 at 19:46

Assuming you want to run recursively, you could turn off debug mode, then you'll succeed (as Visual Studio adds extra stuff on the stack to detect if you "clobber" the stack [it's how it can say "The stack around variable x was overwritten" or whatever the exact message is].

However, relying on being able to do LARGE number of calls recursively is a bad plan in general - at some point or another, it will still fall over. Whether that is 5000, 50000 or 500000 is just a matter of "how much stack-space does this function take". I'd say anything that doesn't have a natural limit of around 100 levels of recursion is a case of "you are solving the problem the wrong way". If you do have such large recursion levels, it's better to use a software stack (e.g. std::stack in C++), and save the crrent state on that stack, and restore it, using the software inside the function.

Running out of stackspace is one of the worst possible runtime problems, because there is really nothing you can do - there may be things you can do to print an error message or some such, but there is really no way to "give the process some more stackspace and continue". When a process runs out of memory or something similar, you can say "Ok, I won't allocate that, and give the user an nice error message saying 'I can't do this', and the nicely save the current state and exit, for example."

[And yes, you can increase the stack-size of your application, but that really should only be done as a true last resort, and only when you fully understand WHY you need such large stack - it's very often something else you're doing wrong if you need a bigger stack].

score 1 · Answer 3 · answered Sep 20 '13 at 18:50

I'm assuming this is for an academic exercise to learn about recursion. (If it is not, please don't use recursion for this!)

A better way to write your function:

#include <iostream>

int f(int i)
{
    if (i >= 5000)
    {
        return i;
    }
    else
    {
        return f(i + 1);
    }
}

int f_alt1()
{
    return 5000;
}

int f_alt2()
{
    int i = 0;
    for (; i <= 5000; ++i);
    return i;
}

int main()
{
    std::cout << f(0) << std::endl;
    return 0;
}

This will still eat up far more runtime resources than returning the constant or incrementing in a loop, and you will need to increase your stack size if you increase the desired constant to a significantly larger number.

//Guys i want to use recursion. I want a way to increase the stack size please tell that — user2800317, Sep 21 '13 at 14:24
That is going to depend on your compiler, as you are going to have to tell the compiler to increase the stack for the program. — Zac Howland, Sep 21 '13 at 16:14

Stack Overflow error in recursive C++ function

3 Answers3