Информатика. Алгоритмы в Паскале – Pascal - 1. Рекурсивные алгоритмы.

Алгоритмы в Паскале – Pascal - 1. Рекурсивные алгоритмы.

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

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

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

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

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

Рекурсия и итерация. 

Рекурсивную программу всегда можно преобразовать в нерекурсивную (итеративную, использующую циклы), которая выполняет те же вычисления. И наоборот, используя рекурсию, любое вычисление, предполагающее использование циклов, можно реализовать, не прибегая к циклам.

К примеру, вычисление факториала и чисел Фибоначчи можно реализовать без рекурсии:

При выполнении рекурсивной подпрограммы сначала происходит «рекурсивное погружение», а затем «возврат вычисленных результатов». Например, вычисление 5! при помощи вызова Fact(5) будет происходить следующим образом:

Fact(5) ® 5 * Fact(4)                     5 * 24    ®   120                  ¯                             ­               4* Fact(3)                   4 * 6                    ¯                           ­                 3 * Fact(2)                3 * 2                        ¯                        ­                    2 * Fact(1)             2 * 1                          ¯                     ­                          1          ®         1 

Как видно на примере вычисления 5!, при «рекурсивном погружении» функция Fact вызывает точно такой же новый экземпляр самой себя. При этом сама функция как бы еще не завершилась, а новый ее экземпляр уже начинает работать. И только когда новый экземпляр завершит работу («вернет вычисленные результаты»), будет продолжена работа самой функции.

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

В том числе процедура может вызвать саму себя. Никакого парадокса здесь нет – компьютер лишь последовательно выполняет встретившиеся ему в программе команды и, если встречается вызов процедуры, просто начинает выполнять эту процедуру. Без разницы, какая процедура дала команду это делать.

Пример рекурсивной процедуры:

Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3).

Ниже представлена блок-схема, показывающая последовательность выполнения операторов.

Рис. 1. Блок схема работы рекурсивной процедуры.

Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии.

Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3.

Еще один визуальный образ происходящего представлен на рис. 2.

Рис. 2. Выполнение процедуры Rec с параметром 3 состоит из выполнения процедуры Rec с параметром 2 и печати числа 3. В свою очередь выполнение процедуры Rec с параметром 2 состоит из выполнения процедуры Rec с параметром 1 и печати числа 2. И т. д.

В качестве самостоятельного упражнения подумайте, что получится при вызове Rec(4). Также подумайте, что получится при вызове описанной ниже процедуры Rec2(4), где операторы поменялись местами.

Обратите внимание, что в приведенных примерах рекурсивный вызов стоит внутри условного оператора. Это необходимое условие для того, чтобы рекурсия когда-нибудь закончилась. Также обратите внимание, что сама себя процедура вызывает с другим параметром, не таким, с каким была вызвана она сама. Если в процедуре не используются глобальные переменные, то это также необходимо, чтобы рекурсия не продолжалась до бесконечности.

Рекуррентное соотношение – это рекурсивная функция с целочисленными значениями.

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

Рекуррентные выражения используются, в частности, для определения сложности рекурсивных вычислений.

Например, пусть мы пытаемся вычислить числа Фибоначчи по рекурсивной схеме

F(i) = F(i-1) + F(i-2), при N >= 1; F(0) = 1; F(1) = 1;

с помощью указанной выше рекурсивной подпрограммы-функции F(n).

Требующееся при вычислении значения F(N) по такой схеме количество рекурсивных вызовов может быть получено из решения рекуррентного выражения

T_N = T_N-1 + T_N-2, при N >= 1; T₀ = 1; T₁ = 1

T_N приблизительно равно Ф^N , где Ф »1.618 - золотая пропорция («золотое сечение»), т.е. приведенная выше программа потребует экспоненциальных временных затрат на вычисления.