How to avoid stack overflow of a recursive function?

c, c++, recursion, stack-overflow

Solution

There's no portable solution other than by replacing recursion with explicit management of the stack (using `std::vector<Node*>`). Non-portably, you can keep track of the depth using a static variable; if you know the maximum stack size, and how much stack each recursion takes, then you can check that the depth doesn't exceed that.

A lot of systems, like Linux and Solaris, you can't know the maximum stack depth up front, since the stack is allocated dynamically. At least under Linux and Solaris, however, once memory has been allocated to the stack, it will remain allocated and remain affected to the stack. So you can recurse fairly deeply at the start of the program (possibly crashing, but before having done anything), and then check against this value later:

static char const* lowerBound = nullptr;

//  At start-up...
void
preallocateStack( int currentCount ) {
{
    char dummyToTakeSpace[1000];
    -- currentCount;
    if ( currentCount <= 0 ) {
        lowerBound = dummyToTakeSpace;
    } else {
        preallocateStack( currentCount - 1 );
    }
}

void
checkStack()
{
    char dummyForAddress;
    if ( &dummyForAddress < lowerBound ) {
        throw std::bad_alloc();   //  Or something more specific.
    }
}

You'll note that there are a couple of cases of undefined/unspecified behavior floating around in that code, but I've used it successfully on a couple of occasions (under Solaris on Sparc, but Linux on PC works exactly the same in this regard). It will, in fact, work on almost any system where: - the stack grows down, and - local variables are allocated on the stack. Thus, it will also work on Windows, but if it fails to allocate the initial stack, you'll have to relink, rather than just run the program at a moment when there's less activity on the box (or change `ulimits`) (since the stack size on Windows is fixed at link time).

EDIT:

One comment concerning the use of an explicit stack: some systems (including Linux, by default) overcommit, which means that you cannot reliably get an out of memory error when extending an `std::vector<>`; the system will tell `std::vector<>` that the memory is there, and then give the program a segment violation when it attempts to access it.

Problem

For example if we are traversaling a rather big tree by following function, it is possible that we get stack overflow. ``` void inorder(node* n) { if(n == null) return; inorder(n->l); n->print(); inorder(n->r); } ``` How to add a condition or something into the function to prevent such overflow from happening?

Original source

Related problems