Что такое рекурсия?
Короткий ответ
Рекурсия - вызов функции самой себя прямо или через другие функции. Для завершения нужны базовый случай и шаг, который к нему приближает.
Разбор
При обходе дерева функция обрабатывает узел и вызывает себя для детей. Отсутствующий узел может быть базовым случаем, на котором вызов сразу завершается.
Глубокая рекурсия может переполнить стек, поэтому иногда ее заменяют явным стеком и циклом. Если структура может содержать циклы, нужно также помнить посещенные узлы.