78212

Рекурсия: прямая и косвенная. Рекуррентные выражения

Лекция

Информатика, кибернетика и программирование

Определения с помощью рекуррентных формул иногда называют рекурсивными определениями. Если для факториала первое (итеративное) определение может показаться проще, то для чисел Фибоначчи рекурсивное определение

Русский

2015-02-07

231.5 KB

6 чел.

екция: Рекурсия: прямая и косвенная. Рекуррентные выражения   Страница  6 из 6

Оглавление

[1] Оглавление

[2] Рекурсия

[2.1] Формы рекурсивных процедур

[2.2] Рекурсивный спуск

[2.3] Комбинация прямой и обратной рекурсии

[2.4] Косвенная рекурсия

[3] Контрольные вопросы

Комбинированный урок №14-15

Тема: Рекурсия: прямая и косвенная. Рекуррентные выражения 

Цель: изучить основные понятия о рекурсии, способы применения. Дать определение рекуррентным выражениям.

Рекурсия

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

Рассмотрим функцию факториала n!. Как правило, ее определяют как произведение первых n целых чисел: n! = 1*2*3*...*n.

Такое произведение конечно можно легко вычислить с помощью итеративных конструкций, например, оператора цикла for:

program Factorial;

var

 Fact : Longint;

 n, i : Integer;

begin

 Write ('Введите число n: ');

 Readln ( n );

 Fact := 1;

 for i:= 1 to n do Fact := Fact*i;

 Writeln ('Факториал  n! = ', Fact);

end.

Однако существует также другое определение факториала, в котором используется рекуррентная формула и которое имеет такой вид:

(1) 0!   = 1

(2) для  любого n > 0 n! = n * (n - 1)!

Определения с помощью рекуррентных формул иногда называют рекурсивными определениями. Если для факториала первое (итеративное) определение может показаться проще, то для чисел Фибоначчи рекурсивное определение:

(1)  F(1) = 1,

(2)  F(2) = 1,

(3)  для любого n > 2 F(n) = F(n-1) + F(n-2)

выглядит для вычислений лучше, чем прямая формула:

Похожие рекуррентные формулы есть также и для многих других математических определений. Понятно, что организовать вычисления по рекуррентным формулам можно и без использования рекурсии. Использование рекурсии позволяет легко (почти дословно) запрограммировать вычисления по рекуррентным формулам. Например, программа, использующая рекурсивную функцию для вычисления факториала n! имеет следующий вид:

program Factorial;

var

 n : Integer;

function Fact ( i : Integer ): Longint;

begin

 if i = 1  then  Fact := 1

 else Fact := i * Fact (i-1)

end;

begin

 Write  ('Введите число n: ') ;

 Readln (n);

 Writeln ('Факториал  n!  = ',   Fact(n));

end.

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

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

Например, следующая процедура будет бесконечно печатать известные всем строки:

program  EndLess1;

procedure PopeAndDog1;

begin

 Writeln('У попа была собака, он ее любил.');

 Writeln('Она  съела  кусок мяса, он  ее  убил,');

 Writeln('похоронил  и  надпись  написал:');

 PopeAndDog1

end;

begin

 PopeAndDog1 

end.

Однако если оператор вызова процедуры поставить перед выводом текста, как показано ниже:

program EndLess2;

procedure PopeAndDog2;

begin

 PopeAndDog2;

 Writeln('y попа была собака, он ее любил.');

 Writeln('Oнa съела кусок мяса, он ее убил,');

 Writeln('похоронил и надпись написал:');

end;

begin

 PopeAndDog2 

end.

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

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

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

Формы рекурсивных процедур

В общем случае любая рекурсивная процедура Rec включает в некоторое множество операторов S и один или несколько операторов рекурсивного вызова.

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

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

Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент копий рекурсивной процедуры.


Структура рекурсивной процедуры может принимать
три разных формы:

  1.  Форма с выполнением действий до рекурсивного вызова (с выполнением действий на рекурсивном спуске):

procedure Rec;

begin

 S; {операторы}

 If <условие>  then Rec;

end;

  1.  Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате):

procedure Rec;

begin

 if <условие> then Rec;

 S; {операторы}

end;

3. Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате):

procedure Rec;

begin

 S1;

 if <условие> then Rec;

 S2;

end;

или

procedure Rec;

begin

 if <условие> then

 begin

   S1;

   Rec;

   S2;

 end;

