How to avoid stack overflow of a recursive function?

Question

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?

Answer 1

consider iteration over recursion , if that is really a concern.

http://en.wikipedia.org/wiki/Tree_traversal

see the psedo code there for iteration iterativeInorder iterativePreorder iterativePostorder

Basdically use your own list as stack data structure in a while loop , You can effectively replace function recursion.

Answer 2

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.

Answer 3

The thing about recursion is that you can never guarantee that it will never overflow the stack, unless you can put some bounds on both the (minimum) size of memory and (maximum) size of the input. What you can do, however, is guarantee that it will overflow the stack if you have an infinite loop...

I see your "if() return;" terminating condition, so you should avoid infinite loops as long every branch of your tree ends in a null. So one possibility is malformed input where some branch of the tree never reaches a null. (This would occur, e.g., if you have a loop in your tree data structure.)

The only other possibility I see is that your tree data structure is simply too big for the amount of stack memory available. (N.B. this is virtual memory and swap space can be used, so it's not necessarily an issue of insufficient RAM.) If that's the case, you may need to come up with some other algorithmic approach that is not recursive. Although your function has a small memory footprint, so unless you've omitted some additional processing that it does, your tree would really have to be REALLY DEEP for this to be an issue. (N.B. it's maximum depth that's an issue here, not the total number of nodes.)

Answer 4

You could increase the stack size for your OS. This is normally configured through ulimit if you're on a Unix-like environment.

E.g. on Linux you can do ulimit -s unlimited which will set the size of the stack to 'unlimited' although IIRC there is a hard limit and you cannot dedicate your entire memory to one process (although one of the answers in the links below mentions an unlimited amount).

My suggestions would be to run ulimit -s which will give you the current size of the stack and if you're still getting a stack overflow double that limit until you're happy.

Have a look here, here and here for a more detailed discussion on the size of the stack and how to update it.