Реферат : Рекурсия (работа 1) 


Полнотекстовый поиск по базе:

Главная >> Реферат >> Информатика, программирование


Рекурсия (работа 1)




Рекурсия.

С понятием рекурсии мы уже встречались: рекуррентные соотношения довольно часто встречаются в математических выражениях. Рекурсия в определении состоит в том, что определяемое понятие определяется через само это понятие. Примером здесь может служить определение высказывания (см. лекция 5, определение 5.1). Рекурсия в вычислениях выступает в форме рекуррентных соотношений, которые показывают, как вычислить очередное значение, используя предыдущие.

Например, рекуррентное соотношение

xi=xi-2+xi-1 , где x1=1 , x2=2

задает правило вычисления так называемых чисел Фибоначчи.

Другим примером рекуррентных соотношений могут служить правила вычисления членов арифметической прогрессии

an+1=an+d , где d - разность прогрессии,

либо геометрической прогрессии

an+1=q an , где 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

else writeln (’значение n меньше 0’)

end {Factorial}

Рис. 16.1. Функция вычисления n! в рекурсивной форме.

Рассмотрим подробно, как будет выполняться обращение к этой функции, напрмер, при n=4.

На рисунке 16.2 показан процесс вычисления для случая Factorial(4).

24


n=0

if n>0 then

else Factorial:=1

n=1

if n>0 then Factorial:= Factorial(0)1

else Factorial:=1

n=2

if n>0 then Factorial:= Factorial(1)2

else Factorial:=1

n=3

if n>0 then Factorial:= Factorial(2)3

else Factorial:=1

n=4

if n>0 then Factorial:= Factorial(3)4

else Factorial:=1

Фрейм 5

Фрейм 4

Фрейм 3

Фрейм 2

Фрейм 1

1

1

2

6


Рис. 16.2. Вычисление функции Factorial(n) для n=4.

Сначала образуется так называемый рекурсивный фрейм №1 при n=4. Для этого фрейма отводится память и в нем фиксируются все значения переменных тела функции при n=4. Отметим, что в рекурсивном фрейме фиксируются значения всех переменных функции, кроме глобальных.

Затем происходит вызов Factorial(n) при n=3. Образуется фрейм №2, где фиксируются значения переменных тела функции при n=3. При этом фрейм №1 также хранится в памяти. Из фрейма №2 происходит обращение к Factorial(n) при n=2. В результате этого обращения образуется фрейм №3, где фиксируются значения переменных тела функции при n=2 и т.д. до тех пор, пока при очередном обращении к функции Factorial условие n>0 не примет значение false.

Это произойдет в фрейме №5. В этом фрейме мы получим значение Factorial =1 и передадим это значение в фрейм №4. После этого фрейм №5 будет уничтожен, так как обращение Factorial(n) при n=0 будет выполнено.

В фрейме №4 мы вычислим значение Factorial(n) для n=1. После чего мы передадим это значение во фрейм №3, а фрейм №4 будет закрыт, так как обращение к Factorial(n) при n=1 будет закончено.

Так мы будем сворачивать эту цепочку фреймов в последовательности, обратной той, в которой мы их порождали, пока не свернем фрейм №1. После чего вычисление функции будет окончено.

Рекурсия возможна не только в случае функций, но и процедур. Пример рекурсии для процедур приведен на рисунке 16.3. Там показано описание рекурсивной процедуры для распечатки (вывода на печать) строки символов в порядке, обратном их вводу.

Procedure BackPrint ;

var символ : char ;

begin read (символ) ;

if символ = EOL {EOL - End Of Line - специальное значение типа

СHAR, соответствующее окончанию ввода}

then writeln ( ) ; {пред началом вывода надо убедиться, что

печатать будем с новой строки}

else begin BackPrint ; write (символ) end

end {Procedure}

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

(Косвенная рекурсия.) Итерация и рекурсия.

Нетрудно заметить сходство между циклическими конструкциями (повторениями) и рекурсией. На рисунке 16.4 показана схема цикла вида while do и его рекурсивного аналога.

Цикл

Рекурсия

while Условие Цикла

do Тело Цикла

Procedure Рекурсивный Цикл ;

begin

if Условие Цикла

then begin Тело Цикла;

Рекурсивный Цикл

