escaping out of recursive function 1

[jimberger]

hello,

i am trying to search through a search tree using a recursive function. however when i find the word i am searching for i want to exit the recusion to avoid searching the entire tree.has anyone any ideas on how i can do this?
thanks for your help
jimberger

 

[qednick]

can't you just [tt]return;[/tt] once you found the item you're looking for?

^{programmer (prog'ram'er), n A hot-headed, anorak wearing, pimple-faced computer geek.}​

 

[qednick]

Or, if it's an infinite recursive you could set some kind of boolean flag to prevent recalls.

^{programmer (prog'ram'er), n A hot-headed, anorak wearing, pimple-faced computer geek.}​

 

[BryanY]

This assumes you have functions for returning the data of the root, as well as the data of the left and right children.


bool find (bintree T, int val)
{
if (empty(T)) return false;
else if (rootdata(T)==val) return true;
else
return find(left(T),val)||find(right(T),val);
}

// I believe this will stop searching the tree as soon as it finds a match

 

[lionelhill]

I thought the idea of a binary tree was to make the search shorter, a sort of structured version of a binary search through an ordered simple array.. In the case here, surely data will get searched in order from one side of the tree to the other, until the value is found (and then, yes, the search will be abandoned, which is good).

But if the data are just going to be searched in order irrespective of what you're looking for, why is a binary tree more efficient than a simple list?

I'm probably not getting the point, so please explain if you have time...

 

[jimberger]

thats a good point actually lionelhill your're right aswell
i was writing the search function wrong i needed to do a check on the value to see if it was greater than the node data to determine which root to take down the tree. having done this the problem of having to exit the recursion no longer exists
thanks for your help
jim

 

[BoulderBum]

I realize you're adopting a different approach, but...

The general rule to any recursive algorithm is you should have a "base case" that defines a termination condition. In this case, you seem to want to find if a value exist in the tree.

You pass the root node to the function at first. I'm not certain that this syntax is correct, but it demonstrates termination conditions.

bool search( treeNode *Node, variable searchValue )
{
//termination condition
if( searchValue == Node->nodeData )
{
cout << searchValue << &quot; found.&quot; << endl;
return true;
}
else if( searchValue < Node->nodeData )
//termination condition
if( Node->leftChild == NULL )
return false;
else return search( Node->leftChild, searchValue );
else if( searchValue > Node->nodeData ) //comparison made for clarity
//termination condition
if( Node->rightChild == NULL )
return false;
else return search( Node->rightChild, searchValue);
}