Пример. Найти сумму первых 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.          /* Связь между задачами */

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

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

Тема «Структуры данных: списки. Основные предикаты

работы со списками. Решение задач с помощью списков.

Задачи, решаемые с помощью перебора»

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