Страницы

Поиск по вопросам

пятница, 21 июня 2019 г.

Работа рекурсивной функции, суть на машинном уровне

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


Ответ

Каждый вызов функции преобразуется в команду типа call xxx. В результате выполнения этой команды в стек заносится адрес возврата. Пока не достигнуто дно рекурсии функция не завершается, а вызывает сама себя. Когда достигается дно рекурсии функция завершается. При этом выполняется команда типа ret, которая выполняет переход по сохранённому в стеке адресу - происходит возврат на один уровень вверх.
Таким образом, в случае дерева, функция вызывает себя до достижения листа, что является признаком дна рекурсии. После этого происходит возврат из вызванных функций.

Комментариев нет:

Отправить комментарий