void preOrderTravers(Node* root) {
if (root) {
printf("%d ", root->data);
preOrderTravers(root->left);
preOrderTravers(root->right);
}
}
Как работает рекурсия?
Вот допустим, что в обходе бинарного дерева мы вышли на левый нижний узел. Я так понимаю, формируются стек вызова рекурсивной функции, и, дойдя до тупика, машина переходит на предыдущий шаг и выполняет preOrderTravers(root->right). Так, да? Просто я где то что то читал но не могу сейчас найти.
Ответ
Каждый вызов функции преобразуется в команду типа call xxx. В результате выполнения этой команды в стек заносится адрес возврата.
Пока не достигнуто дно рекурсии функция не завершается, а вызывает сама себя.
Когда достигается дно рекурсии функция завершается. При этом выполняется команда типа ret, которая выполняет переход по сохранённому в стеке адресу - происходит возврат на один уровень вверх.
Таким образом, в случае дерева, функция вызывает себя до достижения листа, что является признаком дна рекурсии. После этого происходит возврат из вызванных функций.
Комментариев нет:
Отправить комментарий