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

#cpp #c

                    
void preOrderTravers(Node* root) {
if (root) {
    printf("%d ", root->data);
    preOrderTravers(root->left);
    preOrderTravers(root->right);
    }
}


Как работает рекурсия?
Вот допустим, что в обходе бинарного дерева мы вышли на левый нижний узел. Я так
понимаю, формируются стек вызова рекурсивной функции, и, дойдя до тупика, машина переходит
на предыдущий шаг и выполняет preOrderTravers(root->right). Так, да? Просто я где то
что то читал но не могу сейчас найти. 
    

Ответы

Ответ 1

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

Таким образом, в случае дерева, функция вызывает себя до достижения листа, что является
признаком дна рекурсии. После этого происходит возврат из вызванных функций.