34647

Рекурентные выражения. Рекурсия

Реферат

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

При первом вызове функции fib5 определяется через fib4fib3; вычисление fib4 осуществляется через fib3 fib2 fib3 через fib2 fibl fib2 через fib1 fib0. Согласно условию прекращения рекурсии fibl и fib0 равно 1. Соответствующий рекурсивный процесс должен быть осуществлен и для fib4 и т. Решение: Vr n:byte; function fibk:byte :longint; begin if k = 1 then fib : = 1 else fib: =fibk l fibk 2 {рекурсивный вызов} end; BEGIN redlnn; writelnn 'e число Фибоначчи'...

Русский

2013-09-08

73.5 KB

0 чел.

исциплина «Основы алгоритмизации и программирование»  Рекурентные выражения. Рекурсия

Рекурентные выражения. Рекурсия

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

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

Задача 1. Постройте рекурсивную функцию для подсчета значения факториала числа n, где n! = 1*2*3*4*...*n. Заметим, что при подсчете факториала любого числа n может использоваться значение факториала предыдущего числа n -1, умноженное на само число n, т. е. n!=n*(n-1)!. При решении данной задачи используется эта закономерность.

VAR

 n: byte;

function fact (a: byte): longint;

begin

 if a=0 then fact=l else fact: =a*fact(a—1){рекурсия}

end;

Begin 

 readln(n);

 writeln(n,’!=fact(n)); {вызов рекурсии}

end.

Предположим, что нам необходимо подсчитать факториал числа 6. Представим процесс рекурсии в виде таблицы.

Рекурсивный

n:=6

Fact(6)

спуск

а:=6

6*Fact(5)

(погружение)

а:=5

5*Fact(4)

а:=4

4*Fact(3)

а:=3

3*Fact(2)

а:=2

2*Fact(l)

а: = 1

Fact: = l

Рекурсивный

а: = 1

Fact: = 1*1

возврат

а:=2

Fact: =2*1

(всплытие)

а:=3

Fact:=3*2

а:=4

Fact:=4*6

а:=5

Fact: =5*24

а: =6

Fact:: =6*120=720

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

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

Во-первых, рекомендуется компилировать программу с директивой {$S+}. Она пишется перед словом Program. Эта директива включает проверку переполнения стека (то есть именно той области памяти, в которой хранится состояние вызывающей подпрограммы). Если в процессе выполнения программы происходит переполнение стека, вызов процедуры или функции, откомпилированной с опцией {$S+}, приводит к завершению работы программы и на дисплей выводится сообщение об ошибке.

Во-вторых, можно разместить вначале каждой процедуры (функции), вызываемой рекурсивно, строку If KeyPressed then Halt. В этом случае при зависании программы вместо перезагрузки достаточно будет нажать любую клавишу.

Задача 2. Найдите n-е число Фибоначчи. Числа Фибоначчи определяются следующим образом: F0= F1= 1, Fn = Fn-1 + Fn-2, где n = 2, 3, 4, 5, ..., n.

Предположим, необходимо вычислить число Фибоначчи F5. При первом вызове функции fib(5) определяется через fib(4)+fib(3); вычисление fib(4) осуществляется через fib(3) + fib(2), a fib(3) через fib(2) + fib(l), fib(2) через fib(1)+ fib(0). Согласно условию прекращения рекурсии fib(l) и fib(0) равно 1. Соответствующий рекурсивный процесс должен быть осуществлен и для fib(4) и т. д.

Решение:

Var

 n:byte;

function fib(k:byte) :longint;

begin

 if k< = 1 then 

    fib : = 1 else

    fib: =fib(k —l) + fib(k —2) {рекурсивный вызов}

end;

BEGIN

 readln(n);

 writeln(n, '-e число   Фибоначчи-',   fib(n))   {вызов функции}

END.

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

 

В языке Pascal косвенная рекурсия реализуется с помощью специальной директивы forward, которая размещается в заголовке процедуры или функции.

Пример.

Procedure имя (формальные параметры); forward;


