Рекурсия – это универсальное средство для организации повторяющихся действий в Prolog’е. Рекурсивная процедура – это процедура, вызывающая сама себя до тех пор, пока не будет соблюдено некоторое условие, которое остановит рекурсию. Такое условие называют граничным. Рекурсия – хороший способ для решения задач, содержащих в себе подзадачу такого же типа. Базисом рекурсии называют некую начальную ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении записывается некий простейший случай, при котором ответ получается сразу, без использования рекурсии. Шаг рекурсии это правило, в теле которого обязаельно содержится, в качестве подцели, вызов определяемого предиката. Если мы хотим избежать зацикливания, определяемый предикат должен вызываться не от тех же параметров, которые указаны в заголовке правила. Параметры должны изменяться на каждом шаге так, чтобы в итоге либо сработал базис рекурсии, либо условие выхода из рекурсии, размещенное в самом правиле. Общий вид: <имя определяемого предиката>:- [<подцели>], [<условие выхода из рекурсии>], [<подцели>], <имя определяемого предиката>, [<подцели>]. Хвостовая рекурсия: Можно сформулировать условия, при соблюдении которых рекурсия в Prolog’е становится хвостовой, то есть не расходует стек при неограниченном количестве рекурсивных вызовов: рекурсивный вызов должен быть последней целью в хвостовой части правила вывода; перед рекурсивным вызовом не должно быть точек возврата.