===== Рекурсия и рекуррентные соотношения ===== ==== Рекуррентные соотношения ==== Согласно [[http://dic.academic.ru/dic.nsf/enc_physics/4527/%D0%A0%D0%95%D0%9A%D0%A3%D0%A0%D0%A0%D0%95%D0%9D%D0%A2%D0%9D%D0%AB%D0%95| Физической энциклопедии]], **рекуррентные соотношения**(от лат. 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 |]]) **Ссылки по теме** [[http://www.intuit.ru/department/algorithms/algocombi/7/| intuit: Комбинаторные алгоритмы для программистов 7. Лекция: Рекуррентные соотношения]] - рекуррентные соотношения для получения комбинаторных объектов. [[http://dic.academic.ru/dic.nsf/ruwiki/503457| Последовательность Падована]] [[http://dic.academic.ru/dic.nsf/ruwiki/638596| Задача Иосифа Флавия]] ==== Рекурсия ==== Рекурсия === Пример применения рекурсии === === Программа, рисующая квадраты от центра (квадрата) === Сначала подготовимся. 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.