Содержание

Рекурсия и рекуррентные соотношения

Рекуррентные соотношения

Согласно Физической энциклопедии, рекуррентные соотношения(от лат. recur-rens, род. падеж recurrentis - возвращающийся) - однотипные формулы, которые связывают между собой идущие друг за другом элементы некоторой последовательности (это может быть последовательность чисел, функций и т. д.). В зависимости от природы объектов, связанных рекуррентными соотношениями, эти соотношения могут быть алгебраическими, функциональными, дифференциальными, интегральными и т. п.

Короче говоря, мы имеем способ получения некоторой последовательности каких-то (зависит от наших целей и/или желаний) объектов, которые связаны соотношением вида

A[0] = A;

A[i] = F(A [i-1]),

где A[0] задаётся отдельно, а F каким-то образом, возможно - неформально, определяет следующий элемент последовательности из предыдущего, уже определённого.

Внимание! Иногда рекуррентные соотношения рассматриваются в расширенном виде A[i] = F(A[0], A[1] … A[i-1]), т.е. для определения очередного элемента последовательности используются все или несколько предыдущих элементов последовательности. Пример - числа Фибоначчи, где

A[0] = A[1] = 1;

A[i] = A[i-1] + A[i-2];

Также «Рекуррентным соотношением называется закономерность, связывающая объект более высокого порядка с объектом меньшего порядка» (http://glaznev.sibcity.ru/1kurs/integr/list3.htm)

Ссылки по теме

intuit: Комбинаторные алгоритмы для программистов 7. Лекция: Рекуррентные соотношения - рекуррентные соотношения для получения комбинаторных объектов.

Последовательность Падована

Задача Иосифа Флавия

Рекурсия

Рекурсия

Пример применения рекурсии

Программа, рисующая квадраты от центра (квадрата)

Сначала подготовимся.

| Рисование квадрата в центре
uses oglgraph;                     // Необходимая библиотека, у нас заменяет graph
 
var 
  gd, gm: smallint;      
  mx, my, cx, cy:smallint;         
  x, y, d:smallint;
 
begin
  gd := Detect;                    // Автоматическая установка разрешения
  gm := DetectMode;
  initgraph(gd, gm, '');           // Открытие "графического окна" 
 
{далее все, что Вы хотите нарисовать, например:}
 
mx := getmaxX;
my := getmaxY;
cx := mx div 2;
cy := my div 2;
 
x  := cx;
y  := cy;
d  :=cx div 4;
 
rectangle(x-d, y-d, x+d, y+d);   // А вот и рисование !!!!!!
 
 
 
{конец отрисовки}
  repeat until graphkeypressed;    // Задержка закрытия графического окна до нажатия 
                                   // клавиши для завершения работы программы - 
                                   // иначе рискуете ничего толком не увидеть
 
  closegraph();                    // закрытие графического окна - не обязательно, но рекомендуемо.
 
end.

Введение процедуры для рисования "от центра"

| Использование процедуры
uses oglgraph;                     // Необходимая библиотека, у нас заменяет graph
 
var 
  gd, gm: smallint;      
  mx, my, cx, cy:smallint;          
  x, y, d:smallint;
 
 
  Procedure Crectangle(x,y,d:smallint);
 
  begin
 
    rectangle(x-d, y-d, x+d, y+d);
 
  end;
 
// Раздел кода **************************************************************************************
 
begin
  gd := Detect;                    // Автоматическая установка разрешения
  gm := DetectMode;
  initgraph(gd, gm, '');           // Открытие "графического окна" 
 
{далее все, что Вы хотите нарисовать, например:}
 
mx := getmaxX;
my := getmaxY;
cx := mx div 2;
cy := my div 2;
d  :=cx div 4;
 
Сrectangle(x,y,d);
 
 
 
{конец отрисовки}
  repeat until graphkeypressed;    // Задержка закрытия графического окна до нажатия 
                                   // клавиши для завершения работы программы - 
                                   // иначе рискуете ничего толком не увидеть
 
  closegraph();                    // закрытие графического окна - не обязательно, но рекомендуемо.
 
end.

Рекурсивная процедура с "отсечкой"

| Использование рекурсивной процедуры
uses oglgraph;                     // Необходимая библиотека, у нас заменяет graph
 
var 
  gd, gm:         smallint;      
  mx, my, cx, cy: smallint;          
  x, y, d:        smallint;
 
 
  Procedure Crectangle(x,y,d:smallint);
 
  begin
 
    rectangle(x-d, y-d, x+d, y+d);
 
  end;
 
 
  Procedure Crectangle2(x,y,d:smallint);
 
  begin
 
 
    Crectangle(x, y, d);
    if  d >= 1 then  Crectangle2(x, y, d div 2); // Рекурсивный вызов с "отсечкой" при маленьком d
 
 
  end;
 
// Раздел кода **************************************************************************************
 
begin
  gd := Detect;                    // Автоматическая установка разрешения
  gm := DetectMode;
  initgraph(gd, gm, '');           // Открытие "графического окна" 
 
{далее все, что Вы хотите нарисовать, например:}
 
mx := getmaxX;
my := getmaxY;
cx := mx div 2;
cy := my div 2;
 
 
d  := cx div 4;
x  := cx;
y  := cy;
 
Crectangle2(x,y,d); //Вызов рекурсивной функции
 
{конец отрисовки}
  repeat until graphkeypressed;    // Задержка закрытия графического окна до нажатия 
                                   // клавиши для завершения работы программы - 
                                   // иначе рискуете ничего толком не увидеть
 
  closegraph();                    // закрытие графического окна - не обязательно, но рекомендуемо.
 
end.

Ковёр Серпинского

| Использование другой рекурсивной процедуры
uses oglgraph;                     // Необходимая библиотека, у нас заменяет graph
 
var 
  gd, gm:         smallint;      
  mx, my, cx, cy: smallint;          
  x, y, d:        smallint;
 
 
  Procedure Crectangle(x,y,d:smallint);
 
  begin
 
    rectangle(x-d, y-d, x+d, y+d);
 
  end;
 
 
  Procedure Crectangle3(x,y,d:smallint);
 
  begin
 
 
    if  d >= 1 then  
    begin   
      Crectangle3(x, y, d); 
      d:= d div 2;
 
      Crectangle3(x,     y-2*d, d);
      Crectangle3(x-2*d, y,     d);
      Crectangle3(x,     y+2*d, d);
      Crectangle3(x+2*d, y,     d);
    end;                        // if
 
 
  end;
 
// Раздел кода **************************************************************************************
 
begin
  gd := Detect;                    // Автоматическая установка разрешения
  gm := DetectMode;
  initgraph(gd, gm, '');           // Открытие "графического окна" 
 
{далее все, что Вы хотите нарисовать, например:}
 
mx := getmaxX;
my := getmaxY;
cx := mx div 2;
cy := my div 2;
 
 
d  := cx div 4;
x  := cx;
y  := cy;
 
Crectangle3(x,y,d); //Вызов рекурсивной функции
 
{конец отрисовки}
  repeat until graphkeypressed;    // Задержка закрытия графического окна до нажатия 
                                   // клавиши для завершения работы программы - 
                                   // иначе рискуете ничего толком не увидеть
 
  closegraph();                    // закрытие графического окна - не обязательно, но рекомендуемо.
 
end.
| Рисование квадрата в центре
uses oglgraph;                     // Необходимая библиотека, у нас заменяет graph
 
var 
  gd, gm         : smallint;      
  mx, my, cx, cy : smallint;          
  x, y, d 	 : smallint;
 
procedure Serp(x1, y1, x2, y2: smallint; n: Integer);
var
	x1n, y1n, x2n, y2n: smallint;
 
begin
	if  n > 0  then 
	begin
		x1n := 2*x1 div 3 + x2 div 3;
		x2n := x1 div 3   + 2*x2 div 3;
		y1n := 2*y1 div 3 + y2 div 3;
		y2n := y1 div 3   + 2*y2 div 3;
		Rectangle(x1n, y1n, x2n, y2n);
		Serp(x1, y1, x1n, y1n, n-1);
		Serp(x1n, y1, x2n, y1n, n-1);
		Serp(x2n, y1, x2, y1n, n-1);
		Serp(x1, y1n, x1n, y2n, n-1);
		Serp(x2n, y1n, x2, y2n, n-1);
		Serp(x1, y2n, x1n, y2, n-1);
		Serp(x1n, y2n, x2n, y2, n-1);
		Serp(x2n, y2n, x2, y2, n-1)
	end;
end;
 
begin
        gd := Detect;                    // Автоматическая установка разрешения
        gm := DetectMode;
        initgraph(gd, gm, '');           // Открытие "графического окна" 
 
        mx := getmaxX;
        my := getmaxY;
        cx := mx div 2;
        cy := my div 2;
 
 
        d  := cx div 4;
        x  := cx;
        y  := cy;
 
 
	    Rectangle(x-d, y-d, x+d, x+d);
	    Serp(x-d, y-d, x+d, x+d, 4);
        repeat until graphkeypressed;    // Задержка закрытия графического окна до нажатия 
                                         // клавиши для завершения работы программы - 
                                         // иначе рискуете ничего толком не увидеть
 
        closegraph();                    // закрытие графического окна - не обязательно, но рекомендуемо.
 
end.