Рекурсивные алгоритмы. Примеры рекурсивных алгоритмов.

Рекурсия - это способ определения объектов (понятий), при котором определение объекта строится, опираясь на само понятие объекта.

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

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

Категории задач, допускающие рекурсивные определения:
1. Задачи, математические модели которых записываются в виде рекурсивно определенных функций. Классический пример функции, определение которой может задаваться в рекурсивной форме F(n)=n!

Function factorial (n: byte) : byte;

Begin

If n=0 then factorial:= 1;

Else factorial = factorial (n-1) *n;

End;

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

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

Для оценки объема рекурсии вводится понятие глубины – число промежуточных вычислений функции в процессе ее вычисления для данного аргумента. Не всегда является очевидной.

Подобно операторам цикла, рекурсивыне процедуры могут приводить к незаканчивающимся вычислениям. Очевидно основное требование – чтобы рекурсивное обращение к P управлялось некоторым условием B, которое в какой-то момент становится ложным. Основной способ доказательства конечности некоторого повторяющегося процесса: 1.Определяется ф-я f(x) (х – множество переменных), т.ч. из f(x)≤0 следует истинность условия окончания цикла. 2.Доказывается, что при каждом проходении цикла f(x) уменьшается.

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

Не всегда рекурсивное решение задачи является лучшим, более простые решения могут быть найдены с помощью итерации. Итерация - способ организации обработки данных, при котором определенные действия повторяются многократно, не приводя при этом к рекурсивным вызовам программ. Итерация – частный вид рекурсии. При итерационном исчислении происходит последовательное накопление рез-та. Это пример, когда рекурсию исп-ть нецелесообразно. Итерат. Процедура более эф-на, чем рекурсивная и требует меньше памяти

Пример итерации

Procedure F(i: integer): integer;

Int F:integer;j:integer;

Begin

p:=1;

For I=1 to I do p:=p*j;

F:=p;

End;