2. Рекурсивные алгоритмы и подпрограммы

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

Рекурсивным называется любой объект, который частично определяется через себя.

Например, приведенное ниже определение двоичного кода является рекурсивным:

<двоичный код> ::= <двоичная цифра> | <двоичный код><двоичная цифра>

<двоичная цифра> ::= 0 | 1

Здесь для описания понятия были использованы, так называемые, металингвистический формулы Бэкуса-Наура (язык БНФ); знак "::=" обозначает "по определению есть", знак "|" — "или".

Вообще, в рекурсивном определении должно присутствовать ограничение, граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.

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

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

Категории задач, допускающие рекурсивные определения:

1. Задачи, математические модели которых записываются в виде рекурсивно определенных функций.

2. Структура данных задачи определяется рекурсивным образом. Например: графы, деревья, списки.

3. Методы решения задачи допускают рекурсивное определение (игры, головоломки и др.).

Рекурсивные алгоритмы реализуются в виде подпрограмм, которые определяются в программе, как процедуры или функции.

Подпрограмма называется рекурсивной, если в ее определении присутствует прямо или косвенно вызов самой определяемой подпрограммы.

Явная рекурсия характеризуется существованием в определении подпрограммы оператора обращения к ней самой.

Неявная (косвенная) рекурсия характеризуется тем, что одна подпрограмма обращается к другой, которая через цепочку вызовов других подпрограмм рекурсивно обращается к первой.

3. Примеры рекурсивных программ

В ряде случаев рекурсивную подпрограмму можно построить непосредственно из формального математического описания задачи.

 

Факториал
	0! = 0. n! = n ∙ (n – 1)!, при n > 0.	Function Fact(n:byte):longint; begin if n=0 then Fact:=1 else Fact:=n*Fact(n-1) end;
Числа Фибоначчи
	Ф0 = 1. Ф1 = 2. Фn = Фn-1 + Фn-2, при n > 1.	Function F(n:byte):longint; begin if n <= 1 then F:=1 else F:= F(n-1)+F(n-2) еnd;