|
В случае с Ханойской башней, следовательно, только указатель выполнения реально нуждается в стеке.
Теперь мы обладаем базовыми элементами для представления рекурсии: использование стеков и отыскание обратных преобразований. Несколько ниже мы приведем примеры, в которых представление рекурсии может быть упрощено; пока же нам известно достаточно для того, чтобы записывать правила реализации, необязательно оптимальные, но всегда приводящие к правильным результатам.
Рассмотрим некоторые простые примеры рекурсивных процедур.
Пример 1. Программа определения суммы ряда натуральных чисел.
sum_series(1,1).
sum_series(N,S):¾N>0,Next is N-1, sum_series(Next,S1), S is N+S1.
? ¾ sum_series(6,S).
S=21.
YES
Пример 2. Программа генерации ряда натуральных чисел от N до 20.
write_number (20) :¾write(20).
write_number(N):¾ N<20,write(N),nl,Next is N-1, write_number (Next).
? ¾write_number(15).
15
16
17
18
19
20
YES
Для представления формализованной схемы поиска решений будут использоваться следующие обозначения:
1) ТР ¾текущая резольвента. Первой ТР является исходный вопрос. Каждая следующая резольвента ТР получается путем редукции, т. е. замены самой левой цели в предыдущей резольвенте на тело правила, заголовок которого сопоставим с целью, или путем удаления цели. Если цель сопоставима с фактом, и в том и другом случае вырабатывается подстановка и применяется ко всей ТР.
2) Шаг № ¾ шаг вычисления. Шагом вычислений будем считать действия, выполняемые после определения ТР и заканчивающиеся построением новой ТР или выводом об успехе/неудаче.
3) ТЦ ¾текущая цель. Текущая цель ¾ это цель, подлежащая согласованию на данном шаге.
4) Пр № ¾ правило, применимое для редукции на определенном шаге.
5) Успех¾ вывод об успешном вычислении вопроса. Неудача¾ вывод о неуспешном вычислении вопроса.
6) Отказ, возврат. Отказ ¾ это отказ пользователя от выданного успешного ответа на вопрос, механизм возврата включается принудительно. Возврат ¾ это тупиковая ситуация во время вычисления вопроса, механизм возврата включается автоматически.
7) Так как при рекурсивном обращении к правилу создаются новые экземпляры переменных, будем на каждом шаге добавлять к именам переменных индекс в виде номера шага.
Рассмотрим пример классической рекурсивной процедуры вычисления факториала; эта процедура включает два правила:
fact(1,1). %Пр1
fact(N,Res):¾N>1,N1 is N-1,fact(N1,Res1),Res is N*Res1. %Пр2
Схема вычисления запроса
?¾ fact(3, Res).
имеет следующий вид:
ТР: fact(3,Res).
Шаг 1: ТЦ: fact(3,Res).
Пр1: 3=1Þno
Пр2: 3>1,N11 is 3-1, fact(N11,Res11),Res is Res11*3.
ТР: fact(2,Res11), Res is Res11*3.
Шаг 2: ТЦ: fact(2,Res11).
Пр1: 2=1Þno
Пр2: 2>1,N12 is 2-1, fact(N12,Res12),Res11 is Res12*2.
ТР: fact(1,Res12), Res11 is Res12*2 ,Res is Res11*3.
Шаг 3: ТЦ: fact(1,Res12).
Пр1: 1=1Þyes
{Res12=1}
ТР: Res11 is Res12*2 ,Res is Res11*3.
Шаг 4: ТЦ: Res11 is 1*2.
{Res11=2}
ТР: Res is 2*3.
Шаг 5: ТЦ: Res is Res11*3.
{Res=6}
ТР: ÿ (пустая резольвента)
{Res=6}
Успех
| 
