78212

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

Лекция

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

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

Русский

2015-02-07

231.5 KB

5 чел.

екция: Рекурсия: прямая и косвенная. Рекуррентные выражения   Страница  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.  Дайте определение прямой и косвенной рекурсии.


 

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

8691. Суспільство як об’єкт вивчення філософії 84 KB
  Суспільство як об’єкт вивчення філософії. Суспільство, його сутність. Суспільство як самоорганізуюча і саморозвиваюча система. Відмінність законів природи і суспільства. Роль географічного природного середовища в житті суспіль...
8692. Філософія науки і техніки 94 KB
  Філософія науки і техніки. Техніка та історія людства. Філософія техніки: історія становлення та предмет вивчення. Головні проблеми досліджень у філософії техніки. Проблема комп’ютеризації та штучного інтелекту. Пр...
8693. Аксіологія. цінності в житті людини і суспільства 118 KB
  Аксіологія. цінності в житті людини і суспільства. Поняття «аксіологія». Місце аксіології в системі культури. Природа цінностей. Цінність і сенс життя людини. Ієрархія цінностей буття людини. Сучасна культурна криза і проблем...
8694. Релігієзнавство як наука. Свобода совісті як елемент демократичних свобод 90 KB
  Релігієзнавство як наука.Свобода совісті як елемент демократичних свобод Богословсько-теологічний, філософський та науковий методи пізнання релігії. Соціології та психологія релігії. Релігійний світогляд. Релігія, її со...
8695. Структура сучасних релігій. Походження та ранні форми релігій 123.5 KB
  Структура сучасних релігій. Походження та ранні форми релігій Особливості віри. Релігійна свідомість: раціональний та емоційно-вольовий аспект. Релігійний культ: зміст і форми. Релігійні організації. Проблема походження релігії...
8696. Національні релігії. Іудаїзм, індуїзм, конфуціанство, даосизм, синтоїзм 207.5 KB
  Національні релігії. Ранні національні релігії: Стародавній Єгипет, Месопотамія, Індія, Китай, античний світ. Пізні національні релігії: іудаїзм, індуїзм, конфуціанство, даосизм, синтоїзм. Ранні національні релігії - це такі реліг...
8697. Світові релігії. Буддизм 55 KB
  Світові релігії. Буддизм План 1. Витоки буддизму. 2. Догмати буддизму: а. Картина світу очима послідовників буддизму б. Вчення про душу в буддизмі в. Ставлення до земного життя будистів г. Шлях до порятунку через основні правила будизму 3. Мораль ре...
8698. Світові релігії. Іслам 85.5 KB
  Світові релігії. Іслам План 1. Витоки ісламу. 2.Особливості віровчення ісламу. 3.Обрядність ісламу. 4. Етапи життя мусульманина. Принципи і мораль мусульманства. Іслам - наймолодша світова релігія. За даними всесвітньої ісламської ліги 1980...
8699. Світові релігії. Християнство. Розкол християнства, його гілки 127 KB
  Світові релігії. Християнство План. 1. Християнство, його віровчення і культ. 2. Нехристиянські джерела про виникнення християнства. 3. Розкол християнства, його гілки. 4. Етапи життя мусульманина. Принципи і мораль мусульманства. Християнство Христ...