спасите пожалуйста мою психику и клавиатуру...
А почему непременно "рекурсивное"?
Вам требуется "иерархическое" меню, с "неограниченным уровнем вложенности", я бы так это назвал.
Давно уже не делал подобное, 2021 год все таки, composer... webpack... и всё такое :D но наверное подошел бы как-то так:
1. (допустим, root у на это id == 1), тогда надо получить массив значений, у которых parent_id == 1 - правильно? Мы получим 1-й уровень меню.
2. Потом поочередно, в цикле, берем каждый элемент из этого списка, и уже находим детей для него.
3. И т.д.
4. Результаты можно складывать в какой-нибудь объект или массив.
ну это, так, навскидку.