Рекурсивное программирование (стр. 1 )

Государственное учреждение образования

«Речицкая районная гимназия»

Рекурсивное программирование

Выполнил

ученик 8 «А» класса

Руководитель

учитель информатики

Речица, 2013

Понятие рекурсии

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

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

Способность функции обращаться к себе самой называется рекурсией.

Основой для разработки рекурсивных алгоритмов служат, так называемые, рекуррентные соотношения (формулы), устанавливающие зависимость между результатами какого-либо действия на n-м шаге от результата аналогичных действий, полученных на предыдущем n-1-м шаге. Такие алгоритмы часто включают в олимпиады по информатике.

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

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

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

program pr1;

procedure PopeAndDog1;

begin

  writeln(‘У попа была собака, он ее любил’);

  writeln(‘Она съела кусок мяса, он ее убил’);

  writeln(‘похоронил и надпись написал:’);

PopeAndDog1

end;

Begin

PopeAndDog1

End.

Однако если оператор вызова процедуры поставить перед выводом текста, как показано ниже,

Program PR2;

Procedure PopeAndDog2;

  begin

  PopeAndDog2;

  writeln(‘У попа была собака, он ее любил’);

  writeln(‘Она съела кусок мяса, он ее убил’);

  writeln(‘похоронил и надпись написал:’);

  end;

Begin

  PopeAndDog2

End.

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

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

Таким образом, какой-либо локальной переменной А на разных уровнях рекурсии будут соответствовать различные ячейки памяти, которые могут иметь разные значения. Поэтому, воспользоваться значением переменной А i-го уровня рекурсии можно находясь только на i-ом уровне.

Максимальное число рекурсивных вызовов процедуры без возвратов, который происходит во время выполнения  программы, называемой глубиной рекурсии. Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии. Главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполнятся по условию, которое на каком-то уровне рекурсии станет ложным (т. к. бесконечной памяти не существует). Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент  копий рекурсивной процедуры.

  Структура рекурсивной процедуры может принимать 3 разные формы.

1. Форма с выполнением действий до рекурсивного вызова (с выполнением 

действий на рекурсивном спуске).

  Procedure Rec;

  begin

  S;

  if  условие then Rec;

  end;

2. Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате). 

  Procedure Rec;

  begin

  if  условие then Rec;

  S;

  end;

3. Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

  Procedure Rec;

  begin

  S1;

  if  условие then Rec;

  S2;

  End;

  или

  Procedure Rec;

  begin

  if  условие then begin

  S1;

  Rec;

  S2;

  end;

  end;

Все виды рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисления n!, безразличны к тому, какая используется форма рекурсивной процедуры. Однако есть классы задач, при решении которых требуется (программисту) сознательно управлять ходом работы рекурсивных процедур и функций. Такими в частности являются задачи, использующие списковые и древовидные структуры данных.

Выполнение действий на рекурсивном спуске.

Пример. Алгоритм  вычисления факториала. Введем дополнительно 2 параметра:

  P-для выполнения операции умножения накапливаемого факториала на  очередной множитель (до рекурсивного вызова);

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

Program Factorial;

var n:integer;

function Fact_dn (p:longint;  i, m,:integer):longint;

begin

  p:=p* i;  {накопление факториала стоит до оператора рекурсивного} 

  { вызова, сл-но вычисление выполняется на спуске}

  if i=m then Fact_dn:=p

  else  Fact_dn:=Fact_dn(p, i+1, m)

end;

Begin

  write(‘введите число’);

  readln(n);

  writeln(‘факториал n!=’, Fact_dn(1,1,n));

End.

Уро-вень рекур-сии	Рекурсивный спуск	Рекурсивный возврат
0	Ввод (n=5)	Fact_dn(1,1,5)	Вывод n!=120
1	P:=1*1  (1)	I:=1	Fact_dn(1,2,5)	Fact_dn:=120
2	P:=1*2  (2)	I:=2	Fact_dn(2,3,5)	Fact_dn:=120
3	P:=2*3  (6)	I:=3	Fact_dn(6,4,5)	Fact_dn:=120
4	P:=6*4  (24)	I:=4	Fact_dn(24,5,5)	Fact_dn:=120
5	P:=24*5  (120)	I:=5	Fact_dn:=120	Fact_dn:=120

Выполнение действий на рекурсивном возврате.

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

Program Factorial;

var n: integer;

function fact_up (i: integer): longint;

var p: longint;

begin

if i=1 then p:=1

  else p:=fact_up(i-1);

fact_up:= p*i; {накопление факториала стоит}

  {после оператора рекурсивного}

  {вызова. сл-но вычисление вы-}

  {выполняется на возврат}

end;

Begin

  write (‘введите число n: ’);

  readln (n);

  writeln (‘факториал n!=’,fact_up(n));

END.

Трассировка по уровням рекурсии.

Текущий уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
0	ввод (n=5); Fact_up(5)	ввод n!=120
1	i =5; p:=fact_up(4)	Fact_up:=24*5 (120)
2	i =4; p:=fact_up(3)	Fact_up:=6*4 (24)
3	i =3; p:=fact_up(2)	Fact_up:=2*3 (6)
4	i =2; p:=fact_up(1)	Fact_up:=1*2 (2)
5	i =1; p:=1;	Fact_up:=1*1 (1)

Выполнение действий как на рекурсивном спуске и на возврате

Пример. Вывести  на печать символы введённой строки 'HELLO' в  обратном направлении.

  Program  Reverse;

  Procedure  Rev;

  Var  Ch: char;

  Begin

  If not eoln  then  Begin

  Read (Ch);  Rev;  Write (Ch);

  End  End;

Begin

  Rev 

End. 

Текущий уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
0	Rev;
1	Eoln=false; ввод: ‘н’; Rev;	Вывод: ’н’;
2	Eoln=false; ввод: ‘e’; Rev;	Bывод: ‘e’;
3	Eoln=false; ввод: ‘e’; Rev;	Вывод: ‘L’;
4	Eoln=false; ввод: ‘e’; Rev;	Вывод: ‘L’;
5	Eoln=false; ввод: ‘o’; Rev;	Вывод: ‘o’;
6	Eoln:=true;

Примеры рекурсивных алгоритмов