end;

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

Первые две формы рекурсивных подпрограмм рассмотрим на примере вычисления факториала (n!), третью форму - на примере реверсивной печати вводимой строки.

Рекурсивный спуск 

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

Mult - для выполнения до рекурсивного вызова (то есть на спуске) операции умножения накапливаемого значения факториала на очередной множитель;

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

Программа Factorial_Down, которая использует рекурсивную функцию Fact_Dn, выполняющую вычисления на спуске, имеет такой вид:

program Factorial_Down;

var   n : Integer;

 function  Fact_Dn(Mult : Longint; i, m : Integer ) :Longint;

 begin

   Mult := Mult * i;

      { Накопление факториала стоит до оператора рекурсивного вызова.}

      { Следовательно  вычисление  выполняется  на  спуске.          }

   if  i  = m  then  Fact_Dn := Mult

   else  Fact_Dn := Fact_Dn (Mult, i+1, m)

 end;

begin

 Write ('Введите  число  n:  ');

 Readln ( n );

 Writeln ('Факториал  n!   = ' , Fact_Dn(1,1,n ));

end.

Для демонстрации выполняемых функцией Fact_Dn действий приведем таблицу трассировки значений ее параметров по уровням рекурсии. В этой таблице рассмотрен конкретный случай для n = 5.

Рис.1. Трассировка значений параметров

Рассмотренная выше программа Factorial, использующая рекурсивную функцию Fact, выполняет вычисление факториала на возврате. Но это не совсем очевидно, поскольку в функции Fact рекурсивный вызов и операция умножения совмещены в одном операторе присваивания. Для более понятной демонстрации работы на возврате, приведем программу Factorial_Up, использующую функцию Fact_Up, в которой рекурсивный вызов и оператор накопления факториала разделены явным образом.

program Factorial_Up;

var

 n : Integer;

 function Fact_Up(i :Integer) : Longint;

 var

   Mult: Longint;

 begin

   if  i = 1  then Mult := 1

   else Mult := Fact_Up (i-1);

   Fact_Up := Mult * i {Накопление факториала стоит после                 }

                       {оператора рекурсивного вызова.                    }

                       {Следовательно вычисление выполняется на возврате. }

 end;

begin

 Write ( 'Введите число n: ');

 Readln (n);

 Writeln ('Факториал  n! = ', Fact_Up (n));

end.

Приведем таблицу трассировки по уровням рекурсии, аналогичную таблице для функции Fact_Dn: 

Рис.2. Трассировка значений параметров

Комбинация прямой и обратной рекурсии 

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

Задача. Вывести на печать символы введенной строки 'HELLO' в обратном направлении.

Решение этой задачи выполнено в виде показанной ниже программы Reverse_String, использующей рекурсивную процедуру Reverse. Напомним, что функция EoLn возвращает значение, равное False, если строка еще не окончилась, и значение, равное True, когда считывается последний символ строки.

program Reverse_String;

 procedure  Reverse;

 var  

   Ch : Char;

 begin

   if not EoLn  then

   begin

     Read (Ch) ;

     Reverse;

     Write (Ch);

   end

 end;

begin

 Reverse

end.

Если после запуска программы на выполнение в качестве входной строки ввести слово 'HELLO', то соответствующая такой исходной строке таблица трассировки по уровням рекурсии будет иметь следующий вид:

Рис.3. Трассировка значений параметров

Косвенная рекурсия 

Косвенной или взаимной рекурсией называется организация вызовов нескольких процедур и функций по кругу (первая процедура вызывает вторую, вторая - третью, ..., n-я процедура вызывает первую).

Для реализации косвенной рекурсии при описании процедур и функций используется директива forward: 

program Recurs;

 procedure Rec1 (i : Byte); forward;

 procedure Rec2 (i : Byte);

 begin

   Writeln ('рекурсия.');

   Rec1(i)

 end;

 procedure Rec1;

 begin

   if i > 0 then

   begin

     Write ('Взаимная ');

     Rec2 (i-1) 

   end

 end;

begin

 Reс1 (5) 

end.

   Результат:

 Взаимная рекурсия.

 Взаимная рекурсия.

 Взаимная рекурсия.

 Взаимная рекурсия.

 Взаимная рекурсия.