else{окончание рекурсии}

end

Рис. 16.4. Схема организации цикла вида while do

и его рекурсивного эквивалента.

Обратите внимание, что в правой части рис. 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;

НОД:=a

end

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. Рекурсивная функция Аккермана.

Способы повторного использования процедур и функций.

Итак, процесс абстракции в форме процедуры состоит из трех шагов:

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

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

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

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

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

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

Присоединение. Этот способ предполагает, что если у нас есть процедура P1 c предусловием Q1 и постусловием R1 и процедура P2 c пред-и c постусловиями Q2 и R2 соответственно, (причем R1 Q2) , то мы можем построить процедуру P c предусловием 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 целых чисел.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://www.ergeal.ru/

Похожие работы:

  • Рекурсия

    Реферат >> Информатика, программирование
    ... компьютера, называется глубиной рекурсии. Завершение работы рекурсивных подпрограмм ... , заметим, что использование рекурсии является красивым приёмом программирования. ... время исполнения программы. Использование рекурсии увеличивает время исполнения программы ...
  • Рекурсия

    Дипломная работа >> Экономико-математическое моделирование
    ... сложности задач. 1.Что такое рекурсия? Понятие рекурсии достаточно просто для понимания и не ... следующие смысловые единицы: рекурсия, рекурсивный алгоритм, прямая рекурсия, косвенная рекурсия, рекурсивные обращения, рекуррентные ...
  • Рекурсия

    Реферат >> Кибернетика
    ... . . 3 Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Пример 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Пример 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Рекурсия. Рекурсией называется ситуация, когда процедура или ...
  • Использование рекурсии в PHP

    Доклад >> Информатика, программирование
    Использование рекурсии в PHP Дроздовский Михаил Рекурсия — это обращение функции к самой себе. ... не понимают, как же использовать рекурсию на практике — мол, "что за ... задачу достаточно легко решить с помощью рекурсии. Пишем небольшую функцию: function tree ...
  • Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод

    Реферат >> Математика
    ... и Тезее. Теперь рассмотрим применение рекурсии для решения таких задач. Применение ... рекурсии рассматривается на примере задачи ... коня. Наряду с демонстрацией применения рекурсии еще раз демонcтрируется пошаговая, структурная ...
  • VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

    Реферат >> Информатика, программирование
    ... главе обсуждается мощный инструмент — рекурсия. Рекурсия может быть также запутанной ... =========80 Глава 5. Рекурсия Рекурсия — мощный метод программирования ... рекурсии, и приводятся способы устранения рекурсии, если это необходимо. Что такое рекурсия? Рекурсия ...
  • ЛИСП

    Реферат >> Информатика, программирование
    ... с применением рекурсии. Научиться работать с функционалами и макросами. 1. Рекурсия. Различные формы рекурсии. 2. Применяющие ... Рассмотрим следующие формы рекурсии: простая рекурсия; параллельная рекурсия; взаимная рекурсия. Рекурсия называется простой, если ...
  • Логическое и функциональное программирование

    Учебное пособие >> Информатика, программирование
    ... простая запись этой функции через рекурсию: A(m,n)=iif(m=0,n+1,iif(n=0,A(m-1,1),A(m-1,A(m,n-1)))). Вообще говоря, ... содержит вызов функции g: f((…)(…g…)); g((…)(…f…)). Рекурсия более высокого порядка является рекурсией, в которой аргументом рекурсивного ...
  • Построение реалистичного изображения методом обратной трассировки лучей

    Курсовая работа >> Информатика, программирование
    ... ограничение количества итераций (глубины рекурсии). RADIOSITY (ИЗЛУЧАТЕЛЬНОСТЬ). ... программе. Глубина рекурсии – этот параметр устанавливает глубину рекурсии в алгоритме трассировки ... большие значения максимальной глубины рекурсии, т.к. разница в качестве ...
  • Язык логического программирования Visual Prolog

    Учебное пособие >> Информатика, программирование
    ... Prolog распознает специальный случай рекурсии — хвостовую рекурсию — и компилирует ее ... фрейме правила-родителя. Преимущества рекурсии Рекурсия имеет три основных преимущества ... сложности. Оптимизация хвостовой рекурсии У рекурсии есть один большой недостаток ...