В заголовке отдельные параметры можно опускать (но только с начала списка), промежуточные параметры удалять нельзя, например:
procedure IntHandler(DI, ES, BP : Word) ; interupt ;
{ неправильный заголовок }
procedure IntHandler(DI, DS, ES, BP : Word) ; interupt ;
{ правильный заголовок }
Нельзя в заголовке процедуры обработки прерываний записывать и какие-либо другие параметры.
Рекурсивным называется объект, частично состоящий или определяемый с помощью самого себя. Факториал ¾ пример рекурсивного объекта. Факториал числа n определяется как произведение целых чисел от 1 до n и обозначается n!
Приведенное выражение можно переписать так:
Очевидно, что факториал числа n равен произведению числа n на факториал числа (n-1). В свою очередь, факториал числа (n-1) это произведение числа (n-1) на факториал числа (n-2) и т. д.
Таким образом, если вычисление факториала n реализовать как функцию, то в теле этой функции будет инструкция вызова функции вычисления факториала числа (n-1), т. е. функция будет вызывать сама себя. Такой способ вызова называется рекурсией, а функция, которая обращается сама к себе, называется рекурсивной функцией.
Пример. Вычисление факториала числа с использованием рекурсивной функции.
Program Example ;
Var
n : Integer ; { число, факториал которого надо вычислить }
f : Integer ; { факториал числа n }
Function factorial (k : integer ) : integer ;
begin
if k = 1 then factorial := 1
else factorial := k * factorial(k-1) ;
end ;
Begin { основная программа }
writeln(‘Вычисление факториала с использованием рекурсивной ‘,
‘функции.’) ;
write (‘ Введите число, факториал которого надо вычислить ->‘) ;
readln(n) ;
f := factorial (n) ;
writeln(‘Факториал числа ‘, n , ‘ равен ‘, f )
End.
Пример программы: поиск пути
Механизм рекурсии весьма эффективен при программировании задач поиска. В качестве примера рассмотрим задачу поиска пути между двумя городами. Если несколько городов соединены дорогами, то очевидно, что попасть из одного города в другой, проходя по каждой из дорог не более одного раза, можно по различным маршрутам. Задача состоит в том, что надо найти все возможные маршруты.
Карта дорог между городами может быть изображена в виде графа ¾ набора вершин, означающих города, и ребер, обозначающих дороги (рис. 25).
Рис. 25. Представление карты дорог между населенными пунктами в виде графа
Процесс поиска может быть представлен как последовательность шагов. На каждом шаге с использованием некоторого критерия выбирается точка, в которую можно попасть из текущей. Если очередная выбранная точка совпала с заданной конечной точкой, то маршрут найден. Если не совпала, то делаем еще шаг. Так как текущая точка может быть соединена с несколькими другими, то сначала будем выбирать точку с наименьшим номером.
Например, пусть надо найти все возможные пути из точки 1 в точку 5. Согласно принятому правилу, сначала выбираем точку 2. На следующем шаге выясняем, что точка 2 тупиковая, поэтому возвращаемся в точку 1 и делаем шаг в точку 3. Из точки 3 в точку 4, из 4 в 6 и из точки 6 в точку 5. Один маршрут найден. После этого возвращаемся в точку 6 и проверяем, возможен ли шаг в точку, отличную от 5. Так как это возможно, то делаем шаг в 7 и затем в 5. Найден еще один путь. Таким образом, процесс поиска состоит из шагов вперед и возвратов назад. Поиск завершается, если из узла начала движения уже некуда идти.
Алгоритм поиска имеет рекурсивный характер: чтобы сделать шаг, мы выбираем точку и опять делаем шаг, до тех пор пока не достигаем цели.
Таким образом, задача поиска маршрута может рассматриваться как задача выбора очередной точки (города) и поиска оставшейся части маршрута, т. е. имеет место рекурсия.
Граф можно представить двумерным массивом, который назовем map (карта). Значение элемента массива map[i,j] ¾ единица, если города i и j соединены прямой дорогой, или ноль, если города не соединены дорогой. Для приведенного графа массив map можно изобразить в виде таблицы так:
Содержимое ячейки таблицы на пересечении строки i и cтолбца j соответствует значению map[i,j].
Помимо массива map нам потребуется массив road (дорога) и массив incl (от слова include ¾ включать).
В road[i] мы будем записывать номера пройденных городов. В момент достижения конечной точки он будет содержать номера всех пройденных точек, т. е. описание маршрута.
В incl[i] будем записывать TRUE, если точка с номером i включена в маршрут. Делается это для того, чтобы не включать в маршрут уже пройденную точку (ходить по кругу).
Так как мы используем рекурсивную процедуру, то надо обратить особое внимание на условие завершения рекурсивного процесса. Процедура должна прекратить вызывать сама себя, если текущая точка совпала с заданной конечной точкой.
На рис. 26 приведена укрупненная блок-схема алгоритма процедуры выбора очередной точки формируемого маршрута.