Контрольные вопросы

  1.  Дайте определение рекурсии.
  2.  Какие формы принимает рекурсивная процедура? Приведите примеры.
  3.  Что такое рекуррентное выражение? Приведите примеры.
  4.  Дайте определение прямой и косвенной рекурсии.


 

А также другие работы, которые могут Вас заинтересовать

52091. Африка 57.5 KB
  ФГП материка. Открытие и исследование материка. Фронтальный опрос на знание номенклатуры карты по теме ФГП материка. Индивидуальный опрос: а План изучения материка.
52092. Африка 69.5 KB
  Проблемный вопрос Почему в природе трех материков Африки Австралии и Южной Америки много общего Ответ: Потому что все эти материки являются частью единого материка Гондвана. Какой материал мы будем изучать первым вы узнаете если отгадаете загадку: Этот материк по площади в 3 с лишним раза больше другого и почти такой же по площади как два других материка Какой это материк Ответ: Африка так как по площади он в 3 с лишним раза больше Австралии и почти такой же по площади как Южная Америка и Антарктида вместе взятые. Проблемный...
52093. Африка. Фізико-географічне положення. Історія відкриття й дослідження материка 51 KB
  Вивчення нового матеріалу Відкриття та дослідження Африки Час дослідження Дослідники Результати досліджень ІІІ тис. Експедиція під керівництвом португальця Бартоломеу Діама Здійснила плавання вздовж західних берегів Африки до м. Експедиція під керівництвом португальця Васко да Гама На шляху до Індії дісталася південних берегів Африки. Африки.
52094. Населення і народи Африки 55.5 KB
  Мета уроку: формування первинних знань учнів про етнічний склад населення Африки особливості його формування динаміку і розміщення; сприяти розумінню демографічних проблем Африки та шляхи їх вирішення.Формувати первинні практичні вміння характеризувати загальні риси населення материка; вдосконалювати практичні вміння працювати з тематичними картами атласу. Зміст курсу Географія материків і океанів передбачає не тільки вивчення природи материків але й ознайомлення з характеристиками населення материків та його господарською діяльністю.
52095. Тропічні пустелі та напівпустелі. Твердолисті вічнозелені ліси та чагарники 68.5 KB
  Навчальна мета: повторити вивчений матеріал; зясувати рівень оволодіння учнями навчальним матеріалом з попередніх тем; сформувати знання про особливості розміщення природних зон Африки; поглибити систему знань учнів про взаємозв'язки природних компонентів у складі природних зон; сформувати в учнів уміння складати характеристику природних зон у певній послідовності за типовим планом; удосконалювати практичні вміння учнів працювати з картами атласами. Обладнання: фізична карта Африки кліматична карта Африки карта природних зон Африки...
52096. Африка 63.5 KB
  Посовещавшись команды должны выбрать капитана и название команды можно предложить выбрать из названий стран Африки. Название команды пишут маркером на чистых табличках. За каждый правильный ответы команды получают красные жетоны 2 ВОСХОЖДЕНИЕ на Джомолунгму На доске магнитной нарисована гора с маршрутамиступеньками по количеству команд. Команды выбирают одного игрока альпиниста который будет защищать честь команды при восхождении.
52097. Загальні особливості клімату Африки. Кліматичні пояси i типи клімату 43 KB
  Мета: повторите поняття клімат вірні чинники типи клімату кліматичний пояс; сформувати знання про загальні особливості клімату Африки про типи клімату в кожному кліматичному поясі Африки; продовжити формування навичок аналізу карти кліматичної карти Африки кліматичних діаграм; розвивати увагу спостережливість вміння робити висновки визначати головне. Найвища точка Африки: а г. Вам уже відомо що більша частина Африки розташована в тропічних широтах екватор перетинає материк майже посередині саме тому Африка протягом року...
52098. Фізико-географічне положення та берегова лінія Африки 49 KB
  Розмістити порядкові номери географічних обєктів по океанам до яких вони належать Острів Камчатка Острів Шпіцберген Півострів Аравійський Острів Шрі-Ланка Півострів Скандинавський Острови Японські Острів НоваЗемля Острів Ісландія Хребет Ломоносова Острови Бермудські Острів Мадагаскар Море Червоне Острови Гавайські Море Карське Море Чорне Море Берингове Хребет Менделеєва Півострів Індостан Півострів Сомалі Острові Філіппінські Море Азовське Море Саргасове Острови Маріанські ...