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

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

Согласно Физической энциклопедии, рекуррентные соотношения(от лат. 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];

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

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.