Factorial (integer, integer)

CLAUSES

%факториал 0! равен 1

factorial (0, 1):-!.

%факториал n! равен факториалу (n-1)!, умноженному на n

factorial (N, Factorial_N):- M=N-1, factorial (M, Factorial_M),

Factorial_N=Factorial_M*N.

GOAL

write ("Для какого числа Вы хотите найти факториал? "), readint (Number),

factorial (Number, Result), write (Number, "!=", Result).

Результат работы программы: 3!=6

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

Предположим, имеются некоторые абстрактные процедуры F1, F2, F3 и F4. Пусть в процессе выполнения процедуры F1 выполняется вызов процедуры F2, при выполнении которой, в свою очередь, вызывается процедура F3, которая, в свою очередь, вызывает F4. В этом случае стек вызовов будет выглядеть следующим образом:

Сохранять состояние вызывающей процедуры необходимо для того, чтобы продолжить ее выполнение после завершения вызова. Но, а если вызов процедур F2, F3 и F4 будет последним действием в вызывающих процедурах? Тогда можно не сохранять состояние вызывающей процедуры, так как в ней после завершения вызова больше ничего выполняться не будет. Можно хранить в стеке вызовов только состояние последней вызванной процедуры, другими словами подменять состояние бывшей процедуры состоянием новой процедуры.

То есть считать, что процедура F1 вызывает процедуру F4 непосредственно. В этом случае, не расходуется стек вызовов.

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

Выполнение таким образом организованной рекурсии не будет завершаться аварийно из-за переполнения стека, сколько бы ни было рекурсивных вызовов! Аварийное завершение по другим причинам, конечно, не исключается.

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

PREDICATES

tail_recursion

CLAUSES

%хвостовая рекурсия

tail_recursion:- write ("*"), tail_recursion.

GOAL

tail_recursion.

Теперь можно сформулировать условия, при соблюдении которых рекурсия в Prolog'е становится хвостовой, то есть не расходует стек при неограниченном количестве рекурсивных вызовов:

1. рекурсивный вызов должен быть последней целью в хвостовой части правила вывода.

2. перед рекурсивным вызовом не должно быть точек возврата (это условие хвостовой рекурсии специфично для Prolog'а).

Если первое условие очевидно, то необходимость выполнения второго условия может быть, на первый взгляд, не совсем понятна. Чтобы рекурсия была хвостовой, необходимо, чтобы доказательство рекурсивного вызова было действительно последним действием в хвостовой части правила. А если до рекурсивного вызова имеется цель, которую можно передоказать, то есть имеется точка возврата? Тогда придется сохранять в стеке состояние вызывающего правила! Вдруг в дальнейшем, где-то в глубинах рекурсии какая-либо цель не будет доказана? Тогда будет включен поиск с возвратом к ближайшей точке возврата, для чего и нужно сохранять состояние в стеке соответствующего правила (чтобы знать, куда вернуться).

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

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

 

Списки. Описание. Примеры типовых задач обработки: длина списка, членство в списке, склеивание списков, переворачивание списков.

Длина списка

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

length([], 0). /* в пустом списке элементов нет */

length([_|T], L):–

length(T, L_T), /* L_T — количество

элементов в хвосте */

L = L_T + 1. /* L — количество элементов

исходного списка */

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

Разберем на примере, как это будет работать. Пусть нас интересует количество элементов в списке [1,2,3]. Запишем соответствующий вопрос Пролог-системе:

length([1,2,3],X).

Система попытается вначале сопоставить нашу цель с первым предложением length([], 0), однако ей это не удается сделать, потому что первый аргумент цели является непустым списком. Система переходит ко второму предложению процедуры. Сопоставление с заголовком правила проходит успешно, переменная X связывается с переменной L, список [1,2,3] будет сопоставлен со списком [_|T], переменная T будет конкретизирована значением [2,3]. Теперь система переходит к попытке достижения подцелиlength(T,L_T). Как и в предыдущем случае, первое предложение с подцелью не сопоставляется, так как список T не пустой. При сопоставлении заголовка правила с подцелью хвост T конкретизируется одноэлементным списком [3]. На следующем шаге рекурсии переменная T означена пустым списком (хвост одноэлементного списка). И, значит, наша подцель выглядит следующим образом: length([], L_T). Эта цель сопоставляется с фактом, переменная L_Tстановится равной нулю. Раскручивается обратный ход рекурсии: переменная L_T увеличивается на единицу, результат попадает в переменную L. Получаем, что длина списка [3] равна единице. На следующем обратном шаге происходит еще одно добавление единицы, после чего длина списка [2,3] конкретизируется двойкой. И, наконец, на последнем возвратном шаге получаем означивание переменной L числом 3 (количеством элементов в списке [1,2,3]).