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.


 

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

84682. Приём вычислений вида 36 –2 36 – 20 96 KB
  Дидактическая цель: Создать условия для активизации познавательной деятельности учащихся через использование цифровых образовательных ресурсов. Предметные задачи урока: показать с помощью знаково-символического моделирования новые приёмы вычислений.
84683. Информационно-разъяснительная работа посольства 14.25 KB
  Сюда входит как устная разъяснительная работа проводимая во время разного рода бесед выступлений перед общественностью так и распространение печатных изданий официальных бюллетеней посольства прессрелизов и т. Весьма эффективным средством в проведении этой работы служат организуемые посольством приемы с участием представителей широкой общественности демонстрация документальных и художественных фильмов прессконференции и прессбрифинги для представителей местной прессы и аккредитованных в стране корреспондентов информационных агентств...
84684. Виды аналитических и информационных документов, направляемых Посольством в Центр 14.29 KB
  В ней освещается широкоформатная тема например внешняя торговля страны пребывания за год или полгода вопросы состояния отношений страны пребывания с третьими странами участие страны пребывания в работе международных организаций и т. Оно касается крупных внутриполитических или внешнеполитических проблем страны пребывания. Грамотно составленный отчет является базой для внесения корректив во внешнеполитическую линию России в отношении данной страны. Составляются на видных государственных и общественных деятелей страны пребывания.
84685. Структура Посольства, распределение обязанностей, штатное расписание 13.41 KB
  Структура Посольства распределение обязанностей штатное расписание. Посол представляет РФ непосредственно руководит работой Посольства несёт персональную ответственность за выполнение возложенных на Посольство задач и осуществление им функций определяет в соответствии с нормативными актами МИДа России структуру Посольства распределяет должностные обязанности между его сотрудниками. Сотрудников посольства. Обеспечение безопасности посольства его сотрудников и членов их семей организация защиты государственной и иной охраняемой законом...
84686. Роль иностранного языка в работе дипломата 12.06 KB
  Роль иностранного языка в работе дипломата. Роль иностранного языка в работе чрезвычайно важна. Профессиональное владение иностранными языками может пригодиться дипломату во многих сферах его дипломатической деятельности. Знание в совершенстве языка страны пребывания значительно расширяет количество источников информации печатные издания на иностранном языке интернетресурсы телевидение радио и т.
84687. МГИМО: история, структура, кадровая база МИД России 15.87 KB
  МГИМО: история структура кадровая база МИД России. МГИМО является одним из старейших университетских центров страны по подготовке специалистов международного профиля. Первый набор в МГИМО составил 200 студентов. С 1946 года на учебу в МГИМО стали направляться студенты из зарубежных стран.
84688. Статус профессиональной дипслужбы во внешнеполитической системе, дипломаты и политическое руководство 13.63 KB
  Служба в аппарате внешнеполитического ведомства – это особая разновидность федеральной государственной службы Российской Федерации. Это профессиональное осуществление целей и функций внешней политики России посредством исполнения государственных должностей федеральной государственной службы утвержденных в: центральном аппарате МИД РФ диппредставительствах и консульских учреждениях за рубежом представительствах при международных организациях представительствах МИД на территории РФ на отдельных государственных должностях госслужбы в...
84689. Порядок приема в МИД и требования, предъявляемые к выпускникам вузов, впервые поступающим на государственную службу 14.85 KB
  К дипломатической службе не относятся технические сотрудники. В России долгое время не было специального закона о дипломатической службе. Закон – 79ФЗ о гражданской службе от 2004 года распространялся и на дипломатическую службы. В этих законах формулируются принципы государственной службы: равных доступ граждан к службе профессионализм и компетентность стабильность.
84690. Дипломатические ранги и порядок их присвоения 15.73 KB
  Присвоение дип рангов дип работникам производится в соответствии с установленными ФЗ Об основах гос службы РФ и иными нормативными правовыми актами РФ квалификационными требованиями к профессиональному образованию стажу и опыту работы по специальности знанию Конституции РФ Федеральных Законовнов применительно к исполнению своих должностных обязанностей а также с учетом срока пребывания в дип ранге результатов служебной деятельности и при наличии сертификата о соответствующем уровне владения иностранным языком. Присваиваются следующие...