Рекурсия
.
С понятием рекурсии мы уже встречались: рекуррентные соотношения довольно часто встречаются в математических выражениях. Рекурсия в определении состоит в том, что определяемое понятие определяется через само это понятие. Примером здесь может служить определение высказывания (см. лекция 5, определение 5.1). Рекурсия в вычислениях выступает в форме рекуррентных соотношений, которые показывают, как вычислить очередное значение, используя предыдущие.
Например, рекуррентное соотношение
xi=xi-2+xi-1 , где x1=1 , x2=2
задает правило вычисления так называемых чисел Фибоначчи.
Другим примером рекуррентных соотношений могут служить правила вычисления членов арифметической прогрессии
an+1=an+d , где d - разность прогрессии,
либо геометрической прогрессии
an+1=qan , где q - коэффициент прогрессии.
Эта идея рекурсии реализована и в языке Pascal.
Определение 16.1. Функция (процедура) на языке Pascal называется рекурсивной, если в ходе своего выполнения она обращается к самой себе.
Например, мы можем определить вычисление функции n!
рекурсивно. Как это сделать, показано на рисунке 16.1
function Factorial (n : integer) : integer ;
begin if n>0 then Factorial:=Factorial (n-1)*n
else if n=0 then Factorial:=1
elsewriteln (’значение n меньше 0’)
end {Factorial}
Рис. 16.1. Функция вычисления n! в рекурсивной форме.
Рассмотрим подробно, как будет выполняться обращение к этой функции, напрмер, при n=4.
На рисунке 16.2 показан процесс вычисления для случая Factorial(4).
| Цикл | Рекурсия |
| while Условие Циклаdo Тело Цикла | Procedure РекурсивныйЦикл ; begin if УсловиеЦикла then begin ТелоЦикла;Рекурсивный Циклelse{окончание рекурсии}end |
Рис. 16.4. Схема организации цикла вида whiledo
и его рекурсивного эквивалента.
Обратите внимание, что в правой части рис. 16.4 возможно зацикливание! Надо быть очень осторожным и всякий раз, применяя рекурсивную поцедуру или функцию, убедиться в их корректном завершении. Рассмотрим пример. На рисунке 16.5 приведен алгоритм Евклида, с которым мы познакомились на лекции 1, для вычисления НОД (наибольшего общего делителя) в форме обычной и рекурсивной функции на языке Pascal.
Function НОД (a, b : integer) : integer ;
| begin repeat if a > b then a:=a-b else b:=b-a untile a = b;НОД:=aend | begin if a = b then НОД:=a; if a > b then НОД:=НОД(a-b, b); else НОД:=НОД(b-a , a);end |
Рис. 16.5. Циклическая и рекурсивная функции
для вычисления НОД.
Как видно из приведенных примеров на рисунках 16.1 и 16.5, итерация, т.е. цикл всегда может быть заменен его рекурсивным аналогом по схеме, показанной на рисунке 16.4.
С обратным утверждением о замене рекурсии итерацией все сложнее. На рисунке 16.6 приведен пример рекурсивной функции, где по схеме (рис. 16.4) рекурсию итерацией заменить не удается.
в остальных случаях
Рис. 16.6. Рекурсивная функция Аккермана.
Способы повторного использования процедур и функций.
Итак, процесс абстракции в форме процедуры состоит из трех шагов:
Именование. Присвоить рутинному алгоритму уникальное имя, которое затем будем использовать как имя соответствующей процедуры.
Определить пред- и постусловия для создаваемой процедуры или функции в соответствии с контекстом их использования в основной программе.
Параметризиовать процедуру. (Везде далее, если явно не оговорено, говоря о процедурах, будем иметь в виду также и функции). Для этого часть предусловия и постусловия в спецификации оформить в виде параметров соответствующего типа, часть из которых будет доставлять исходные данные, а другая часть - результаты работы процедуры.
Обобщить типы параметров. Проанализировать все места в программе, где будет обращение к данной процедуре на предмет, какие типы данных используются в этих местах, как они соотносятся с типами параметров в процедуре. Назовем совокупность типов данных в месте вызова процедуры контекстом обращения к процедуре Определить типы параметров так, чтобы они соответствовали как можно большему числу контекстов обращений к процедуре.
Реализовать получившуюся абстракцию рутинного алгоритма либо в форме процедуры, либо функции.
Мы не в праве ожидать, что выделенные нами уже существующие функции или процедуры, которые могут быть нам полезны для создания нашей новой программы, мы сможем использовать в том виде, как они есть. Есть четыре основных способа адаптации или повторного использования уже существующих рутинных алгоритмов и процедур для новых целей. Это - присоединение, вложение, настройка и слияние.
Присоединение. Этот способ предполагает, что если у нас есть процедура P1c предусловием Q1 и постусловием R1 и процедура P2c пред-и c постусловиями Q2 и R2 соответственно, (причем R1ÞQ2) , то мы можем построить процедуру Pc предусловием Q1 и постусловием R2 последовательно соеденив Р1 и P2 так, как показано на рис.16.7.
P {Q1}
| {Q1} Р1 {R1} |
{R1ÞQ2}
| {Q2} Р2 {R2} |
{R2}
Рис. 16.7. Присоединение процедур Р1 и P2 .
Вложение. Этот способ применяется, когда новая процедура P образуется вложением известной процедуры P2 внутрь другой известной процедуры P1. Вложение возникает либо когда мы явно вставляем P2 как тело цикла или как альтернативу в теле процедуры P1 , либо когда P2 - это параметр для P1 .
Настройка. Суть этого способа состоит в том, что существующую процедуру Р1 мы либо обобщаем, либо, наоборот, сужаем в соответствии со спецификацией Р.
Например, если у нас есть процедура выбора максимального числа из массива из 100 натуральных чисел, то легко ее можем обобщить на случай массива из 1000 целочисленных компонентов.
Слияние. Этот способ построения новой процедуры Р за счет слияния, объединения двух существующих процедур Р1 и P2 .
Например, пусть процедура Р1 выбирает максимальное, а P2 - минимальное значения в массиве из 100 целых чисел. Тогда, объединив операторы процедуры Р1 и процедуры P2 в надлежащем порядке, мы получим процедуру Р , выбирающую max и min из 100 целых чисел.