Поиск по сайту


Каталог учебных материалов

Свежие работы в разделе

Наша кнопка

Разместить ссылку на наш сайт можно воспользовавшись следующим кодом:


Контакты

Если у вас возникли какие либо вопросы, обращайтесь на email администратора: admin@kazreferat.info

Рекурсия

Узнать стоимость написания работы

Содержание

 

Рекурсия  . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 4

 

Пример 4 . . . . . . . . . . . . . . . . . . . . . . . . . . 4

 

Пример 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 6

Рекурсия.

Рекурсией называется ситуация, когда процедура или функция сама себя вызывает. Вот типичная конструкция такого рода:

procedure proc(i:integer);

begin

anweisungen1;

if bedingung then proc(i+1);

anweisungen2;

end;

Вызов proc(1) означает, что proc вызывает себя раз за разом с помощью proc(2), proc(3),.. до тех пор, пока условие bedingung не отменит новый вызов. При каждом вызове выполняется оператор anweisungen 1, после чего порядок выполнения операторов прерывается новым вызовом proc(i+1). Чтобы для каждого вызова был отработан и оператор anweisungen2, все локальные переменные процедуры сохраняются в стеке. Стеком является структура магазинного типа LIFO (Last In First Out), т.е. если, например, при proc(10) условие более не выполняется, anweisungen2 выполняется со значениями, обрабатываемыми в обратном порядке для proc(9),…,proc(1). Локальные параметры помещаются в стек один за другим и выбираются из стека в обратной последовательности (латинское recurrere означает «возвращение назад»).

В Паскале можно пользоваться именами лишь тогда, когда в тексте программы этому предшествует их описание. Рекурсия является единственным исключением из этого правила. Имя proc можно использовать сразу же, не закончив его описания.

Пример1 представляет собой бесконечную рекурсию, с помощью которой можно установить, насколько велик стек. При этом помните, что при использовании директивы (*$S+*) при переполнении стека получим сообщение об ошибке; а при использовании директивы (*$S-*) – нет, а значит, мы скорее всего столкнемся с зависанием системы. Установкой по умолчанию является (*$S+*). Программа будет прервана с выдачей сообщения об ошибке «Error 202: stack overflow error (“Ошибка 202: переполнение стека»).

Пример1:

Program stack_test;

{программа проверки стека}

procedure proc(i:integer);

begin

if i mod 1024 = 0

then writeln(i:6);

proc(i+1);

end;

begin

proc(1);

end.

Стек связан с другой структурой памяти – с динамической областью. С помощью директивы (*$М*) можно управлять размером стека.

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

- с помощью последовательного присоединения (или итерации в форме цикла);

- с помощью вложения одной операции в другую (а именно, рекурсий).

В следующем примере2 один раз счет от 1 до n ведется с помощью цикла, а второй – с помощью рекурсии. При этом хорошо видно, как заполняется, а затем освобождается стек. В процедуре rekursion операция writeln(i:30) выполняется перед рекурсивным вызовом, после чего writeln(i:3) освобождает стек. Поскольку рекурсия выполняется от n до 1, вывод по команде writeln(i:30) выполняется в обратной последовательности n,n-1,…,1, а вывод по команде writeln(i:3) – в прямой последовательности 1,2,…,n (согласно принципу LIFO – последним пришел, первым обслужен).

Пример2:

 Показывает принципиальное различие между итерацией и рекурсией: итерации необходим цикл и локальная переменная k как переменная цикла. Рекурсии ничего этого не требуется!

program iterativ_zu_rekursion;

var n:integer;

procedure rekursion (i:integer);

begin

writeln(i:30);

if i < 1 then rekursion(i-1);

writeln(i:3);

end; (* Рекурсия *)

procedure schleife(i:integer);

var k:integer;

bagin

k :=1;

while k <= i do begin

write(k:3);

k :=k+1;

end;

end; (* Цикл *)

begin

write(‘Введите n:’); readln(n);

writeln(‘Пока:’);

scheife(n);

writeln;

writeln(‘Рекурсия’);

rekursion(n);

end.

Пример3:

Рекурсивная процедура convert переводит десятичное число z в восьмеричную систему путем деления его на 8 и выдачи остатка в обратной последовательности.

Program dezimal_oktal_konvertierung;

{преобразование из десятичной системы в восьмеричную}

var z:integer;

procedure convert(z:integer);

begin

if z > 1 then convert(z div 8);

(* Это рекурсивный вызов *)

write(z mod 8:1);

end;

begin

writeln(‘Введите некоторое положительное число:’);

readln(z);

writeln(‘Десятичное число:’,z:6);

write(‘Восьмеричное число: ’);

convert(z);

end.

Один из наиболее ярких примеров применения рекурсии дают числа Фибоначчи. Они определяются следующим образом:

x[1]=x[2]=1

x[n]=x[n-1]+x[n-2] при n > 2

Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, т.е.

1 1 2 3 5 8 13 21 34 55 …

Следующий пример позволяет вычислить n-ный элемент ряда Фибоначчи как итеративно (то есть в цикле, начиная с х[1] до х[n]), так и рекурсивно (n-ный элемент ряда является суммой двух предшествующих элементов). Причем рекурсивная функция вызывает себя дважды.

Пример4:

С использованием рекурсии вычисляются числа Фибоначчи, причем глубина рекурсии индицируется. Перед каждым рекурсивным вызовом выводится выводиться ASCII-символ с номером 8 (Backspace), а после вызова вновь стирается. Тем самым можно наблюдать за работой программы, поскольку программа за счет delay(300) приостанавливается на 0.3 с.

program fibonacci(input, output);

uses crt;

var n,result:integer;

function fibit(n:integer):integer;

var a,b,c,i:integer;

