Adam - 1 year ago 62
C++ Question

# How to make this search function non-recursive?

I am trying to turn this recursive function into a non-recursive one.This is a search function from a binary search tree. I am aware it is natural to make it recursive, but for learning purposes I would like to make it non-recursive. How could I do this? Thanks in advance!

``````    bool Search(BstNode* root, string data) {

if (root == NULL) return false;
else if (root->data == data) return true;
else if (data <= root->data) return Search(root->left, data);
else return Search(root->right, data);

}
``````

Here is mechanical way to make a recursive algorithm non-recursive.

``````bool Search(BstNode* root, string data) {
if (root == NULL) return false;
else if (root->data == data) return true;
else if (data <= root->data) return Search(root->left, data);
else return Search(root->right, data);
}
``````

Bundle up the state (arguments and local variables):

``````bool Search(BstNode* root, string data) {
struct State {
BstNode* root;
string data;
};
State state{root, data};

if (state.root == NULL) return false;
else if (state.root->data == data) return true;
else if (data <= state.root->data) return Search(state.root->left, data);
else return Search(state.root->right, data);
}
``````

wrap body in a loop:

``````bool Search(BstNode* root, string data) {
struct State {
BstNode* root;
string data;
};
State state{root, data};

while(true) {
if (state.root == NULL) return false;
else if (state.root->data == data) return true;
else if (data <= state.root->data) return Search(state.root->left, data);
else return Search(state.root->right, data);
}
}
``````

Replace case where you tail-end recurse (return recursive_call) with changing state and continue:

``````bool Search(BstNode* root, string data) {
struct State {
BstNode* root;
string data;
};
State state{root, data};

while(true) {
if (state.root == NULL) return false;
else if (state.root->data == data) return true;
else if (data <= state.root->data) {
state = {state.root->left, data};
continue;
} else  {
state = {state.root->right, data};
continue;
}
}
}
``````

Now, if there are any more recursive calls that are not `return recursive_call`, add a manual stack of state and push/pop it instead of changing the back. Include the location of the return state as a `void**` in the code with labels.

This isn't required here, so I won't bother doing it.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download