14

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?

Deqing
  • 14,098
  • 15
  • 84
  • 131
  • That's not really a question you should be worrying about unless you're dealing with some pretty huge trees. – Borgleader Jul 01 '13 at 04:24
  • 1
    Be suggestion would be to send extra param `counter` to track it. – VoidPointer Jul 01 '13 at 04:28
  • 2
    This is only an issue if your tree is really deep. If that is the case you have, you may want to consider converting your recursive function to a non-recursive one. – Vaughn Cato Jul 01 '13 at 04:31
  • Is it a binary search tree, or is it just a tree (e.g. an acyclic graph with no more than two outgoing edges and one incoming edge)? – jxh Jul 01 '13 at 13:36

7 Answers7

6

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.

Anand Rathi
  • 790
  • 4
  • 11
  • That certainly works. There are actually two ways to do it: a pointer-based stack implementation (similar to a linked list), or if you can modify the tree data structure you could just add a parent pointer to every node. The difference would be (treedepth * 2 * ptrsize) memory for the stack vs. (treesize * ptrsize) memory for the parent pointers, where treesize is the number of nodes. Either way you move the memory from the stack to the heap, which may solve the problem, or may just turn a stack overflow into a heap overflow. :) – Dave Lillethun Jul 01 '13 at 05:48
  • 1
    Of course if there's some working state to the inorder() recursive function that was omitted for brevity/clarity, then changing recursion to iteration could make the memory needs O(1) instead of O(log n) - in other words, one copy of the working state instead of treedepth copies. (If the tree has n nodes then the depth is O(log n). ) – Dave Lillethun Jul 01 '13 at 05:50
  • @Dave Thanks for your nice inputs – Anand Rathi Jul 01 '13 at 06:00
3

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.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
1

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.)

Dave Lillethun
  • 2,978
  • 3
  • 20
  • 24
1

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.

Community
  • 1
  • 1
Nobilis
  • 7,310
  • 1
  • 33
  • 67
  • 1
    `ulimit -s` isn't the only limit to stack size. As you say, you need to have the (virtual) memory available for the stack (and most Unix only allocate it lazily). And how much virtual memory you have available depends on what else is happening on the machine at the moment you need the memory. – James Kanze Jul 01 '13 at 09:51
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);
}
jxh
  • 69,070
  • 8
  • 110
  • 193
  • Using any sort of balancing will change the order. Presumably (since he spoke of inorder), the order is semantically significant, so balancing probably isn't an option. – James Kanze Jul 01 '13 at 09:46
  • You are technically correct that my suggestion is not a general solution. However, if the tree was built for performing searches, which it typically is, then balancing is probably the first thing to try. – jxh Jul 01 '13 at 13:34
  • For searching, the tree should be balanced. And you'll probably never visit the entire tree in order. The first thing which came to my mind was a syntax tree, which of course cannot be reordered. – James Kanze Jul 01 '13 at 17:47
  • @JamesKanze: I agree about syntax trees not tolerating much reordering, but to have a syntax tree so deep as to trigger stack overrun seems unlikely to me. I am more likely to believe big data. – jxh Jul 01 '13 at 22:25
0

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.

It'sPete
  • 5,083
  • 8
  • 39
  • 72
  • 1
    With static var, is it possible to reset this for next search/iteration ? – VoidPointer Jul 01 '13 at 04:41
  • There is always a way... but the real question is will it stick up to code review ;). You can pass a boolean parameter to reset the function when the user calls the function. When you call the function from your function, always pass false to not reset the counter. – It'sPete Jul 01 '13 at 04:45
  • 1
    @VoidPointer You shouldn't have to need to reset it. It will be initialized to 0. Increment when you enter, decrement when you leave, and reset to 0 if you hit the limit, just before throwing an exception to bail out. – James Kanze Jul 01 '13 at 09:43
0

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.

Nishanth KD
  • 13
  • 3