Задан файл с функциями определить какие из них рекурсивные?

Question

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

Всем привет. Столкнулся со следующей проблемой : нужно написать парсер, который будет искать рекурсивные функции в файле. В частности, нужен алгоритм проверки того, что функция является рекурсивной.

Answer 1

[ApeCoder]

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

Answer 2

[GavriKos]

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

Answer 3

[irishmann]

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

Comments

[GavriKos]

Сработает только в случае явной рекурсии. А вот если будет вызов например A->B->A, то уже так не прокатит.