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.


 

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

85060. Инфекции, передаваемые половым путем 30.46 KB
  Познакомить учащихся с признаками основных инфекций передаваемых половым путем ИППП и причинами их распространения. Обсудить основные меры профилактики ИППП. Основные меры по профилактике ИППП. Самый высокий уровень заболеваемости ИППП отмечается в группе 20 21летних затем 15 19летних.
85061. Россия в мировом сообществе 32.75 KB
  Сформировать у учащихся общее представление о роли России в современном мире показать потенциальные возможности страны и основные направления политики государства направленной на обеспечение стабильности и национальных интересов России. Изучаемые вопросы Потенциальные возможности России. Роль России в мировых процессах. Обеспечение стабильности и национальных интересов России в мировом сообществе.
85062. Национальные интересы России в современном мире. Основные угрозы национальным интересам и безопасности России 34.01 KB
  Национальные интересы России в современном мире. Основные угрозы национальным интересам и безопасности России Цель урока. Сформировать у учащихся представление о национальных интересах России как совокупности сбалансированных интересов личности общества и государства; убеждение в возрастании в современных условиях роли гражданина России в деле обеспечения национальных интересов России. Дать учащимся общее понятие об угрозе национальным интересам и безопасности России которую несут в себе последствия чрезвычайных ситуаций природного...
85063. Формирование общей культуры населения в области безопасности жизнедеятельности 32.12 KB
  Формирование общей культуры населения в области безопасности жизнедеятельности Цель урока. Систематизировать представления учащихся об общей культуре населения в области безопасности жизнедеятельности подчеркнув значение уровня культуры населения в области безопасности жизнедеятельности для обеспечения национальной безопасности России. Общая система обеспечения безопасности населения страны. Уровень культуры в области безопасности населения страны и национальная безопасность России.
85064. Опасные и чрезвычайные ситуации, общие понятия и определения, их классификация 31.06 KB
  Сформировать понимание недостижимости абсолютной безопасности населения и возрастания роли каждого человека в обеспечении личной безопасности в различных опасных и чрезвычайных ситуациях. Ключевые понятия в области безопасности жизнедеятельности. Подчеркнуть что человек на протяжении периода своего существования на Земле в первую очередь стремился расширить сферу своей жизнедеятельности и обеспечить свое благополучие и очень мало заботился об обеспечении безопасности своей жизнедеятельности. Не случайно обеспечением безопасности...
85066. Чрезвычайные ситуации природного характера, их причины и последствия 30.73 KB
  Чрезвычайные ситуации природного характера их причины и последствия Цель урока. Систематизировать знания учащихся о наиболее характерных опасных природных явлениях и чрезвычайных ситуациях природного происхождения возникающих на территории нашей страны. Повторить основные причины возникновения чрезвычайных ситуаций природного характера и их возможные последствия. Напомнить о необходимости знать местные признаки приближения опасного природного явления.
85067. Чрезвычайные ситуации техногенного характера, их причины и последствия 30.7 KB
  Сформировать у учащихся более полное представление о факторах опасности техносферы для безопасности жизнедеятельности населения страны обратив внимание на источники техногенных опасностей основные причины их возникновения. Сформировать убеждение что повышение уровня культуры в области безопасности жизнедеятельности всего населения страны это приоритетный путь повышения уровня безопасности жизнедеятельности личности общества и государства. Изучаемые вопросы Факторы опасности техносферы для безопасности жизнедеятельности населения страны....
85068. Военная угроза национальной безопасности России. Международный терроризм — угроза национальной безопасности России 35.59 KB
  Военная угроза национальной безопасности России. Международный терроризм угроза национальной безопасности России Цель урока. Познакомить учащихся с внешними внутренними и трансграничными угрозами национальной безопасности России в современном мире. Обоснованно показать учащимся возрастание роли Вооруженных сил России по обеспечению военной безопасности государства и укрепления Вооруженных сил РФ.