Решим задачу нахождения степени числа с помощью рекурсии.

Рекурсивное определение функции, вычисляющей степень числа таково:

ЧИСЛО x В СТЕПЕНИ y - есть ЧИСЛО x В СТЕПЕНИ y-1, УМНОЖЕННОЕ НА САМО ЧИСЛО x.

Например, два в пятой это два в четвертой, умноженное на два.

Переведем эту мысль с русского на прологовский:

В программе используется трехаргументный предикат st; в котором первый аргумент (входной) - это число, возводимое в степень; второй аргумент (входной) - это степень, в которую возводится число; третий аргумент (выходной) - ответ.

Зададим Прологу цель - st(2,5,Z).

Когда Пролог будет унифицировать эту цель, то произойдет рекурсивный вызов цели st(2,4,ZZ). Что в свою очередь приведет к рекурсивному цели st(2,3,ZZ) и так далее. Если рекурсивный вызов ничем не ограничивать, то он уёдет в область отрицательных чисел.

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

ЛЮБОЕ ЧИСЛО x В СТЕПЕНИ 1 - есть ЧИСЛО x.

Переведем эту мысль с русского на прологовский:

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

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

В ходе унификации исходной цели st(2,5,Z) на такой программе Пролог сначала попробует произвести унификацию первого предложения. Такая попытка закончится неудачей, так как второй аргумент в предложении указан "1", а в цели второй аргумент заявлен как "5". Тогда Пролог перейдет к унификации второго предложения, где и будет осуществлен рекурсивный вызов с изменненным значением второго аргумента. Процесс унификации новой цели st(2,4,ZZ) снова будет начат с первого предложения, где опять законцчится неудачей. Что приведет Пролог к необходимости рассмотрения второго предложения. Путем таких рекурсивных вызовов Пролог постепенно (начиная от 5 через 4,3,2) доберется до значения второго аргумента равного 1. После чего уже будет унифицировано первое предложение. Это приведет к присвоению третьему аргументу значения первого - именно так обозначено в первом предложении: st(X,1,X).

Достигнутая цель запустит обратный ход рекурсии, который будет представлен последовательным выполнением третьей подцели второго предложения Z=ZZ*X всех шагов рекурсии в обратном порядке от 1 до 5.

То есть после срабатывания базиса рекурсии первое такое выполнение будет таким: Z=2*2. И Пролог уже узнает не только чему равно два в первой, но и чему равно два во второй степени.

Обратный ход рекурсии будет продолжаться до унификации основной цели st(2,5,Z), после чего ответ будет выдан на экран:

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

Дело в том, что запрос st(2,1,ZZ) может быть унифицирован не только в первом предложении, но во втором. Ведь там на это не наложено никаких ограничений. Это приводит к тому, что Пролог все таки уходит в область отрицательных значений. И продолжает это до тех пор пока не происходит переполнение стека.

Ну что же - добавим ограничение:

Дополнительное условие не позволит проводить унификацию цели на втором предложении если второй аргумент меньше или равен единице.

Возможен и такой вариант:

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

Обычно для останова рекурсии используют именно предикат отсечение.