Программа «Сумма ряда целых чисел от 1 до 7» - демонстрация обобщенного правила рекурсии. Программа суммирует числа от 1 до 7. S(7) = 7+6+5+4+3+2+1 = 28

Программа начинается с попытки выполнить подцель sum_series(7,Sum) в разделе goal. Сначала программа пытается сопоставить подцель с подправилом sum_series(1,1). Сопоставление неудачно.

Затем программа пытается сопоставить подцель sum_series(7,Sum) с sum_series(Number,Sum). На этот раз сопоставление завершается успешно с присвоением переменной Number значения 7.

Затем программа сравнивает значение Number, которое равно 7, с 0, т.е. проверяется условие выхода. Так как 7 больше 0, то сопоставление успешно, программа переходит к следующему подправилу. Для этого подправила переменной Next_number присвоено значение 6, т.е. значение Number - 1. Затем правило вызывает само себя в виде sum_series(6,Partial_Sum).

Следующим подправилом является правило Sum, содержащее свободную переменную Partial_Sum. Так как только что был вызван рекурсивный процесс, то правило Sum не может быть вызвано.

Теперь программа пытается сопоставить неизменяемое правило sum_series(1,1) с sum_series(6,Partial_Sum). Процесс сопоставления неуспешен, поскольку несопоставим ни один из параметров.

В результате программа переходит к следующему правилу с головой sum_series(Number,Sum), присваивая переменной Number значение 6. Этот циклический процесс сопоставления продолжается до тех пор, пока не будет получено sum_series(1,Partial_Sum). Теперь это правило сопоставляется с sum_series(1,1), а Partial_Sum приписывается значение 1.

При сопоставлении правила с головой правила переменная Sum получает значение 1. Так как сопоставление продолжается дальше, то Next_number получает значение 0 (1 - 1). При следующем цикле сопоставления переменная Number получает значение 0. Во время сопоставления с условием выхода правило оказывается неуспешным, и сопоставление «прыгает» к правилу Sum.

Во время процесса сопоставления переменная Partial_Sum была свободна, а программа запоминала значения Number для последующего использования. Но это правило продолжает означивать переменную Sum, присваивая ей последовательно значения 1, 3, 6, 10, 15, 21 и 28. То есть из стека извлекаются значения Number в качестве списка параметров для последнего подправила после того, как рекурсия была остановлена.

Конечное значение Sum есть 28.

/*Правило рекурсии программы выполняет вычисления по обычной схеме сложения:
1. Начальное значение
2. Следующее значение
3. Частичная сумма
3. Следующее значение
6. Частичная сумма
 ...
 
Среда - EZY Prolog */
 
domains
 
number, sum = integer
 
predicates
 
sum_series(number, sum)
 
clauses
 
/* Неизменяемое правило */
sum_series(1,1).   /* сумма ряда */
 
/* Правило имеет четыре компоненты и одно дополнительное нерекурсивное правило Sum. */
sum_series(Number,Sum) :- Number > 0,write("1 - Number = ", Number),nl,
Next_number = Number - 1,write("2 - Next_number = ", Next_number),nl,
sum_series(Next_number, Partial_Sum),write("3 - Number = ", Number), nl, write("3 - Partial_Sum = ", Partial_Sum),nl,
Sum = Number + Partial_Sum,write("4 - Sum = ", Sum),nl,write("4 - Number = ", Number),write("4 - Partial_Sum = ", Partial_Sum), nl, nl. /* Последняя компонента правила рекурсии - это нерекурсивное правило Sum с Partial_Sum (частичная сумма) в качестве переменной.
Это правило не может быть выполнено до тех пор, пока Partial_Sum не получит некоторого значения. */
 
goal
 
sum_series(7,Sum),nl, /* первая подцель */
write("Сумма ряда:"),nl,nl,
write(" S(7) = ", Sum), nl.

Результат:

Сумма ряда:
S(7) = 28

Модификация выполнена посредством удаления условия выхода Number > 0 и введения правила sum_series(1,1) :- !. вместо sum_series(1,1).

Результаты работы этих правил идентичны. Использование отсечения (!) в правиле sum_series(1,1) :- !. не улучшает работы правила рекурсии. Эти два правила следует рассматривать как альтернативные варианты.

/* Среда - EZY Prolog */
 
domains
 
number, sum = integer
 
predicates
 
sum_series(number, sum)
 
clauses
 
sum_series(1,1) :-!.   /* сумма ряда */
 
/* Правило имеет три компоненты и одно дополнительное нерекурсивное правило Sum. */
sum_series(Number,Sum) :- write("1 - Number = ", Number),nl,
Next_number = Number - 1,write("2 - Next_number = ", Next_number),nl,
sum_series(Next_number, Partial_Sum),write("3 - Number = ", Number), nl, write("3 - Partial_Sum = ", Partial_Sum),nl,
Sum = Number + Partial_Sum,write("4 - Sum = ", Sum),nl,write("4 - Number = ", Number),write("4 - Partial_Sum = ", Partial_Sum), nl, nl. /* Последняя компонента правила рекурсии - это нерекурсивное правило Sum с Partial_Sum (частичная сумма) в качестве переменной.
Это правило не может быть выполнено до тех пор, пока Partial_Sum не получит некоторого значения. */
 
goal
 
sum_series(7,Sum),nl, /* первая подцель */
write("Сумма ряда:"),nl,nl,
write(" S(7) = ", Sum), nl.

Результат:

Сумма ряда:
S(7) = 28

!!Рекомендуем: Семейная Энциклопедия Здоровья ⇒ Что должен знать современный человек? ⇒ Самоанализ. Работа над собой ⇒ Оглавление ⇒ Главная сайта