Рекурсия. Множество предложений, имеющих в заголовке предикат с одним и тем же именем и одинаковым количеством аргументов

Множество предложений, имеющих в заголовке предикат с одним и тем же именем и одинаковым количеством аргументов, трактуются как процедура. Для процедурной модели важен порядок, в котором записаны предложения и условия в предложениях.

В отличие от традиционных языков программирования, в которых основным средством организации повторяющихся действий являются циклы, в Прологе используются процедура поиска с возвратом (откат) и рекурсия. Откат даёт возможность получить много решений в одном вопросе к программе, а рекурсия позволяет использовать в процессе определения предиката его самого. Рекурсию используют не только в Прологе, но и в остальных языках программирования. Но в Прологе в отличие от остальных языков рекурсия является основным приемом программирования.

Предикат родитель имеет 2 аргумента. В качестве первого указывается имя родителя, а в качестве второго имя ребенка. Получить отношение – быть предком. Для того, чтобы один человек был предком другого человека, нужно, чтобы он был его родителем, либо являлся родителем другого его предка.

Отношение предок является транзитивным замыканиемотношения родитель, то есть это наименьшее отношение, включающее отношение родитель и обладающее свойством транзитивности.

Базис рекурсии – это предложение, определяющее некоторую начальную ситуацию или ситуацию в момент прекращения.

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

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

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

Попробуем записать реализацию предиката, эквивалентную математическому определению предиката:

Данных пример с ошибкой – переполнится стек.

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

Второй вариант решения проблемы - добавить в первое предложение процедуры отсечение.

Существует вариант рекурсии, который использует столько же оперативной памяти сколько и обычные языки – хвостовая (правая рекурсия). Для ее осуществления рекурсивный вызов определяемого предиката должен быть последней подцелью в теле рекурсивного правила и к моменту рекурсивного вызова не должно остаться точек возврата (непроверенных альтернатив). То есть у подцелей, расположенных левее рекурсивного вызова определяемого предиката, не должно оставаться каких-то непроверенных вариантов и у процедуры не должно быть предложений, расположенных ниже рекурсивного правила. Турбо Пролог, на который мы ориентируемся в нашем курсе, распознает хвостовую рекурсию и устраняет связанные с ней дополнительные расходы. Этот процесс называется оптимизацией хвостовой рекурсии или оптимизацией последнего вызова.

Вычисление факториала с использованием хвостовой рекурсии, добавим два дополнительных параметра, которые будут использоваться для хранения промежуточных результатов. Третий параметр нужен для хранения текущего натурального числа, для которого вычисляется факториал, четвертый параметр - для факториала числа, хранящегося в третьем параметре.

Остановить рекурсию можно, воспользовавшись отсечением в базисе рекурсии, как мы это делали ранее или добавив в начало второго предложение сравнение N1 с N.

Если мы решим, что вызвать предикат с 3 тремя аргументами неудобно, можно ввести дополнительный двухаргументный предикат, который будет запускать исходный предикат:

Циклы в Прологе:

Пример. Числа Фибоначчи. Базисов рекурсии в данном случае два. Первый будет утверждать, что первое число Фибоначчи равно единице. Второй базис - аналогичное утверждение про второе число Фибоначчи. Шаг рекурсии также будет необычным, поскольку будет опираться при вычислении следующего числа Фибоначчи не только на предшествующее ему число, но и на предшествующее предыдущему числу. В нем будет сформулировано, что для вычисления числа Фибоначчи с номером N сначала нужно вычислить и сложить числа Фибоначчи с номерами N-1 и N-2.

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

Несмотря на то, что предикат fib2 находит, в отличие от предиката fib, не одно число Фибоначчи, а сразу два, он использует намного меньше стекового пространства и работает во много раз быстрее. Для вычисления числа Фибоначчи с номером N (а заодно и N+1-го числа Фибоначчи) необходимо всего лишь N рекурсивных вызовов предиката fib2.

Если нам не нужно след. число, можно сделать последним аргументом анонимною переменную, и добавить след. предикат :

Обратите внимание, что если во втором правиле процедуры описан предикат предок, изменить порядок поцелей с декларативной точки зрения смысл остается прежним (левосторонняя рекурсия).

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

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