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


 

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

21948. ГЕОДЕЗИЧНІ РОБОТИ ПРИ МОНТАЖІ ЕЛЕМЕНТІВ БУДІВЕЛЬНИХ КОНСТРУКЦІЙ 1.06 MB
  ГЕОДЕЗИЧНІ РОБОТИ ПРИ МОНТАЖІ ЕЛЕМЕНТІВ БУДІВЕЛЬНИХ КОНСТРУКЦІЙ Розглянувши елементи та методи інженерногеодезичних робіт розглянемо методику геодезичного забезпечення встановлення елементів будівельних конструкцій в проектне положення. Завдання та зміст геодезичних робіт При проведенні монтажних робіт встановлюють в проектне положення елементи та вузли будівельних конструкцій: фундаменти колони панелі цегляні стіни балки плити перекриття тощо. У промислових спорудах після монтажу будівельних конструкцій у проектне положення...
21949. ІНЖЕНЕРНО-ГЕОДЕЗИЧНІ ВИШУКУВАННЯ ЛІНІЙНИХ СПОРУД 3.34 MB
  Комплекс інженерногеодезичних робіт по вибору найбільш оптимальної економічно обґрунтованої траси називають трасуванням. Проектування траси лінійної споруди по топографічним картах і планам називають камеральним трасуванням. Вибір траси безпосередньо на місцевості називають польовим трасуванням.1 виходячи із дотримання граничного ухилу траси.
21950. ОРГАНІЗАЦІЯ ІНЖЕНЕРНО-ГЕОДЕЗИЧНИХ РОЗМІЧУВАЛЬНИХ РОБІТ 5.04 MB
  Організація інженерногеодезичних робіт Для геодезичного забезпечення будівельної галузі в системі Міністерства будівництва архітектури та комунального господарства України повинна бути створена державна Геодезична служба в будівництві ДГСБ. Вона повинна законодавчо відповідати за стан якість виконання інженерногеодезичних робіт в будівництві бути керівним органом по створенню нормативнотехнічних документів НТД. В системі Держбуду інших міністерствах і відомствах повинні бути створені підрозділи ДГСБ які б виконували керівні та...
21951. Виды и стадии инженерно-геологических изысканий 184.22 KB
  Виды и стадии инженерногеологических изысканий 1. Инженерногеологическая рекогносцировка. Инженерногеологическая съемка. Инженерногеологическая разведка.
21952. ОСОБЕННОСТИ ИНЖЕНЕРНО-ГЕОЛОГИЧЕСКИХ ИССЛЕДОВАНИЙ ДЛЯ РАЗЛИЧНЫХ ВИДОВ СТРОИТЕЛЬСТВА 260.31 KB
  ОСОБЕННОСТИ ИНЖЕНЕРНОГЕОЛОГИЧЕСКИХ ИССЛЕДОВАНИЙ ДЛЯ РАЗЛИЧНЫХ ВИДОВ СТРОИТЕЛЬСТВА. ИНЖЕНЕРНОГЕОЛОГИЧЕСКИЕ ИССЛЕДОВАНИЯ ДЛЯ ПРОМЫШЛЕННОГО И ГРАЖДАНСКОГО СТРОИТЕЛЬСТВА I. Инженерногеологические исследования при выборе строительной площадки выполняемые с целью сравнительной оценки возможных вариантов ее размещения первая стадия изысканий включают в себя проведение следующих работ. Инженерногеологическая рекогносцировка.
21953. ТЕХНИЧЕСКАЯ МЕЛИОРАЦИЯ ПОРОД. Отчетные инженерно-геологические материалы 229.19 KB
  Отчетные инженерногеологические материалы. ПРЕДМЕТ И ЗАДАЧИ ТЕХНИЧЕСКОЙ МЕЛИОРАЦИИ ПОРОД Главная задача грунтоведения и инженерной геологии заключается в оценке геологической обстановки сопровождающейся прогнозом инженерногеологических процессов и явлений применительно к требованиям различных видов производственной деятельности человека. В случае отрицательного прогноза в комплекс инженерногеологических работ входит выбор наиболее рациональных способов борьбы с неблагоприятными процессами и явлениями. Различают мероприятия двух типов: 1...
21954. Инженерно-геологические исследования в горном деле 2.71 MB
  Предмет и задачи инженерногеологических исследований в проблеме рационального использования полезных ископаемых. Системный подход к инженерногеологическому исследованию при разведке месторождений полезных ископаемых. Инженерногеологические условия месторождений полезных ископаемых. Предмет и задачи инженерногеологических исследований в проблеме рационального использования полезных ископаемых.
21955. Введение в инженерную геологию 2.3 MB
  Основные направления инженерной геологии и ее современная структура. Возникновение инженерной геологии и развитие ее на первых этапах были связаны со строительством. Поэтому можно говорить о предыстории инженерной геологии которая по существу складывается из двух этапов.
21956. Основные факторы, определяющие инженерно-геологические условия территории региона 1.87 MB
  Результаты воздействия этих факторов в геологическом прошлом отражены в геологическом строении и характере пород и в различных последствиях влияния геологических процессов карст тектоническая нарушенность пород и др. зависят от характера пород образовавшихся в существующее геологическое время. Геология При изучении инженерногеологических условий анализируется геологическое строение и состав пород в соответствии с их генезисом и геохронологическими схемами. Горные породы Земную кору слагают горные породы различные по происхождению и...