quote:

---

Original post by omegasyphon

just curious why do you even want to search a binary tree with a non recursive function? sure it can be done but whats the point? its not more efficient.

---

Actually, searching a binary search tree is a lot more efficient without recursion.

The reason recursion is used a great deal with tree''s is because it is a simple and elegant solution.

recursive BST search:

bool SearchRecursive( dataType data, treeNode* node ){ if( node->data == data ) return true; if( node->data > data && node->hasLeft() ) return SearchRecursive( data, node->left ); if( node->data < data && node->hasRight() ) return SearchRecursive( data, node->right ); return false;}

what a really simple routine, right? Its pretty too.

The problem is that recursion in this example is a waste. The entire purpose of recursion is to store the state of an earlier operation for use later. In a BST search, we do not need to know which path the routine traveled down. This method saves a stack frame for every level of the tree, and then must pop it all from the stack once it reaches a termination point.

Since the BST search algorithm has no use for remembering data from previous levels, and just needs to exit out when it reaches a termination point, an iterative solution to this problem is much faster:

bool SearchIterative( dataType data, treeNode* node ){ treeNode* p = node; while( p != 0 ) { if( p->data == data ) return true; if( p->data > data ) p = p->left; else p = p->right; } return false;}

This version is not much larger, and if you run it, it will be much faster, since it does not require a stack frame creation for each level of the tree.

The same goes with Binary Search Tree insertions, since you do not need to remember the path on the way down, there is no need for recursion.

===============================================
Have I no control, is my soul not mine?
Am I not just man, destiny defined?
Never to be ruled, nor held to heel!

Mithrandir, that isn''t a very good example. Any compiler with any sense will note that the recursion there is pure tail-recursion, and optimize it right out. That''s why I don''t feel bad about using tail recursion... I know that the compiler will realize that it doesn''t need a new stack frame for each call, and therefore won''t create one.

A compiler would really be able to optimize that?

quote:

---

Original post by c_wraith

Mithrandir, that isn''t a very good example. Any compiler with any sense will note that the recursion there is pure tail-recursion, and optimize it right out. That''s why I don''t feel bad about using tail recursion... I know that the compiler will realize that it doesn''t need a new stack frame for each call, and therefore won''t create one.

---

You are putting waaaaay too much faith in the compiler.

Sure, some of the (much) more advanced compilers might do that, but there is really no way of knowing what the compiler would actually do.

My point was that the iterative method is much better for these problems, and not a whole lot larger than the recursive method.

When you start to assume you know exactly what the compiler is going to do, you end up with problems with portability. Besides, what if you wanted to use recursion, and the compiler "optimised" it out...

I''ve never heard of a compiler optimising major theories in the code out though...

===============================================
Have I no control, is my soul not mine?
Am I not just man, destiny defined?
Never to be ruled, nor held to heel!