begin

a := 1; b := 1;

if (n=1) or (n=2)

then fibit :=1

else begin

for i= 3 to n do

begin c :=a+b; a := b; b :=c; end;

fibit :=c;

end;

end;

begin

clrscr;

write(‘n = ‘);

readln(n);

writeln(‘Итеративно:’,fibit(n):5);

writeln(‘рекурсивно:’);

write(‘ ….!….#….!….#….’);

writeln(‘!….#….!….#….!….#’);

write (‘Глубина рекурсии:’);

result := fibrek(n);

writeln;

write(result);

end.

Этот пример демонстрирует прежде всего различия между итерацией и рекурсией. Итерации необходим цикл и вспомогательные величины; итерация сравнительно ненаглядна (см. fibit в приведенном выше примере). Рекурсия обходится без вспомогательных величин и обычно проще для понимания, что демонстрирует следующая запись:

if (n=1) or (n=2) then fibrek := 1

else fibrek := fibrek(n-1)+fibrek(n-2);

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

Если процедура или функция вызывает себя сама, это называют прямой рекурсией. Но может встретиться ситуация, когда процедура А вызывает процедуру В, вызывающую С, а процедура С вновь возвращается к А. В этом случаи мы имеем дело дело с косвенной рекурсией, что демонстрирует приведенный ниже пример. С таким типом рекурсии мы сталкиваемся там, где использована директива forward.

Пример 5:

Следующая программа выдает простые числа от 1 до n, для чего используются функции next и prim, которые вызываются перекрестно, то есть рекурсивно. Одновременно это является примером применения директивы forward.

program primzahlen_rekursiv_berechnen;

{программа рекурсивного вычисления простых чисел}

var n,i : integer;

c : char;

function next(i:integer):integer;forward;

{Это прямая ссылка вперед на функцию next,

которая будет определена позже}

function prim(j:integer):boolean;

{prim имеет значение true, если j простое число,

и false в противном случае}

var k:integer;

begin

k :=2;

while (k*k <= j) and (j mod k < > 0) do

k :=next(k);

{k пробегает последовательность простых чисел, начиная с 2,

вплоть до корня из j, при этом проверяется, делится ли j на

одно из таких простых чисел. При этом используется

следующая функция next}

if j mod k = 0 then prim := false

else prim := true;

end {prim};

function next;

{Параметры уже стоят в ссылке вперед,

next вычисляет, каково следующее за j простое число}

var i:integer;

begin

1 :=i+1;

while not(prim(1)) do 1 :=1+1;

{Итак, next вызывает в свою очередь prim}

next :=1;

end {next};

begin (******* Исполняемая часть программы *******)

write(‘Введите положительное число n,’);

writeln(‘Должны быть определены все’);

writeln(‘предшествующие ему простые числа’);

readln(n);

for i :=2 to n do

begin

if prim(i) then writeln(i:14)

else writeln(i:4);

if i mod 23 = 0 then begin

write(‘<RET>’:60); read(c,c);

end;

end;

end.

 

Другие материалы

  • Финансовые функции и рекурсия
  • ... Mathcad. Все они делятся на три категории: прямые рекурсивные аналоги, частные случаи и обобщения встроенных в Excel финансовых функций. Для первой категории функций и их аргументов используются стандартные обозначения. В иных ситуациях обозначения произвольны. Наличие почти во всех задачах несложно ...

  • Применение рекурсии в алгоритмах с возвратом. Файловый тип. Ввод/вывод
  • ... case TryMove (x, y) of true: WriteLn ('Нашел путь :-)'); false: WriteLn ('Нет путей :-('); end; end; End. Файловый тип. Ввод/вывод.  Все рассмотренные ранее типы данных обладали одним общим свойством - число их компонентов конечно и заранее фиксировано. Однако, существует достаточно ...

  • Использование рекурсии в PHP
  • ... и очень объемным. Ну а если там появится небольшая ошибка... (дальше, я думаю, объяснять не стоит). ------------------------- Эту задачу достаточно легко решить с помощью рекурсии. Пишем небольшую функцию: function tree($uid, $conn) { $sql = "SELECT * FROM x_table WHERE parent_id=$uid" ...

  • VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
  • ... ‑либо образом. Часто требуется сортировать данные несколькими различными способами. Во‑вторых, многие алгоритмы сортировки являются интересными примерами программирования. Они демонстрируют важные методы, такие как частичное упорядочение, рекурсия, слияние списков и хранение двоичных ...

  • ЛИСП
  • ... довольно широко используется как под управлением UNIX, так и под управлением VAX/VMS и в настоящее время является наиболее часто используемой версией Лиспа для систем разделения времени. Кроме того, он широко используется и на 32-битовых микро-ЭВМ и рабочих станциях, работающих под управлением UNIX ...

  • Логическое и функциональное программирование
  • ... (8) следует, что в M нет двух неравных натуральных чисел. Доказательство закончено. 3.2 Рекурсия   Особое место для систем функционального программирования приобретает рекурсия, поскольку она позволяет учитывать значения функции на предыдущих шагах. С теоретической точки зрения рекурсивные ...

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

  • Язык логического программирования Visual Prolog
  • ... числами. Он начинается с имени, называемого функтором (в данном случае date), за которым следуют три аргумента. Функтор в Visual Prolog — не то же самое, что функция в других языках программирования; это просто имя, которое определяет вид составного объекта данных и объединяет вместе его аргументы ...

Rambler's Top100 Рейтинг@Mail.ru
Рефераты и материалы размещенные на сайте принадлежат их законным правообладателям. При использовании материалов сайта, ссылка на KazReferatInfo обязательна!
Казахстанские рефераты
Copyright © 2007-2016г. KazReferatInfo