Как сделать эту функцию поиска нерекурсивной?

Question

Как сделать эту функцию поиска нерекурсивной?

Я пытаюсь превратить эту рекурсивную функцию в нерекурсивную. Это функция поиска из бинарного дерева поиска. Я знаю, что естественно сделать его рекурсивным, но для целей обучения я бы хотел сделать его нерекурсивным. Как я мог это сделать? Заранее спасибо!

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

}

2

binary-search-tree binary-tree c++non-recursive recursion

Решение

Другие решения

Обычно вы можете сделать рекурсивную функцию в общем итеративной, по существу «помещая» рекурсивные вызовы в стек, а затем используя

while !stack.is_empty() do stack.pop() Такие вещи

поскольку это, по сути, то, что будет делать компилятор, учитывая, что рекурсия не происходит на уровне машинного кода

1

Источник

Accepted Answer

Вот механический способ сделать рекурсивный алгоритм нерекурсивным.

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);
}

Объедините состояние (аргументы и локальные переменные):

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 == state.data) return true;
else if (data <= state.root->data) return Search(state.root->left, state.data);
else return Search(state.root->right, state.data);
}

завернуть тело в петлю:

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 == state.data) return true;
else if (data <= state.root->data) return Search(state.root->left, data);
else return Search(state.root->right, data);
}
}

Замените случай, когда вы используете хвостовую рекурсию (возврат recursive_call) с изменением состояния, и продолжайте:

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 == state.data) return true;
else if (data <= state.root->data) {
state = {state.root->left, state.data};
continue;
} else  {
state = {state.root->right, state.data};
continue;
}
}
}

Теперь, если есть еще рекурсивные вызовы, которые не являются return recursive_call, добавьте ручной стек состояния и нажмите / вытолкните его вместо смены спины. Включите местоположение возвращаемого состояния как void** в коде с метками.

Это не требуется здесь, поэтому я не буду беспокоиться об этом.

5