Задание
: Представить решение задачи 2 с помощью рекурсивной процедуры.

Решение:

VAR

 chf :longint;

 n:byte;

procedure fib(k:byte; var chf :longint);

var

 chfl, chf2:longint;

begin

 if n< = 1 then 

   chf: = 1 else 

   begin

     fib(k—l.chfl); {рекурсивный вызов}

     fib(k — 2,chf2);

     chf:=chfl + chf2

   end

end;

BEGIN

 readln(n);

 fib(n, chf); {вызов процедуры}

  writeln(n, '-e число Фибоначчи-', chf)

END.


 

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

67007. Подорож картою України 52 KB
  Мета: продовжити формувати уявлення учнів про географічне розміщення України її кордони сусідство з іншими країнами; ознайомити з найбільшими містами України горами водоймами тваринами рослинами; детальніше познайомити із столицею України містом Києвом; викликати позитивні емоції виховувати почуття любові...
67008. Правила поведения в экстремальной ситуации 63.5 KB
  Вводная часть: актуализация опорных знаний. - Что на свете всего дороже. - Как понимаете это слово. Что с ним связано? Что влияет на наше здоровье? (Питание, спорт, профилактика вредных привычек соблюдение правил безопасности, правильный отдых) - Что такое опасная ситуация? - Какое отношение имеют эти слова к здоровью?
67009. Текст. Признаки текста. Виды связи в тексте. Цепная связь. Способы передачи цепной связи. Параллельная связь. Присоединительная связь 102.5 KB
  Текст можно определить как объединенную смысловой и грамматической связью последовательность речевых единиц: высказываний, сложных синтаксических целых, фрагментов, разделов и.т.д. Основными признаками текста являются: 1) завершённость, смысловая законченность, которая проявляется в полном...
67010. Тема текста. Содержание текста. Коммуникативная задача текста. Части текста. Микротемы текста 38.5 KB
  Цели: 1. Углубить понятие о смысловом делении текста. 2. Продолжить работу над синтаксическими конструкциями для выражения характера, образа действия. 3. Добиться осознания студентами тесной взаимосвязи языка и общества, основных функций языка в обществе, которые будут способствовать правильному стилистическому использованию изученных конструкций в речи.
67011. Функционально-смысловые типы монологической речи. Описание 47 KB
  Цели: 1. Углубить понятие о типах монологической речи. 2. Продолжить работу над пунктуационными, синтаксическими, орфографическими и иными ошибками изложений (над наиболее типичными коллективно, над остальными – индивидуально. 3. Добиться осознания студентами тесной взаимосвязи языка и общества...
67012. Описание как функционально-смысловой тип речи 39.5 KB
  В текстах данного типа всегда представлена статичная картина, складывающаяся из указаний на предметы (или части предметов) и их признаки; главным, во имя чего создаются предложения, является указание на признаки; называющие их слова, как правило, помещается в конце предложения...
67013. Функционально-смысловые типы монологической речи. Повествование 43.5 KB
  Повествование раскрывает тесно связанные между собой события явления действия. Чаще всего это действия происходившие в прошлом. Предложения в повествовательных текстах не описывают действия а повествуют о них. Повествование это сообщение о каких-либо событиях и действиях.
67014. Функционально-смысловые типы монологической речи. Рассуждение 78 KB
  Рассуждение это тип речи целью которого является выяснение какого-либо понятия доказательство или опровержение какой-нибудь мысли. С логической точки зрения рассуждение это цепь умозаключений на какую-либо тему изложенная в последовательной форме. Рассуждение как тип речи широко встречается в научном стиле.
67015. Функциональные стили русского языка (общая характеристика) 90.5 KB
  Современный русский язык состоит из 5 стилей: Разговорный стиль Научный стиль Официально-деловой стиль Публицистический стиль Художественный стиль Функционально-стилевая типология охватывает практически все тексты рассматривая их во всем многообразии содержательных и языковых стилевых признаков. Любой текст можно отнести к тому или иному стилю...