Одна важная проблема, на которую следует обращать внимание в рекурсивных определениях, - это левосторонняя рекурсия. Она возникает в случае, когда правило порождает подцель, по существу эквивалентную исходной цели, которая явилась причиной использования этого правила. Так, если бы мы определили предикат
человек(X):- человек(Y), мать(Х,Y).
человек(адам).
и ввели вопрос
?- человек(X).
то Пролог сначала использовал бы правило и рекурсивно породил подцель человек (Y). Попытка найти соответствие этой цели вновь привела бы к выбору первого правила и породила бы еще одну новую эквивалентную подцель. И так далее, до тех пор, пока не исчерпались бы вычислительные ресурсы. Конечно, если бы была возможность использовать механизм возврата, то был бы найден сообщенный в определении факт об Адаме и началось бы порождение решений>[7]. Ошибка заключается в том, что для того, чтобы начался возврат, Пролог должен потерпеть неудачу при проверке первого утверждения. В данном же случае поиск решения оказывается неопределенно длинным, и нет никакой возможности завершить этот поиск с успехом либо с неудачей. Из всего сказанного выше можно извлечь следующую мораль:
Не следует предполагать, что только потому, что вы предоставили все относящиеся к делу факты и правила, Пролог всегда найдет их. Создавая программу на Прологе, вы все время должны представлять, каким образом Пролог осуществляет поиск в базе данных и какие переменные будут конкретизированы, когда будет использовано одно из ваших правил.
Для приведенного примера имеется простой способ устранения ошибки – поместить факт перед правилом, а не после него. В действительности существует хороший эвристический принцип: помещать, где это возможно, факты перед правилами. Иногда при размещении правил в некотором конкретном порядке может возникнуть ситуация, когда они будут правильно работать для целей одного вида и не будут работать для целей другого вида. Рассмотрим следующее определение предиката список (X), при котором предикат список является истинным, если X – список, последний элемент которого имеет в качестве хвоста пустой список:
список([A|B]):- список(B).
список([]).
Если мы используем эти правила для получения ответов на вопросы, подобные следующим:
?- список ([a,b,c,d]).
?- список([]).
?- список(f(1,2,3))
то данное определение будет работать хорошо. Но если мы сделаем запрос
?- список(X).
то программа зациклится. Предикат, аналогичный предикату
