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

If you have a very large tree, and you are running into issues with overrunning your stack using recursive traversals, the problem is likely that you do not have a balanced tree. The first suggestion then is to try a balanced binary tree, such as red-black tree or AVL tree, or a tree with more than 2 children per node, such as a B+ tree. The C++ library provides std::map<> and std::set<> which are typically implemented using a balanced tree.

However, one simple way to avoid recursive in-order traversals is to modify your tree to be threaded. That is, use the right pointer of leaf nodes indicate the next node. The traversal of such a tree would look something like this:

n = find_first(n);
while (! is_null(n)) {
    n->print();
    if (n->is_leaf()) n = n->r;
    else n = find_first(n->r);
}

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

A small prototype of the alterations that can be made by associating another int variable with the recursive function.You could pass the variable as an argument to the function starting with zero value by default at the root and decrement it as u go down the tree ...

drawback: this solution comes at the cost of an overhead of an int variable being allocated for every node.

void inorder(node* n,int counter)
{
 if(counter<limit) //limit specified as per system limit
 {
  if(n == null) return;
  inorder(n->l,counter-1);
  n->print();
  inorder(n->r,counter-1);
 }
 else
  n->print();
}

consider for further research: Although the problem may not be with traversal if only recursion is to be considered. And could be avoided with better tree creation and updation. check the concept of balanced trees if not already considered.

Answer 4

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 5

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.

Answer 6

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 7

You can add a static variable to keep track of the times the function is called. If it's getting close to what you think would crash your system, perform some routine to notify the user of the error.