Основы программирования на языке Пролог



         

Рекурсия - часть 10


После того, как этот предикат выдаст те же ответы, что и исходный предикат предок, он зациклится и в итоге выдаст сообщение о том, что стек переполнен.

С оригинальным предикатом предок этого не происходило, потому что в его втором правиле первой подцелью стоял вызов подцели родитель. В результате выполнения этой подцели переменная Человек получала в качестве значения имя какого-то человека. Поэтому в момент вызова второй подцели предок(Человек,Потомок) переменная Человек была уже связанной. В новой же версии предиката второе правило начинается с вызова подцели предок2(Человек,Потомок), причем переменная Человек в ней свободна. После того, как будут исчерпаны все альтернативы для означивания свободных переменных через первое предложение процедуры, подцель будет унифицироваться с заголовком второго предложения. Свободная переменная Человек будет связана с переменной Предок, а переменная Потомок подцели - с переменной Потомок заголовка правила. При попытке выполнить первую подцель правила все повторится. Этот процесс будет продолжаться до тех пор, пока не будет исчерпано все свободное пространство стека.

Такой вид рекурсии, когда тело правила начинается с рекурсивного вызова определяемого предиката, называется левосторонней рекурсией. С левосторонней рекурсией очень часто возникают описанные проблемы. Поэтому нужно стараться, если возможно, избегать использования левосторонней рекурсии, в отличие от правосторонней или хвостовой рекурсии.




Содержание  Назад  Вперед