Тема «Рекурсия на Прологе (нисходящая стратегия). Ручная трассировка рекурсивных программ. Решение задач на символьную арифметику. Рекурсия: восходящая стратегия»

На Прологе рекурсивный метод является единственным способом решения задач с помощью минимального количества определений, повторяющихся в процессе поиска утверждений (подобно команде повторения в процедурных языках). Трудность в его понимании объясняется недостаточной методической проработкой. Как правило, в руководствах метод не объясняется, а показывается на примере единственной функции факториал (кстати, почти не используемой в школьном курсе математики).

Суть метода можно разъяснить следующим образом: если решение исходной задачи может быть сведено к решению другой (как правило, более простой) подзадачи, причем эта подзадача есть уменьшенный вариант исходной задачи (с таким же количеством исходных данных и результатов) и также сводима к другой подзадаче, то этот процесс называется рекурсией. Надо заметить, что способ разбиения и решения подзадачи идентичен примененному к исходной задаче.

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

Из этого объяснения следует, что для того чтобы решить зада-^ЧУ рекурсивно, необходимо:

а) определить связь между исходной и вспомогательной задачей;

б) определить граничное условие.

Пример.Найти сумму первых N натуральных чисел рекурсивным методом.

Заметим, что результат есть функция, зависящая от количества натуральных чисел S(N), которая выражается так:

Первые (N — 1) слагаемых есть результат такой же функции от (N - 1) членов. Значит, это — вспомогательная задача, которая удовлетворяет условиям рекурсивного метода. Граничное условие запишется так: S(1) = 1. Таким образом, математическая формулировка задачи имеет вид:

Теперь решение задачи нетрудно записать на Прологе:

сумма(1,1):-!. /* Граничное условие, S(N)=1 */

сумма(N,S):-M is N-l, /* M=N-1 */

сумма(M,S), /* Вспомогательная задача */

S is C+N. /* Связь между задачами */

Стратегия, использованная при решении данной задачи, имеет название восходящей. Для полного понимания метода рекомендуется исполнять некоторые программы в режиме ручной трассировки. Кроме того, необходимо на первых этапах усвоения материала записывать на Прологе функции, выраженные в математической форме. В рамках темы можно решить ряд задач, получивших название «Символьная арифметика». При этом преследуют следующие цели: во-первых, более глубоко понять природу рекурсивных функций, во-вторых, уяснить, что в определении арифметических операций лежит рекурсивный метод.

Восходящая стратегия является разновидностью рекурсивного метода. В основе лежит следующая идея: от граничного условия решать задачи большего размера. Для этого вводятся два дополнительных параметра — размер решенной задачи и промежуточный результат. С помощью этой стратегии, как правило, решаются переборные задачи.