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.


 

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

36562. Принцип программного управления 45 KB
  Всё что способен делать компьютер это выполнять программы. Процессор â€движущая сила†исполнитель точно выполняющий команды программы. а также операции копирования перемещения информации из одних ячеек памяти в другие ввода данных в оперативную память например символов набранных на клавиатуре вывода информации например на экран дисплея или на диск окончания программы и другие.  Процессор выполняет команды начиная с первой команды программы.
36563. Структурный тип запись 45 KB
  Например анкета служащего содержит такие данные как фамилия имя отчество строковый тип год рождения целый тип разряд целый тип и многие другие данные. Объединение таких данных общий структурный типанкета затруднительно сделать в рамках массива или множества. Естественным средством структурирования в этом и подобных случаях является структурный тип Запись.
36564. Структурный тип множество 41.5 KB
  Понятие о типе Множество в Турбо Паскале. Множество является ещё одним структурным типом Турбо Паскаля служащим для объединения однородных однотипных элементов. Однако форма объединения в Множество существенно отличается от типа Массив.
36565. Особенности разработки программы с подпрограммой 35.5 KB
  Практически все используемые прикладные программы это программы с подпрограммами процедурами и функциями. Подпрограммы как уже указывалось позволяют преодолевать сложность обеспечивая декомпозицию программы на более простые составные части. Разработка программ на ТурбоПаскале с подпрограммами имеет ряд отличий от той методики которая изложена выше применительно с простым программам.
36566. Область действия имен в программе 29 KB
  В программах не использующих подпрограммы имена описанные в разделе описаний действуют во всей программе не вызывая какихлибо проблем. В подпрограммах могут использоваться свои локальные внутренние имена и кроме того она может также использовать глобальные внешние для неё имена из других подпрограмм или основной программы. Локальными именами подпрограммы называются те имена которые описаны в этой подпрограмме в её разделе описаний. Все остальные используемые в подпрограмме имена являются глобальными именами данной...
36567. Параметры-процедуры и параметры-функции. Процедурный тип 30.5 KB
  Описание процедурных типов имеет форму заголовка процедуры или функции с опущенным её именем: type имя процедурытипа = procedure список формальных параметров ; type имя функциитипа = function список формальных параметров : тип ; Например: type fun =function x:rel:rel; При описании подпрограммы с процедурными параметрами такие параметры указываются формальным именем и соответствующим процедурным типом. Пример процедуры использующей описанный выше процедурный тип fun: procedure print_f n:byte; f:fun; const count = 20; vr X:rel;...
36568. Особенности использования параметров в процедурах и функциях 30 KB
  Это означает что нельзя использовать описание типа rry непосредственно в списке формальных параметров. Например: procedure sttem:rry [1.8] of byte; {Неправильное описание параметра m} type byte_st = rry [1. type rry10 = rry[0.
36569. Функции: описание и вызов функции 32 KB
  В отличие от процедур функции не являются отдельными операторами. Функции возвращают значения результат обращения к ним и предназначены для использования в составе выражений или в качестве выражений. Это накладывает определенный отпечаток на синтаксическую структуру описания функций которая имеет вид: function имя функции [ список формальных параметров ]: тип функции ; описание локальных имён begin тело функции последовательность операторов end; В заголовке описания функции обязательно указывается тип вырабатываемого функцией...
36570. Процедура: описание и вызов процедуры 30 KB
  Структура описания процедуры во многом сходна со структурой программы. По существу отличие только в заголовке процедуры. Описание процедуры может быть помещено на любое место в разделе описания вызывающей подпрограммы.