Вячеслав Осипов

Начать строить дерево вызовов для каждой функции. Как только при добавлении очередного вызова где то выше по дереву уже есть вызов этой же функции - вот вам и рекурсия.

Найти или написать парсер
Пройтись по AST
Найти те определения функций, которые включают вызовы себя

Читаем все функции в массив, где ключом будет название функции, а значением - тело функции.
Перебираем этот массив, проверяя следующим образом:
Если название функции содержится в теле - то это рекурсия, пишем этот элемент в другой массив
Иначе - рекурсии нет, проверяем следующий элемент.