Рекурсивные процедуры

Другой способ использования повторений - рекурсия. Рекурсивная про-

цедура - это процедура, которая вызывает сама себя. В рекурсивной проце-

дуре нет учета ее выполнения, потому что обратные, общие или промежуточ-

ные результаты можно передавать из одного вызова в другой как независимые

аргументы.

Логика рекурсии проста для осуществления, даже если вы забыли в дан-

ный момент, как работает компьютер. (Пролог так отличается от машинного

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

данный момент). Забудьте, что компьютер последовательно проходит адреса

памяти и представьте себе ЭВМ способную понимать, например, такие рецеп-

ты:

Найти факториал числа N:

Если N равно 1, то факториал равен 1.

Иначе найти факториал N-1 и умножить его на N.

Этот рецепт означает следующее: чтобы найти факториал 3, вы должны

найти факториал 2, а чтобы найти факториал 2, вы должны вычислить факто-

риал 1. Вы можете найти факториал 1 без обращения к другим факториалам,

поэтому повторения не начнуться. Если у Вас есть факториал 1, то умножае-

те его на 2, чтобы получить факториал 2, а затем, умножаете полученное на

3, чтобы получить факториал 3.

В Турбо Прологе это выглядит так:

factorial(1, 1) :-!.

factorial(X, FactX) :-

Y = X-1,

factorial(Y, FactY),

FactX = X*FactY.

Полностью выполнение этого рецепта будет выглядеть следующим обра-

зом:

/* Программа CH07EX03.PRО */

/* Рекурсивная программа вычисления факториалов.

Рекурсия обычная, не хвостовая.*/

predicates

factorial(inteqer, real)

clauses

factorial(1, 1) :- !.

factorial(X, FactX) :-

Y = X-1,

factorial (Y, FactY),

FactX = X*FactY.

Что же все-таки делает компьютер?

- Минуту, - скажите вы. Но как компьютер выполняет предикат

factorial в середине обработки? Если вы вызываете факториал с X = 3, то

затем этот предикат обратится к X = 2. Будет ли он иметь два значения пе-

ременной, или второе значение стирает первое?

Дело в том, что компьютер создает новую копию предиката factorial

таким образом, что он становится способным вызывать сам себя как пол-

ностью самостоятельную процедуру. При этом, конечно, код выполнения не

будет копироваться, но все аргументы и промежуточные переменные копируют-

ся.

Информация хранится в области памяти называемой "стек", которая соз-

дается каждый раз при вызове правила. Когда выполнение правила завершает-

ся, занятая его стеком память возвращается общему объему памяти, и выпол-

нение продолжается со стеком, который использовался перед вызовом.

Дело в том, что компьютер создает новую копию предиката factorial

таким образом, что он становится способным вызывать сам себя как пол-

ностью самостоятельную процедуру. При этом, конечно, код выполнения не

будет копироваться, но все аргументы и промежуточные переменные копируют-

ся.

Информация хранится в области памяти называемой "стек", которая соз-

дается каждый раз при вызове правила. Когда выполнение правила завершает-

ся, занятая его стеком память возвращается общему объему памяти, и выпол-

нение продолжается со стеком, который использовался перед вызовом.